Problems

Today we will be solving problems using the Pigeonhole Principle. What is it? Simply put, suppose we are asked to put pigeons inside pigeonholes, but we have more pigeons that pigeonholes. No matter how we try to do it, there will be a pigeonhole with at least two pigeons. For example, consider the following picture, where we have \(10\) pigeons but only \(9\) pigeonholes:

No matter how hard we try to arrange the pigeons, it will be impossible to fit at most \(1\) pigeon in each pigeonhole! Here is a way to see why: suppose that in each pigeonhole there was at most \(1\) pigeon. Since we have \(9\) pigeonholes, this means we have at most \(1\times 9=9\) pigeons in total, but this is can’t be true, because we started with \(10\) pigeons!
By pigeonhole we can mean any container, and by pigeon we can mean any object that we want to place inside the containers. This is a simple but very powerful idea, and today we will learn how to use it to solve some difficult problems! Let’s start by seeing a simple example. Can you see what the pigeonholes and the pigeons should be?

Draw how Robinson Crusoe should put pegs and ropes to tie his goat in order for the goat to graze grass in the shape of a parallelogram.

Draw a picture how Robinson used to tie the goat and the wolf in order for the goat to graze the grass in the shape of half a circle.

Draw a picture how Robinson used to tie the goat and the wolf in order for the goat to graze the grass in the shape of a young moon (see the picture below)

Draw a picture how Robinson used to tie the goat and the wolf in order for the goat to graze the grass in the shape of half a ring.

Find all the prime numbers \(p\) such that there exist natural numbers \(x\) and \(y\) for which \(p^x = y^3 + 1\).

Find all natural numbers \(n\) for which there exist integers \(a,b,c\) such that \(a+b+c = 0\) and the number \(a^n + b^n + c^n\) is prime.

The dragon locked six dwarves in the cave and said, "I have seven caps of the seven colors of the rainbow. Tomorrow morning I will blindfold you and put a cap on each of you, and hide one cap. Then I’ll take off the blindfolds, and you can see the caps on the heads of others, but not your own and I won’t let you talk any more. After that, everyone will secretly tell me the color of the hidden cap. If at least three of you guess right, I’ll let you all go. If less than three guess correctly, I’ll eat you all for lunch." How can dwarves agree in advance to act in order to be saved?

Nick has written in some order all the numbers \(1,2,...33\) at the vertices of a regular \(33\)-gon. His little sister Hannah assigned to each side of the \(33\)-gon the number equal to the sum of the numbers at the ends of that side. It turns out that Hannah obtained \(33\) consecutive numbers in certain order. Can you find an arrangement of numbers as written by Nick which lead to this situation?

Alice the fox and Basilio the cat have grown \(20\) counterfeit bills on a money tree and now write seven-digit numbers on them. Each bill has \(7\) empty cells for numbers. Basilio calls out one digit "1" or "2" (he doesn’t know the others), and Alice writes the number into any empty cell of any bill and shows the result to Basilio. When all the cells are filled, Basilio takes as many bills with different numbers as possible (out of several with the same number, he takes only one), and the rest is taken by Alice. What is the largest number of bills Basilio can get, regardless of Alice’s actions?