Competition problem — Number theory

Library / /71 of 86

Number theory Difficulty 6.9 National olympiad Prove it Estonia

Priit's collection consists of $1111$ stamps which are all distributed into envelopes in such a way that every envelope contains more than one stamp, all envelopes contain the same number of stamps, and each envelope contains only stamps from one country. It is known that more than $40\%$ of stamps in this collection are from Estonia, more than $30\%$ of stamps in the collection are from Latvia and more than $20\%$ of stamps in the collection are from Lithuania. Find the largest possible number of envelopes containing Estonian stamps and the largest possible number of envelopes containing Lithuanian stamps.

Solution

*Answer:* $41$ and $29$ .

As $1111 = 11 \cdot 101$ where the factors are prime, we have four cases:
* $1$ envelope containing $1111$ stamps;
* $1111$ envelopes, each containing $1$ stamp;
* $11$ envelopes, each containing $101$ stamps;
* $101$ envelopes, each containing $11$ stamps.

The first case is impossible since Priit has stamps of at least $3$ countries and one envelope can contain only stamps of one country. The second case is excluded by the conditions of the problem explicitly. If there were $11$ envelopes then at least $5$ envelopes would have to contain Estonian stamps, at least $4$ envelopes would have to contain Latvian stamps and at least $3$ envelopes would have to contain Lithuanian stamps. This would require at least $12$ envelopes in total which contradicts the assumption. Hence there must be $101$ envelopes. Then at least $41$ envelopes have to contain Estonian stamps, at least $31$ envelopes have to contain Latvian stamps and at least $21$ envelopes have to contain Lithuanian stamps. So the number of envelopes containing Lithuanian stamps cannot exceed $29$ . It is indeed possible to have $41$ envelopes containing Estonian stamps and $29$ envelopes containing Lithuanian stamps if $31$ envelopes contain Latvian stamps and there are no stamps from other countries.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.