Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is for self-study. This question is from Rosen's "Discrete Mathematics And Its Applications", 6th edition.

An arm wrestler is the champion for a period of 75 hours. (Here, by an hour, we mean a period starting from an exact hour, such as 1 P.M., until the next hour.) The arm wrestler had at least one match an hour, but no more than 125 total matches.

1 - Show that there is a period of consecutive hours during which the arm wrestler had exactly 24 matches.

2 - Is the statement in the previous exercise true if 24 is replaced by

a) 2? b) 23? c) 25? d) 30?

My solution to part 1 is the following, based on Rosen's solution to a similar problem given as example in the text:

1 - If I consider $a_i$ to be the number of competitions until the $i^{th}$ hour, then, $1\leq a_1<a_2<\cdots<a_{75}\leq 125$, because there are no more than 75 hours and the total number of competitions is no more than 125. Now I will add 24 to all the terms of the above inequality: $25\leq a_1+24<a_2+24<\cdots<a_{75}+24\leq 149$.

There are 150 numbers $a_1,\cdots,a_{75},a_1+24,\cdots,a_{75}+24$. By the inequalities above, these numbers range from 1 to 149. Then, by the pigeonhole principle, at least two of them are equal (in a list of 150 integers ranging from 1 to 149, at least two are equal).

Because all the numbers $a_1,\cdots,a_{75}$ are distinct, and all numbers $a_1+24,\cdots,a_{75}+24$ are also distinct, it follows that $a_i = a_j + 24$ for some $i > j$. Therefore, from the $(j+1)^{th}$ hour to the $i^{th}$ hour, there were exactly 24 competitions.

Now, I will show the attempt at a solution for part 2:

2 - a) The same reasoning as above can be used:

$1\leq a_1<a_2<\cdots<a_{75}\leq 125$. Adding 2 to all terms:

$3\leq a_1 + 2<a_2 + 2<\cdots<a_{75} + 2\leq 127$

So, there are 150 numbers that range from 1 to 127. Therefore, by the pigeonhole principle, at least $\left \lceil \frac{150}{127} \right \rceil$ = 2 numbers must be equal. So, there is an $a_i = a_j + 2$. This guarantees that there is a period of consecutive hours during which there were exactly 2 competitions.

b) The same reasoning as above can be used:

$1\leq a_1<a_2<\cdots<a_{75}\leq 125$. Adding 23 to all terms:

$24\leq a_1 + 23<a_2 + 23<\cdots<a_{75} + 23\leq 148$

So, there are 150 numbers that range from 1 to 148. Therefore, by the pigeonhole principle, at least $\left \lceil \frac{150}{148} \right \rceil$ = 2 numbers must be equal. So, there is an $a_i = a_j + 23$. This guarantees that there is a period of consecutive hours during which there were exactly 23 competitions.

c) $1\leq a_1<a_2<\cdots<a_{75}\leq 125$. Adding 25 to all terms:

$26\leq a_1 + 25<a_2 + 25<\cdots<a_{75} + 25\leq 150$

In this case, there are 150 numbers that range from 1 to 150. So, there are not necessarily two equal numbers. Therefore, we can't conclude anything directly.

But it is possible to show that the statement is not true for 25, because an explicit counter-example (suggested below in the comments) can be found. Suppose the number of matches until each one of the 75 hours is, respectively: $\{1,2,\cdots,25,51,\cdots,75,101,\cdots,125\}$. Here, there are no pairs of numbers whose difference is 25.

d) $1\leq a_1<a_2<\cdots<a_{75}\leq 125$. Adding 30 to all terms:

$31\leq a_1 + 30<a_2 + 30<\cdots<a_{75} + 30\leq 155$

In this case, there are 150 numbers that range from 1 to 155. So, we can't apply the pigeonhole principle here, similarly to the above situation. It is not easy to find a counter-example in this case; I think that, for 30, the statement is always true (that is, there is always a period of consecutive hours during which there were exactly 30 matches). But I'm not sure how to prove it.

Edit: I think I found a way to prove it, based on the suggestion given by Lopsy; I've included it as an answer to this question.

Thank you in advance.

share|improve this question
1  
Just because the pigeonhole principle doesn't apply immediately doesn't mean that it isn't true - you'd need to come up with an explicit counter-example. –  Thomas Andrews Jan 8 '12 at 16:07
1  
In the case of $25$, you can come up with a pretty easy counter-example - $\{a_i\}=\{1,2,...,25,51,...,75,101,...125\}$. Can you come up with a counter-example for $30$? –  Thomas Andrews Jan 8 '12 at 16:15
    
@ThomasAndrews: Actually it seems that it's not possible to come up with a counter-example for 30. If I use the same reasoning you used for 25: $\{1,\cdots,30,61,\cdots,90,121,\cdots,125\}$. In this list there are only 65 hours. But there are 75 hours and at least 1 match per hour. If I added more numbers smaller than 125 to this list, I would get 2 numbers whose difference is 30. It seems to mean that the statement is valid for 30. –  anonymous Jan 8 '12 at 17:54
    
I didn't say that you could find a counter-example, I asked if you could :) but the fact that my counter example doesn't easily extend to 30 is again not proof that there is no counter-example for 30, so you'll need to prove it. –  Thomas Andrews Jan 8 '12 at 19:04
2  
Hint: there can only be three $a_i$ in the set {1, 31, 61, 91, 121}, right? Okay, now keep using this idea... you should be able to finish the problem using this. –  Lopsy Jan 9 '12 at 2:15

1 Answer 1

up vote 2 down vote accepted

I'm posting this answer to my own question because I think I found a solution, but I would appreciate feedback on whether the solution below is complete.

The only detail that is missing to complete part d is that I need to show that the statement is true if 24 in the original statement is replaced by 30; that is, I will try to show that there is a period of consecutive hours during which the arm wrestler had exactly 30 matches (since there seems to be no counter-example for this case).

I think I found a way to prove it, based on the suggestion given by Lopsy in the comments to the question. This attempt is very similar to the accepted answer here: Prove that 2 students live exactly five houses apart if.

We build the following sets: the 5-element sets $\{1, 31, 61, 91, 121\}$, $\{2, 32, 62, 92, 122\}$, ..., $\{5, 35, 65, 95, 125\}$, and the 4-element sets $\{6, 36, 66, 96\}$, $\{7, 37, 67, 97\}$, ..., $\{30, 60, 90, 120\}$. The purpose of these sets is to represent every possibility of number of matches played so far. They encompass all numbers from 1 to 125 and, inside each set, the difference between adjacent numbers is 30; however, there are no numbers from two different sets whose difference is 30. There are 5 five-element sets, and 25 four-element sets.

Now, if I want to choose 75 numbers from all sets so that there are no two numbers whose difference is 30, I have to choose at most 3 elements from the sets with 5 elements (for example, I can choose 1, 61 and 121 from the set $\{1, 31, 61, 91, 121\}$; if I choose one more, then clearly two of them will have difference equal to 30), and at most 2 elements from the sets with 4 elements (for example, I can choose 30 and 120 from $\{30, 60, 90, 120\}$, but, if I choose one more, then clearly two of them will have difference 30). There are 30 sets in total; since there are 5 sets with 5 elements and 25 sets with 4 elements, the maximum number of elements that can be chosen so that no two of them have 30 as difference is $3\times 5 + 2\times 25 = 15 + 50 = 65$ numbers. But I need to choose 75 numbers. So, there must be some numbers whose difference is 30.

Does this make sense, or is there some mistake?

share|improve this answer
    
Looks fine to me. –  Peter Taylor Feb 5 '12 at 13:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.