1

When we need to use the Pigeonhole theorem and why we are using the Pigeonhole theorem in this case?

I also have a question below:

Each tile has one letter on it, and a point value in the bottom right hand corner (e.g. "M" is worth 3 points). $$M_3A_1T_1H_4E_1M_3A_1T_1I_1C_3S_1$$

Suppose that the pictured tiles get split between two bags. Which of the following statements follows from the pigeonhole principle?

a)Both bags will contain at least 3 tiles worth 1 point.

b)One bag will contain at least 4 tiles worth 1 point, the other bag will have at most 3 tiles worth 1 point.

c)One bag will have more points on its tiles than the other bag.

d)Both bags must contain a tile with the letter M on it.

e)Both bags will have the same number of tiles in them.

I am thinking b) might be the answer but I am just guessing based on my logic and nothing about the Pigeonhole theorem. I know d) and e) must be wrong as 2Ms can be put in one bag and there is 11 elements, it is impossible to have the same number of tiles in two bags.

Please correct me if I am wrong

Alan Bish
  • 41
  • 4
  • (b) is indeed the only statement which must be true. The (extended) pigeonhole principle implies the first half of the statement that there must be at least one bag with at least $\left\lceil\frac{7}{2}\right\rceil=4$ tiles worth 1 point in it. The second half of the statement follows from simple algebra, noting that with at least 4 in one bag, and since amount in both bags adds up to seven, there is at most 3 in the other bag. – JMoravitz May 02 '22 at 17:17
  • "Why are we using the pigeonhole principle here?" Because it is a useful tool. Yes, it does basically amount to "there will be at least one bag with the average amount or larger" which may sound obvious... but since in maths we try to be rigorous and precise with how we phrase arguments the pigeonhole principle allows us to explain why that "obvious" statement must be true precisely. – JMoravitz May 02 '22 at 17:20
  • @JMoravitz "The second half of the statement follows from simple algebra, noting that with at least 4 in one bag, and since amount in both bags adds up to seven, there is at most 3 in the other bag" Can you please further explain this part, I got lost in the words. – Alan Bish May 02 '22 at 17:28
  • Letting $a$ be the amount of point 1 tiles in the first bag and $b$ the amount in the second bag... without loss of generality suppose that $b\geq 4$. We know that $a+b=7$ and we know that $b\geq 4$ so we know that $a=7-b\leq 7-4\leq 3$ – JMoravitz May 02 '22 at 17:29
  • I got it now, thank you! – Alan Bish May 03 '22 at 06:08
  • Just want to point out that your "guessing based on my logic" was very likely you making use of the Pigeonhole principle. "Pigeonhole Principle" is nothing more that a label we attach to this line of reasoning to allow us to talk about it without having to explain it with every mention. You just didn't realize your reasoning fits the reasoning pattern of the pigeonhole principle. – Paul Sinclair May 03 '22 at 14:42
  • I also find it somewhat amusing to note that if you used the meta-logic that (a),(c),(d),(e) cannot be correct because it is easy to construct counter examples for all (putting both Ms and the H in one bag, and rest in the other breaks all four of them), and since "none" is not an available option, therefore (b) must be the one that follows from the pigeonhole principle - this meta-logic itself is an application of the pigeonhole principle. – Paul Sinclair May 03 '22 at 15:00
  • @PaulSinclair I am curious can the answer be "One bag will contain at least 6 tiles, the other bag will have at most 5 tiles." ? – Alan Bish May 05 '22 at 08:14

1 Answers1

1

Mostly to clear the unanswered line:

You are correct with b) if we divide 7 letters among 2 bags at least $4=\left\lceil\frac{7}{2}\right\rceil$ are in one bag. The others (no more than 3 as 7-4=3)

e) is wrong because an odd number doesn't divide exactly in 2 by definition.

c) fails because {M,M,A,T,I,S} and {H,A,T,E,C}

Etc.

Roddy MacPhee
  • 859