Assigned Problems 4.2

• 4.2 -- P248 4, 5, 6, 11, 15, 18, 21, 23, 26, 29
• Problem 4,5: Given d+1 consecutive integers there are two whose remainder when divided by d are equal. And I think question 5 says something like, there is exactly one which is divisible by d.

For the first send each of the d+1 integers to their remainder when divided by d (i.e. k is sent to (k mod d) ). Since there are d+1 integers and the remainder is between 0 and d-1, i.e. d possible values, the conclusion follows.
Question 5 is kind of like the pigeon hole in reverse. Again, each of the d consecutive integers are sent to their mod d value. If you did not use each possible mod d value then some pair from the d consecutive integers have the same remainder when divided by d. But this is not possible, if d divides the difference of two distinct numbers, these numbers are a multiple of d apart.

• Problem 6: If f is a function from S to T both finite with |S|> |T|, then f is not one-to-one.

This is just a restatement of the pigeon hole principle: N = |S| many objects are placed (by f) in k = |T| < N holes implies that two go to the same hole. I.e. there are s and s' in S, such that f(s)=f(s').

• Problem 11: 5 chosen from 1-8 means two will add to 9, what about only 4 chosen?

Build boxes so that if two numbers are sent to that box, then they add to 9. Well, {1,8} is box 1, {2,7} is box 2, {3,6} is box 3, {4,5} is box 4. Now, 5 numbers and 4 boxes means that two come from the same box. Of course 4 doesn't work: {1,7,6,4} for example, is 1 from each box.

• Problem 15: x is irrational then for each positive n, there is a j <n such that jx is within 1/n of an integer.

Think about this, it is very interesting. Take any irrational number and spin the Wheel of Fortune wheel x*360 degrees each time for n successive spins. At least once it will come back within 1/n * 360 degrees of the starting position. More generally it can be shown that if you just keep going the wheel will stop at virtually every position (well at least arbitrarily close to every position). But if you spin it by r*360 for some rational angle it will eventually settle on a pattern and only visit finitely many positions. It is the same on a pool table, if you hit a bank at an irrational angle (and the sides of the pool table are rational length) then the ball (without friction) will get abitrarily close to every spot on the table.

Let us think of this in terms of the spinning wheel, i.e. since we only care how close we are to an integer but not what the integer is we can just think of going around in a circle rather than along the real line.

The hard part to this question is to realize that what we are really looking for is a pair j < j' such that j*x and j'*x are with 1/n of each other. Here's why: if we pretend that we start all over again from the position j*x, then after j' - j spins we are very close to the starting point again. In other words if we start at the beginning and make j' - j spins we are very close to the starting position, which is what we want. So we just partition the Wheel of Fortune into little interval sectors of (1/n)*360 degrees. Of course there are n of them. For each j = 1, ..., n, send j to the value d_j, where d_j is the index of the sector that j spins lands us in (number the sectors starting from 12 o'clock and go clockwise). I think we need a little trick here. If any of the d_j are either 1 or n, then we have what we want. So instead assume that none of them are 1 or n, then we get that n values of j are being sent to n-2 values of d_j, hence 2 go to the same place, so we get our j and j'.

• Problem 18 : 101 people of different heights in a line. Ask 11 to stand forward so that their heights either increase left to right or decrease left to right.

This is just the n^2 + 1 list of numbers has a n+1 length increasing of decreasing sublist. n=10.

• Problem 21 : In a group of 10 people there are either 3 mutual friends or 4 mutual strangers.

This is a slight improvement of the Ramsey Theorem. Consider Person numer 10. Split 1-9 into two sets A and B. Every person in A is a friend of 10 and no one in B knows Person 10. If there are just two people in A that know one another then those 2 plus Person 10 form a group of 3 mutual friends. So we might as well assume that no two people in A know one another. How many are there in A? If there are 4 or more, then we have our 4 mutual strangers so we might as well assume there are no more than 3 in A. That leaves 6 in B. Assume now that B has no 3 mutual friends. So we are down to the final case, we must produce 4 mutual strangers (one of which will be 10). So we just have to show that B contains 3 mutual strangers. Pick any member of B, suppose it is 9. Recursively, Split B into BA and BB (friends of 9 and strangers to 9). No two in BA know one another since then we'd have 3 friends (9 and those two). Therefore BA consists of mutual strangers. If there are 3 elements in BA, we are done (10 plus those 3). Therefore we may assume there are no more than 2 elements in BA which leaves at least 5-2 ( B - {9} has 5 and BA has 2) in BB. So BB has at least 3 members so two of them are strangers. Finally these 2 plus 9 and 10 yield the desired group of 4 strangers.

• Problem 23 : 25 million people in Canada. There are 4 born on the same day of the year and who have the same three initials.

Just pigeon hole with big numbers. 366 days or less in a year and 26^3 possible three initials. According to my editor's multiplying ability that makes 6,432,816 possible days of the year and three initial permutations. Clearly 3 times this quantity is slightly less than 21 million so there must be 4 people who share the same combination.

• Problem 26 : Networked 6 computers and each is directly connected to at least one other. Then there are two which are connected to the same number.

For each of the 6 computers, there is a number from 1 to 5 representing how many that computer is connected to (not itself!).

• Problem 29 : An arm wrestler is champion for 75 hours. At least 1 match per hour and no more than 125 total matches. There was a period of consecutive hours when the wrestler had exactly 24 matches.

This is just like the baseball tournament of course. Let a_i denote the number of matches by the end of the i-th hour. In case we need it we can note that we can include a_0 = 0. At least one match per hour tells us that all the a_i are distinct. 75 hours tells us we have the values: a_0, a_1, ..., a_{75}. No more than 125 total matches, hence a_{75} is no larger than 125 (and all the other a_i are strictly smaller). We want to find a pair i< j, so that a_i + 24 = a_j. Let us make another list of numbers:
a_0 + 24, a_1 +24, ..., a_{75}+24.
If we can get a number, a_j, from the first list to equal a number, a_i + 24, from the second list, we have what we need.
The combined two lists (constituting 76 + 76 = 152 entities) range in value from a_0=0 to a_{75}+24 <= 125+24=149.
Good, that means two of the 152 values must be equal. It really is a number from the first list equalling one from the second because no two in the first (and consequently no two from the second) are equal.