\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Brazil 2013/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 57}
\maketitle
\section*{Problem}
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 then picks 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.
\section*{Video}
\href{https://www.youtube.com/watch?v=TqUFlbW8cgE&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/TqUFlbW8cgE}}
\newpage
\section*{Solution}
Let $p_0$, $p_1$, $p_2$, \dots, $p_k$ be the set of primes that appear anywhere in $A$.
Define a huge integer $N$, such that
\[ N > \prod_i \max_{a \in A} \nu_{p_i}(a) \]
for example (but anything big enough will do).
Then, we have Bernaldo select
\[ b = p_0^{N-1} p_1^{N^2-1} p_2^{N^4-1} p_3^{N^8-1} \dots
p_k^{N^{2^k}-1}. \]
Then, if Arnaldo had picked $a = p_0^{e_0} \dots p_k^{e_k}$, we would have
\[ d(ab) = (N+e_0)(N^2+e_1)(N^4+e_2)(N^8+e_3) \dots (N^{2^k}+e_k). \]
If we view this number in base $N$,
then there is no re-grouping, because $N$ is so large.
Then the $N^{2^{k+1}-1 - 2^i}$ digit would give $e_i$, so Bernaldo wins.
\begin{remark*}
In general, Bernaldo can read \emph{any}
product from the digits:
for example the $N^{5}$'s place would give $e_1 e_3 e_4 e_5 \dots e_k$,
or the $N^{13}$ place would give $e_1 e_4 e_5 \dots e_k$.
So only a few digits are necessary.
\end{remark*}
\end{document}