[Math Lair] Answers to Pigeonhole Principle Problems

Math Lair Home > Puzzles & Problems > Answers to Pigeonhole Principle Problems

Here are the answers for the pigeonhole principle problems page.

  1. We can group the five selected numbers into three categories based on the remainder they give when divided by 3. All numbers will have a remainder of either 0, 1, or 2 when divided by 3. Two possibilities exist:
    1. Three of the numbers have the same remainder when divided by 3. In this case, the sum of these three numbers will be a multiple of 3.
    2. No three numbers have the same remainder when divided by 3. In this case, there will need to be at least one number with a remainder of 0, one number with a remainder of 1, and one number with a remainder of 2. The sum of these three numbers will be divisible by 3.
  2. [image of unit square divided into four partsDivide the unit square into four smaller squares as shown. Because there are five points and only four subsquares, at least two points will fall in or on the border of the same square. Because the length of the diagonal of the smaller square is
    1
    root 2
    , the distance between at least one set of two points must be no greater than that distance.
  3. Consider each of the columns that contain three squares. For three squares, there are eight different permutations of black and white. If any of the eight permutations are repeated, a square is formed. So, seven different permutations must be used. This means that one of them must be a column containing either all black or all white. These columns will form a square with three other permutations (the three that have two squares the same colour), at least one of which must be present, so a square must be formed.
  4. We can group the integers in pairs that sum to 104, as follows:
    Group 1
    1
    Group 2
    4, 100
    Group 3
    7, 97
    ...
    Group 17
    49, 55
    Group 18
    52
    When selecting 20 distinct integers from the given arithmetic progression, at least two must be in the same group. However, if two integers from the same group are selected, they must sum to 104, and the assertion is proved.
  5. Say that there are n guests at the party. Each of them must know a number of guests between 0 and n − 1. There are two possibilities:
  6. Consider the decimal portions of X, 2X, ..., (n − 1)X. Each must, of course, fall somewhere between .000... and .999... Divide the range between 0 and 1 into n equal partitions, the first being between 0 and 1/n, the second being between 1/n and 2/n, ..., the nth being between (n − 1)/n and 1. If the decimal portions of aX and bX fall in the same partition, then the decimal part of |ab|X must differ from an integer by no more than the size of the partion, 1/n. Otherwise, all of the partitions must contain one of the numbers, including the partition ranging between 0 and 1/n, which completes the proof.
  7. You can also look at this question geometrically. Geometrically, the question boils down to drawing all sides and diagonals of a hexagon in two colours (say, red and green) such that there is no triangle with three sides all the same colour. Looking at the problem this way: Therefore, in any group of six people there are either three mutual acquaintances or three mutual strangers.
  8. Consider the n numbers between n + 1 and 2n. It is possible to select all of these and not have any member of the set divide another member of the set. However, we need to find an additional number. Consider the upper half of the remaining numbers (from n / 2 + 1, rounded down, to n). If we select one of these numbers, we will not be able to select its double, which will appear between n + 1 and 2n. Therefore, there are still only n possible numbers to select. Now consider the upper half of the remaining numbers. If any of these are selected, we will not be able to select its double. We can repeat the process until we reach the number 1. Therefore, given a set of n + 1 integers between 1 and 2n, show that at least one member of the set must divide another member of the set.