Syzygy

Friday, November 19, 2010

CHMMC Tiebreaker 1

Since they've put up the problems for the Fall 2010 competition, I figure it should be ok to discuss them publicly here.

AFAIK, Henry Maltby was the only one (of 12 students) to solve Tiebreaker 1 correctly in the allotted time (10 minutes). I've reproduced the problem below:

The numbers \(25\) and \(76\) have the property that when squared in base \(10\), their squares also end in the same two digits. A positive integer is called amazing if it has at most \(3\) digits when expressed in base \(21\) and also has the property that its square expressed in base \(21\) ends in the same \(3\) digits. (For this problem, the last three digits of a one-digit number \(b\) are \(00b\), and the last three digits of a two-digit number \(ab\) are \(0ab\).) Compute the sum of all amazing numbers. Express your answer in base \(21\).

One straightforward way to solve the problem is to find all the amazing numbers (in base \(21\)): Let the number be \(xyz\). Then \(xyz^2 = \left(x \cdot 441 + y \cdot 21 + z\right)^2\). We only need to consider the last three digits of this result, which is given by \((2 \cdot x \cdot z + y^2) \cdot 441 + 2 \cdot y \cdot z \cdot 21 + z^2\). This gives us the following equations:
\[\begin{align}
z^2 & \equiv z \, (\bmod{21}) \\
2 \cdot y \cdot z + \left\lfloor\frac{z^2}{21}\right\rfloor & \equiv y \, (\bmod{21}) \\
2 \cdot x \cdot z + y^2 + \left\lfloor\frac{2 \cdot y \cdot z + \left\lfloor\frac{z^2}{21}\right\rfloor}{21}\right\rfloor & \equiv x \, (\bmod{21})
\end{align}\]
We find that there are 4 solutions to the first equation: \(z = 0, 1, 7, 15\) with the corresponding \(\left\lfloor\frac{z^2}{21}\right\rfloor = 0, 1, 2, 10\). Solving for \(x\) and \(y\) yields the ordered triplets \((x, y, z) = (0, 0, 0), (0, 0, 1), (7, 16, 7), (13, 4, 15)\). Adding these together yields the base \(21\) number \(\boxed{1002_{21}}\).

Of course we can generalize the problem by considering different bases, \(b\), as well as a different number of "digits", \(d\). Define \(A(b, d)\) to be the set of integers with at most \(d\) "digits" in its base \(b\) representation that, when squared, has the same last \(d\) "digits". Then define \(S(b, d)\) to be the sum of all the elements in \(A(b, d)\). The above problem is the special case, \(S(21, 3)\).

First, we note that having the same last \(d\) "digits" in its base \(b\) representation is equivalent to having the same residue \(\bmod{b^d}\). So \(A(b, d)\) is the set of all solutions for \(x^2 \equiv x \, (\bmod{b^d})\) where \(x < b^d\). Simplifying, we get \(x(x-1) \equiv 0 \, (\bmod{b^d})\).

Representing the prime factorization of \(b\) as \(b = p_1^{\alpha_1} p_2^{\alpha_2} ... p_k^{\alpha_k}\), this yields the following system of equations:
\[\begin{align}
x(x-1) & \equiv 0 \, (\bmod{p_1^{d \alpha_1 }}) \\
x(x-1) & \equiv 0 \, (\bmod{p_2^{d \alpha_2 }}) \\
\vdots \\
x(x-1) & \equiv 0 \, (\bmod{p_k^{d \alpha_k }})
\end{align}\]
For each equation, \(x\) must be either \(0\) or \(1\) \(\bmod{p_i^{d \alpha_i }}\). The Chinese Remainder Theorem tells us that each binary ordered \(k\)-tuplet (the \(i\)th bit being the solution to the \(i\)th equation above) corresponds to a unique residue (or value of \(x\)) \(\bmod{b^d}\).

To find \(S(b, d)\), we observe that each ordered \(k\)-tuplet (corresponding to a solution, \(x\)) has a binary "inverse" (corresponding to a different solution, \(x^\star\)). The \(2^k\) ordered \(k\)-tuplets divide up perfectly into these pairs. Furthermore, we note that \(x + x^\star \equiv 1 \, (\bmod{p_i^{d \alpha_i }}) \, \forall \, i\) which means that \(x + x^\star \equiv 1 \, (\bmod{b^d})\). Because \(0 \le x, x^\star \le b^d-1\), \(x + x^\star\) is either \(1\) or \(1 + b^d\).

However, \(x + x^\star = 1\) only for one \((x, x^\star)\) pair: \((0, 1)\). Therefore all other \((x, x^\star)\) pairs must sum up to \(1 + b^d\). Then \(S(b, d) = \boxed{(2^{k-1}-1)(1 + b^d) + 1}\). For the case where \(d = 3\) and \(k = 2\) such as when \(b = 21\), the answer will be \(\boxed{1002_b}\) as above.

Labels:

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home