Problems

In the Land of Linguists live \(m\) people, who have opportunity to speak \(n\) languages. Each person knows exactly three languages, and the sets of known languages may be different for different people. It is known that \(k\) is the maximum number of people, any two of whom can talk without interpreters. It turned out that \(11n \leq k \leq m/2\). Prove that then there are at least \(mn\) pairs of people in the country who will not be able to talk without interpreters.

There are two piles of rocks, \(10\) rocks in each pile. Fred and George play a game, taking the rocks away. They are allowed to take any number of rocks only from one pile per turn. The one who has nothing to take loses. If Fred starts, who has the winning strategy?

A group of \(15\) elves decided to pay a visit to their relatives in a distant village. They have a horse carriage that fits only \(5\) elves. In how many ways can they assemble the ambassador team, if at least one person in the team needs to be able to operate the carriage, and only \(5\) elves in the group can do that?

There are \(5\) pirates and they want to share \(8\) identical gold coins. In how many ways can they do it if each pirate has to get at least one coin?

We want to wrap \(12\) Christmas presents in different coloured paper. We have \(6\) different patterns of paper and we want to use each one exactly twice. In how many ways can we do this?

Mr Roberts wants to place his little stone sculptures of vegetables on the different shelves around the house. He has \(17\) sculptures in total and three shelves that can fit \(7\), \(8\) and \(2\) sculptures respectively. In how many ways can he do this?
The order of sculptures on the shelf does not matter.

Find the largest possible number of bishops that can be placed on the \(8 \times 8\) chessboard so that no two bishops threaten each other.

Theorem: All people have the same eye color.

"Proof" by induction: This is clearly true for one person.

Now, assume we have a finite set of people, denote them as \(a_1,\, a_2,\, ...,\,a_n\), and the inductive hypothesis is true for all smaller sets. Then if we leave aside the person \(a_1\), everyone else \(a_2,\, a_3,\,...,\,a_n\) has the same color of eyes and if we leave aside \(a_n\), then all \(a_1,\, a_2,\,a_3,...,\,a_{n-1}\) also have the same color of eyes. Thus any \(n\) people have the same color of eyes.
Find a mistake in this "proof".

Theorem: If we mark \(n\) points on a circle and connect each point to every other point by a straight line, the lines divide the interior of the circle is into is \(2n-1\) regions.
"Proof": First, let’s have a look at the smallest natural numbers.

• When \(n=1\) there is one region (the whole disc).

• When \(n=2\) there are two regions (two half-discs).

• When \(n=3\) there are \(4\) regions (three lune-like regions and one triangle in the middle).

• When \(n=4\) there are \(8\) regions, and if you’re still not convinced then try \(n=5\) and you’ll find \(16\) regions if you count carefully.

Our proof in general will be by induction on \(n\). Assuming the theorem is true for \(n\) points, consider a circle with \(n+1\) points on it. Connecting \(n\) of them together in pairs produces \(2n-1\) regions in the disc, and then connecting the remaining point to all the others will divide the previous regions into two parts, thereby giving us \(2\times (2n-1)=2n\) regions.

In how many ways can you read the word TRAIN from the picture below, starting from T and going either down or right at each step?