Tuesday, January 01, 2013
Ex 2.15 Age-guessing game
If you want to show that you are a real nerd, here is an age-guessing game you might play at a party. You ask a fellow party-goer to divide his age by each of the numbers 3, 4, and 5, and tell you the remainders. Show how to use this information to determine his age.
== Attempt ==
Since 3, 4, and 5 are relatively prime, based on the Chinese remainder theorem, we know that the map:
  | \[ \begin{aligned} \tau : I_n &\to I_{n_1} \times \dotsb \times I_{n_k} \\ a &\mapsto (a \bmod n_1, \dotsc, a \bmod n_k) \end{aligned} \] |
- \(\{n_i\}_{i=1}^k\) is a pairwise relatively prime family of integers
- \(n := n_1 \dotsm n_k\)
- \(I_m\) denotes {\(0, \dotsc, m-1\)} for each positive integer \(m\), and
- \(a \in \mathbb{Z} \)
In other words, with \(n := 3 \times 4 \times 5 = 60 \) there exists a unique integer \(a'\) in \(I_{60}\) that would match all the remainders of a given age via dividing \(a'\) by each of the numbers 3, 4, and 5. Furthermore, if \(a'\) is a solution, \(a \equiv a' \pmod {60}\), where \(a\) is the final solution.
One way, therefore, is to start by brute forcing \(a'\) by trying out all positive integers less than 60. Once we got that, it should be easy to tell if we need to add an extra 60 to the final solution by simple observation of the subject person. The assumption is no one lives beyond the age of 119 :)