Is there a solution using the Box Principle for a chessmaster's game schedule?

[symplectic_manifold]

Hi!
I'm working through the book "Problem Solving Strategies" by A.Engel at the moment.

There is an example in the introductory section of the "The Box Principle" chapter, I don't quite understand.

Problem:
A chessmaster has 77 days to prepare for a tournament. He wants to play at least one game per day, but not more than 132 games. Prove that there is a sequence of successive days on which he plays exactly 21 games.

Solution:
Let $a_i$ be the number of games played until the $i$th day inclusive.
Then $1\le{a_1}<...<a_{77}\le{132}\Rightarrow22\le{a_1+21}<a_2+21<...<a_{77}+21\le{153}$
Among the 154 numbers $a_1,...,a_{77},a_1+21,...,a_{77}+21$ there are two equal numbers. Hence there are indices i, j, so that $a_i=a_j+21$. The chessmaster has played exactly 21 games on the days # $j+1,j+2,...,i$.

Well, if I got it right, the boxes are the days and the pearls are the games, spread among the days and whose number per day is not greater than 132.
(Personally, I would expect the converse)

My first question would be: Why is the second sequence formed from the initial added to this, i.e. why is there suddenly a doubled number of games, and hence boxes?

 

[VietDao29]

Well, if I got it right, the boxes are the days and the pearls are the games, spread among the days and whose number per day is not greater than 132.
(Personally, I would expect the converse)

You have 2 sequences:
$$1 \leq a_1 \leq a_2 \leq ... \leq a_{77} \leq 132$$
$$22 \leq a_1 + 21 \leq a_2 + 21 \leq ... \leq a_{77} + 21 \leq 153$$
So, you can say that the 154 numbers$$a_1, ..., a_{77}, a_1+21, ..., a_{77}+21$$ will take the number from 1 to 153. There will be 153 boxes, but there will be 154 pearls. So at least two of the numbers $$a_1, ..., a_{77}, a_1+21, ..., a_{77}+21$$ have the same value.

My first question would be: Why is the second sequence formed from the initial added to this, i.e. why is there suddenly a doubled number of games, and hence boxes?

Since you need to prove : $$a_i = a_j + 21$$, it means between the day i + 1, to the day j, the chessmaster will play 21 games, you need to create another sequence : $$22 \leq a_1 + 21 \leq a_2 + 21 \leq ... \leq a_{77} + 21 \leq 153$$ and prove that at least two of those 154 numbers have the same value.
I don't know if it's clear enough.
Viet Dao,

 

[symplectic_manifold]

So far, thank you!
I'm sorry but I still don't understand why the second sequence must be generated , although I got your argument with 153 boxes and 154 pearls.

I found an analogous, if not identical problem, which I understood.

Problem:
A certain island is home to 510 seals. Suppose each seal has 10 or more mustaches, but not more than 30. Prove that among these 510 seals at least 25 of them have an equal number of mustaches.
Solution:
We divide the seals into 21 groups according to how many mustaches they have (the set {10,...,30} has 21 elements), and assume that each group has at least 24 seals, then there are at least 24*21=504<510 seals on the island. This means that at least one group has at least 25 seals with the same number of mustaches.

The problem is that although both problems have much in common, when I reformulate the initial problem in terms of the second, they seem almost identical, but nevertheless something is different about the original one. I wonder if such a reformulation is allowed:
A certain island is home to 77 seals. Suppose each seal has 1 or more mustaches, but not more than 132. Prove that among these 77 seals at least n-1 of them have exactly 21 mustaches.

As you see, this is a blind reformulation, but I have a subtle feeling that it's inappropriate or even false.

In the problem with the seals, the boxes are the 21 groups according to the number of mustaches, and the pearls are the 510 seals. Obviously the number of pearls is greater than the number of boxes. It seems so clear to me, and I don't have any problem to apply the Dirichlet principle here in its original form...I can vividly imagine the whole picture.

But in the reformulation the number of seals (pearls) is less than the number of mustaches (boxes). I find it rather difficult to imagine the converse situiation - the boxes are the seals (days) and the pearls - the mustaches (games).

Was I right to say, that in the original problem the games are pearls and the days are boxes? If so, could you/anyone describe the application process of the box principle in this problem?...Plleeeaasee!

 

[VietDao29]

A certain island is home to 77 seals. Suppose each seal has 1 or more mustaches, but not more than 132. Prove that among these 77 seals at least n-1 of them have exactly 21 mustaches.

