Strategy to Solve a Number Guessing Problem from Belarus Open Math Olympiad 2012

Question

I've come across a problem from the Belarus Open Math Olympiad that I'm finding particularly challenging, as my background in mathematics is not very strong. I'm hoping someone here can help me understand how to approach it

Problem Statement:

"Vasya conceived a two-digit number a, and Petya is trying to guess it. To do this, he tells Vasya a natural number k, and Vasya tells Petya the sum of the digits of the number ka. What is the smallest number of questions that Petya has to ask so that he can certainly be able to determine Vasya’s number?"

My feeling is the answer might be 1

Answer 1

Hints towards a solution. If you're stuck, explain what you've tried and why you can't push through:

Let $s(n)$ be digit sum of $n$.

1. Relax the problem. Ignore the search of "smallest number" for now. Simply show that there exists positive integers $d$, $k_1, k_2, \ldots , k_d$ such that $f(n) = ( s(k_1 n), s(k_2 n) , \ldots s(k_d n) ) $ is an injection from $\{10, 11, \ldots, 99\} \rightarrow \mathbb{N}^d$.
   • Arguably, the crux of the question is to show that for $ a \neq 10^m b$, there exists a $k$ such that $s(ka) \neq s(kb)$.
     • We first take $ k = 1$, and so may assume that $ s(a) = s(b)$, which restricts us to at most 9 values. How can we proceed?
     • If you're stuck, think about how we can differentiate $ \{ 11, 20 \}$ and $ \{ 13, 22, 31 \}$. What must happen in order for their digit sums to differ?
   • Note: The question wants to know what the best possible $d$ is, but for now we simply find any $d$ that works.
   • Show that we can set $d \leq 90$ through an inductive argument. Can you come up with a better, simple bound?
2. Inheriting from above, if for all $n < 100$, $k_i n < 10^r$ and $s(k_in) < 10^s$, then there exists a $k$ such that $s(kn) = \sum s(k_in) 10^{si } $.
3. This allows us to ask for $s(kn)$, and read off the individual $s(k_i n)$, and hence determine $n$.

• Hence, 1 question is sufficient.

---

Investigating the case of $ s(a) = 9 $, which is unique from the rest because they are close multiples of each other.
For small $k$, most of the digit-sums will be 9 or 18.
In the table below, I highlighted the times when the digit sum is 18. In order to distinguish between $a_1 = 18$ and $a_2 = 90$, the smallest $k$ is 16.

Answer 2

I think you are correct Let the two digit number be 10x + y So, 10x + y = a -> equation 1 Since it's a two digit number the sum of digit should be between 1 and 18 And it's given that sum of digits is " ka " Therefore, x+y=ka if we take k = 1 x+y=a x = a-y Put x = a-y in equation 1 10(a-y) + y = a 10a - 10y + y = a a = y x = 0 y = 1 Thus our number is 10(0)+1 = 1 If I am wrong please correct me

Answer 3

TOTAL EDIT: I realised there is a spoiler option, so I will use it to hide the full solution and only publicise the hints.

Step 1: how do we even know that there is a predetermined finite set of $N$ queries which is good enough across all possible two-digit examples of $a$?

Hint for Step 1: Are there only a finite number of pairs of distinct two-digit numbers? How to use this fact?

There are only ${90\choose2}=4005$ possible pairs. So, if we can prove that for each pair $(b,c)$ there exists some integer $k_{(b,c)}$ such that the sum of digits of $b\times k_{(b,c)}$ is different from the sum of $c\times k_{(b,c)}$, then by choosing and fixing the values of $k_{(b,c)}$ we only need at most $4005$ different values of $k$ to get all the info we need about $a$. After all, once we have the info for the sum of digits of $a\times k_{(b,c)}$ across all $4005$ options of $(b,c)$, there can't be two different candidates $a'$ and $a''$, since one of the $k_{(b,c)}$ would have separated them.

All that is left for Step 1 is to prove the premise: that for any given pair $(b,c)$ there really does exist some $k_{(b,c)}$ such that the sum of digits of $b\times k_{(b,c)}$ is not equal to that of $c\times k_{(b,c)}$. For ease of notation, assume $b<c$. I will give a proof that works for arbitrarily large examples of $b$ and $c$ such that $\frac{c}{b}$ is not a power of $10$. The technique is to choose $k_{(b,c)}$ judiciously so that $b\times k_{(b,c)}$ or $c\times k_{(b,c)}$ is easy to work with. My method, however, is still very tedious and I don't find the details very exciting.

Case one: $\frac{c}{b}$ is an integer - remember, it's not a power of $10$. Therefore, the sum of digits of $\frac{c}{b}$ is greater than $1$. Now let $\langle c\rangle$ be the number of digits of $c$. Think of the number that is constructed by writing out the number $100\cdots00=10^{\langle c\rangle}$ repeatedly, $M$ times in a row. ($M$ could be any integer. We will decide which integer later.) Denote the constructed number as $X$. Now, recalling that $b<c$, adjust the last $\langle c\rangle$ digits of $X$ i.e. by choosing a number $d<b$ such that $X+d$ is a multiple of $b$. What happens when you compute $\frac{c}{b}\times(X+d)$? Compare: the sum of digits of $X+d$ is at most $M+9\times\langle c\rangle$, whereas the sum of digits of $\frac{c}{b}\times(X+d)$ is at least $M\times\frac{c}{b}$. Notice that we could choose $M$ to be large enough that the sum of digits of $M\times\frac{c}{b}$ is clearly larger.

Case two: $\frac{c}{b}$ is not an integer. I'll leave it as an exercise. My approach would be to look at $\frac{b}{c}<1$ and to construct a number that is a multiple of $c$ but which is almost all $0$'s i.e. not even any repeated $1$'s.

Step 2: Given that $N$ fixed-in-advance queries (as per Step 1) is enough across all possible two-digit inputs $a$, how can we artificially create a number $k$ such that $ak$ alone has all the info needed which the $N$ queries would have given us?

Hint for Step 2: The building blocks of the number $k$ would be similar to a number of the form $100\cdots00100\cdots00100\cdots00\cdots$.

Recall from the solution to Step 1 that we have at most $4005$ different integers $k_1,\ldots,k_{4005}$ to begin with. Let us denote by $K$ the maximum of these $k_i$. Let's say we wanted an integer $k'$ such that, no matter which two-digit input $a$ we start with, from the sum of digits of $ak'$ alone we know what the sum of digits of $ak_1$ is as well as what the sum of digits of $ak_2$ is. My method, though not impossibly tricky, is still tedious and I don't find the details very exciting. For ease of notation assume $k_1<k_2$.

Again let $\langle c\rangle$ denote the number of digits of $c$. Think about the number that is made by writing $k_1\times10^{\langle 99K\rangle}$ repeatedly, exactly $10^{\langle 99K\rangle}$ times in a row. Add $k_2$ to that constructed number. Call the result $Y$. Notice that the sum of digits of $aY$ is equal to $\beta+\phi$, where $\beta$ is the sum of digits of $ak_2$ and where $\phi$ is $10^{\langle 99K\rangle}$ times the sum of digits of $ak_1$. I used $99K$ because this is the maximum possible value of $ak$, and the choice of $10^{\langle 99K\rangle}$ leaves enough room for the instances of $ak_1$ to be separated in the written-out form of $aY$. Notice that once you do get the value of $\beta+\phi$, you can "read out" the sum of digits of $ak_2$ separately from that of $ak_1$, because you know in advance that the info relevant to $k_1$ is tucked away $\langle 99K\rangle+1$ digits to the left.

This procedure can easily be extended.