| Is there something glareingly wrong in the following proof? It seemed
suspisciously easy for one of Andrew's posers. If it's sound then the
generalisation seems straightforward.
Define S_i to be the total number of birds seen on all days up to and including
day i.
We have:
i) S_i+1 >= S_i + 1
ii) S_i+7 <= S_i + 10
These conditions also imply that:
iii) S_i+1 <= S_i + 4
Let n be the last i for which S_i < 21. We assert that n >= 11. For S_1 can be
at most 4, hence S_8 can be at most 14, and S_15 can be at most 24. This means
that S_14 can be at most 23, S_13 at most 22, S_12 at most 21 and S_11 at most
20.
Let A be the set of numbers S_i + 21, 1 <= i <= n. There are at least 11
numbers in this set, and all lie in the range S_n + 1 to S_n + 21.
Now let m be the last i for which S_n+i < S_n + 21. Applying the same argument
as above, we construct a set B of 11 or more numbers S_n+1 to S_n+m lying in the
range S_n + 1 to S_n + 21.
A and B have between them 22 or more elements, but there union has at most 21
elements. Their intersection must therefore be non-empty. So we have some S_i
in B equal to some S_j + 21 in A, and S_i - S_j = 21. Ie, the total number of
birds seen goes up by 21 between days i and j. QED.
Andy.
|
| Giving that at least 1 bird is sighted every day. It would seem that to ensure
that you see "at least" 21 birds you would have to spend at most 21 days.
On the other hand when the observer is "very lucky" he can see 10 birds in 7
days that means that in 14 days at most he can see 20 birds. So on day 15
can he see more than 1 bird? As he starts his vacation on day 1 he can see 4
birds then he can see at most one bird a day for the next six. (there is no
mention about equal distribution in this problem.)On day 8 he can see 4 more
birds (how lucky can he be) and again at most 1 for the next six days. And
finaly on day 15 he can see 4 more birds, (wonderful but not exactly 21 either)
that will total 24 birds. Therefore as the problem is stated "exactly" 21 birds
is proven false. Now if the problem also read that at most he saw any giving
day was 2 then for the 10 birds in 7 consecutive days to work , he would have
to see exactly 1, 2, 1, 2, 1, 2, 1, 2, 1, ... if and only if it was extactly 10
birds and not " at most". And even then if he saw 2 birds on day 1 at day 15
he would end up seeing 22 birds and not 21.
|
| Re: -.2. Yes, this isn't a hard problem, but it does require clear thinking.
Re: -.1. I get confused in the second paragraph.
I had a slightly different answer from .2, fwiw:
The shortest possible holiday is 21 days.
If the ornithologist, O, was only around for 20 days, then he might
have seen 1 bird per day, and not seen 20 birds at all.
So, let's consider just the first 21 days of the ornithologist's
holiday. Suppose that he sees N (>= 21) birds in total over this period.
Since the period divides up into three weeks of 7 days, we know that N =< 30,
by the 7-day constraint. In fact, 21 days is sufficient to guarantee a
21-bird period, as long as N < 42. So we will take N < 42 in all that follows.
We'll define A_i, for i = 0 to N as follows:
A_0 = A_N = 1
for j = 1 to N-1,
A_j = 1 if the jth bird and the (j+1)th birds were seen on different
days, otherwise:
A_j = 0 (the jth and the (j+1)th bird were seen on the same day)
Since N < 42, the limits of the following sum are meaningful [yes,
even when N=41, when we assume the sum is over zero summands].)
sum(j=N-20 to 20) A_j
=< sum (j=N-20 to 20) 1
= 41-N
Now sum(j) A_j = 22, (because on each day at least one bird was
spotted, therefore each time when A_j = 1, that records the passage of 1 night).
=> sum(j=0 to N-21) A_j + sum(j=21 to N) A_j >= N-19
Why is this important? Because, by the pigeon hole principle, Eugene, it
means that one of the following N-20 pairs of [distinct, since N-21 < 21]
elements:
A_0 & A_21
A_1 & A_22
.
.
.
A_(N-21) & A_N
satisfies A_j & A_(j+21) = 1, and we are done.
*******************************************************************************
What this all suggests is that the problem (which I cribbed from the
French math magazine Quadrature) can be considerably stiffened. We keep
the constraints:
(1) At least one bird per day.
(2) Not possible to avoid 21-bird period of days.
but junk:
(3) Not more than 10 birds in any 7 day period.
and could replace it with:
(3') Not more than 13 birds in any 7 day period.
Regards,
Andrew.
|
| > An ornithologist goes on a field trip. Each day he spots a number of
>birds, at least one bird each day. He is not very lucky: he never manages to
>spot more than 10 birds in any consecutive period of 7 days.
>
> Prove that if his holiday is long enough (how long?) then there must
>come some period of consecutive days (not necessarily 7) during which he
>spots *exactly* 21 birds.
>
> Generalize.
The difficult thing about tbis problem is the bizarre 10 bird / 7 day
maximum, which implies the simpler, weaker and more useful 41 bird / 21 day
maximum. Messy problems are harder than clean problems, but here fortunately,
the mess can be cleaned up.
If we want to generalize the proof, then we say:
"D is a constant. At least 1 bird/day. Over any consecutive D days,
less than 2D birds. How long must the holiday be so that he spots exactly
D birds over some period of days."
It's clear that at least D days are necessary, or otherwise he may
see 1 bird/day and *never* reach the threshold. We'll show that D days are
sufficient. Consider the first D days of his holiday. Let the total number
of birds seen over this period be N. D =< N < 2D.
Define A_j as in -.1.
sum(j=0,...,N) A_j = D+1
sum(j=N-D+1,...,D-1) A_j =< sum(j=N-D+1,...,D-1) 1 = 2D-1-N
[Note, the above sum is well-defined even when N=2D-1, in which case the
sum is over 0 summands, and is zero.]
Subtracting the inequality from the equality:
sum(j=0,...,N-D) A_j + sum(j=D,...,N) A_j >= N-D+2
=> sum(j=0,...,N-D) [A_j + A_(j+D)] >= N-D+2
For the sum of K natural numbers to be greater than K, at least one
term must be >= 2. So there is J such that:
A_J = A_(J+D) = 1.
By the definition of A_j, this says that there is a period of days which
began just before the spotting of the Jth bird, and ended just after the
spotting of the (J+D)th, as requested.
This is all just -.1 with 21 replaced by D.
Now, suppose that we actually had N > 2D-1 birds over the D days.
If N is even and D is odd, then by spotting the birds two at a time (mating
season) we can avoid ever seeing D of them in a period.
A more generalizable way of avoiding D birds in a period is to spot
one bird/day for D-1 days, and N-D+1 birds on the remaining day. If N > 2D-1,
this works a treat. So our problem statement is now maximally tense.
Re: .2.
.2 did not actually compute the figure "21 days". Andy computed in
his notation, n >= 11, and presumably implied m >= 11, hence in his notation
n+m >= 22 days are required. His approach is basically viable, but he
neglected to include S_0 in his set A, and hence lost the precision here.
Regards,
Andrew.
|