Nope, you cannot do this problem. Unless, you add some more information and change something to follow:
A certain island is home to 77 seals. Suppose each seal has 1 or more mustaches, but not more than 132, and none of them have the same number of mustache. Prove that among these 77 seals at least n-1 of them have exactly 21 mustaches. (This italic sentence is wrong). It should reads, prove that sum of the difference in moustaches of some seal is exactly 21.

...and assume that each group has at least 24 seals, then there are at least 24*21=504<510 seals on the island. This means that at least one group has at least 25 seals with the same number of mustaches.

The 'at least' should be change to 'at most', so it will make more sense. If the number of seals has the same number of moustache is at most 24. Then the maximum number of seal should be : 24*21=504<510 (contradiction). (21 different number of moustache).
Okay, let's talk about the last problem of the chessmaster.
I did make a mis take in my post, but somehow I cannot edit it (there's no edit button ).

$$1 \leq a_1 \leq a_2 \leq ... \leq a_{77} \leq 132$$
$$22 \leq a_1 + 21 \leq a_2 + 21 \leq ... \leq a_{77} + 21 \leq 153$$

It should reads:
$$1 \leq a_1 < a_2 < ... < a_{77} \leq 132$$
$$22 \leq a_1 + 21 < a_2 + 21 < ... < a_{77} + 21 \leq 153$$
Why should you create the second array? Because you want to prove that : $$a_i = a_j + 21$$, for some i, j. $$a_x$$ indicates the number of games the chessmaster has played after the x-th day. So if there exist number i, j such that : $$a_i = a_j + 21$$. It means after i-th days, the number of games the chessmaster plays is 21 games more than the games he has played after the j-th day. It means in the day j + 1, .. i, the chessmaster plays exactly 21 games.
So how can you get $$a_j + 21$$?? And how can you know what's its range? So you should generate the second sequence, and that's what the writter does :
$$22 \leq a_1 + 21 < a_2 + 21 < ... < a_{77} + 21 \leq 153$$
Any clearer now??
Viet Dao,

 

[Doodle Bob]

Solution:
Let $a_i$ be the number of games played until the $i$th day inclusive.
Then $1\le{a_1}<...<a_{77}\le{132}\Rightarrow22\le{a_1+21}<a_2+21<...<a_{77}+21\le{153}$
Among the 154 numbers $a_1,...,a_{77},a_1+21,...,a_{77}+21$ there are two equal numbers. Hence there are indices i, j, so that $a_i=a_j+21$. The chessmaster has played exactly 21 games on the days # $j+1,j+2,...,i$.

Well, if I got it right, the boxes are the days and the pearls are the games, spread among the days and whose number per day is not greater than 132.
(Personally, I would expect the converse)

Actually, the boxes are the numbers from 1 to 153 (a total of 153) and the pearls are the 154 numbers in the set $a_1,...,a_{77},a_1+21,...,a_{77}+21$, of which there are 154 but which also are elements of the set {1, ..., 153}. Hence there has to be a repeat somewhere.

Is using the metaphor "boxes and pearls" common these days? I've always taught this as the pigeonhole principle.

 

[symplectic_manifold]

Oh, I'm really sick!
Now I see my mistake! Of course, making such a silly mistake like this can make any problem seem to be difficult. :grumpy:

Anyway, I think I completely misunderstood the statement of the problem.
It reads: Prove that there is a sequence of successive days on which he plays exactly 21 games. This means that the chessmaster plays IN SUM 21 games over a period of several consecutive days, and NOT that he plays 21 games EACH DAY for a number of days.

VietDao29, I think now that I unveiled my mistake I understand this:

It should reads, prove that sum of the difference in moustaches of some seal is exactly 21.

Am I right? Exactly this was my mistake, wasn't it?

I'm really ashamed!

 

[VietDao29]

I'm really ashamed!

It's good that you see your mistake. By the way, don't be ashamed. Everyone can make mistakes.
Viet Dao,

 

[mansi]

how do we get the inequality 1<= a1 <=...<=a77 <= 132 ?? it hasn't been mentioned anywhere that the number of games played keeps increasing with each passing day, has it??

 

[symplectic_manifold]

Applying the pigeon hole principle, the first step you make is dividing those 77 days into 132 categories according to the number games played on one particular day. So if there are two days with the same number of games, you better assign each day in a different category with a different number less than the initial one, so that in sum you get your initial value for games for two days. For example, if you say there are two days, on which the chessmaster plays 3 games, you can as well split the pair and put each day in the categories 1 and 2 respectively, thus the numbers keep increasing. This is the justification for the form of the above inequality, and also the way the pigeon hole principle works.

I hope this was helpful. :)

 

[mansi]

it was...thanks!