## 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: