Can you find \(11\) distinct whole numbers whose last digits are all different from each other?
The Chinese remainder theorem is a fundamental result in number theory that allows one to decompose congruence problems to into simpler ones. The theorem says the following.
Suppose that \(m_1,m_2\) are coprime (i.e: they have no prime factors in common) natural numbers and \(a_1,a_2\) are integers. Then there is a unique integer \(x\) in the range \(0\leq x \leq m_1m_2-1\) such that \[x \equiv a_1 \pmod{m_1} \quad \text{ and } \quad x \equiv a_2 \pmod{m_2},\] where the notation \(x\equiv y \pmod{z}\) means that \(x-y=kz\) for some integer \(k\). Prove the Chinese remainder theorem using the pigeonhole principle.
We have ten positive integers \(x_1,\dots,x_{10}\) such that \(10\leq x_i\leq 99\) for \(1\leq i\leq 10\). Prove that there are two disjoint subsets of \(x_1,\dots,x_{10}\) with equal sums of their elements.
Look back at Problem 3. You will now prove that actually we can do better! Show that given \(5\) distinct whole numbers - not necessarily consecutive - we can also find three of them such that their sum is divisible by \(3\).