Problem 56: Brazil MO 2013, Day 1, Problem 2

Posts: 312
Joined: Mar 10, 2015

by henderson, Dec 16, 2016, 3:48 PM

${\color{red}\bf{Problem \ 56}}$ Arnaldo and Bernaldo play the following game: given a fixed finite set of positive integers $A$ known by both players, Arnaldo picks a number $a \in A$ but doesn't tell it to anyone. Bernaldo thens pick an arbitrary positive integer $b$ (not necessarily in $A$ ). Then Arnaldo tells the number of divisors of $ab$ . Show that Bernaldo can choose $b$ in a way that he can find out the number $a$ chosen by Arnaldo.
(Brazil MO 2013)
${\color{red}\bf{Solution}}$ Let us say the primes that divide at least one element from $A$ are $p_0,p_1,\ldots,p_k$ . An element $a\in A$ can be represented then as $a=\prod_{j=0}^k p_j^{\alpha_j}$ , with $\alpha_j \geq 0$ . When $b=\prod_{j=0}^k p_j^{\beta_j}$ , the number of divisors of $ab$ is $\tau(ab) = \prod_{j=0}^k (1+ \alpha_j + \beta_j)$ . Let us plug in $\beta_j = x^{2^j}$ ; then $P(x) = \prod_{j=0}^k (1+\alpha_j + x^{2^j})$ is a polynomial in $x$ of degree $2^{k+1} - 1$ , where the coefficient of $x^{2^{k+1} - 2^j - 1}$ is precisely $1+\alpha_j$ . In fact, if we take $n > \prod_{j=0}^k (1+\alpha_j)$ , then $P(n)$ is the writing in basis $n$ of some (huge) integer, and all "digits" can be determined, namely also the values $\alpha_j$ . So all is left to do is to take $n > \prod_{j=0}^k (1+a_j)$ , where $a_j = \max_{A} \alpha_j$ , and $\beta_j = n^{2^j}$ .