In the test I claimed that if we had a collection of $x_1, $ $b-1$ coins, $x_2,$ $b^2-2$ coins, $x_3,$ $b^3-1$ coins $\cdots x_m, b^m-1$ then the total number of numbers which can be formed is $\prod_{i=1}^{m}x_i$. The proof is not hard noting that if a number is formed then it must be of the form $k-S_b(k)$ where $b | k$ and $S_b(k)$ denotes sum of integers in base $b$.So by question we have a set of $x_i$ such that $\prod x_i=n^2+1$ for some particular $n$ in this whole earth and $x_i \leq b-1$ Then proceeded to die for the rest of the test.

I got that $b - 1 = x^2 + y^2$ for some $x, y$ :skull: nobody i know has solved this problem so far

It's seems like base system idk

It's been 6 long years since one of my problems appeared in INMO Like the above commenters have observed, this is indeed a statement about numbers in base $b$. Anu can pay exactly $x$ rupees by using some collection of her notes iff $x=y-s_b(y)$ for some positive integer $y$, where $s_b$ denotes sum of digits in base $b$. Further, for a given $x$, there are only finitely many $y$ satisfying $x=y-s_b(y)$; indeed, as $y \to \infty$ the RHS also goes to $\infty$, so the set of solutions in $y$ is bounded and hence finite. Thus we have an equivalent statement (in fact this is the statement that I had originally proposed): Reformulation: Let $b \geq 2$ be a positive integer. Let $s_b(m)$ denote the sum of digits of $m$ in base $b$. Suppose there exists a positive integer $n_0$ such that $n_0-s_b(n_0)-1$ is a perfect square. Prove that there are infinitely many positive integers $n$ such that $n-s_b(n)-1$ is a perfect square. We will now work with the restatement. The proof is entirely constructive. For simplicity, we will separately deal with the cases when $b=2$ and $b>2$. Case I: $b=2:$ For any integer $k \geq 2$, take $n=2^{2k}+2^{k+1}+4+2$. Clearly $s_2(n)=4$, so \[n-s_2(n)-1=2^{2k}+2^{k+1}+1=(2^k+1)^2\]is a perfect square. Alternatively, for any integer $k\ge 3$, we can take $n=2^{2k}+2^{k+2}+8$. Clearly, $s_2(n)=3$, so \[n-s_2(n)-1=2^{2k}+2^{k+2}+4=(2^k+2)^2\]is a perfect square. Case 2: $b>2:$ Suppose for some integers $n_0>0$ and $x\geqslant 0$, we have $n_0-s_b(n_0)-1=x^2$. There are two different methods of approach. The first one is my original solution, and the second one was found by an anonymous reviewer. Solution 1: Observe that \[b-1 \mid n_0-s_b(n_0) = x^2+1.\]This means $-1$ is a quadratic residue modulo $b-1$, and that is all we'll use. Let $r$ be a residue modulo $b-1$ satisfying $r^2+1 \equiv 0 \pmod{b-1}$; so $0 \leq r \leq b-2$. Since $b \geq 3$, we must have $r>0$. Then, by replacing $r$ by $b-1-r$ if needed, we can assume $r \leq \frac{b-1}{2}$. Let $$a=\frac{r^2+1}{b-1}<\frac{(b-1)^2+1}{b-1}=b-1+\frac{1}{b-1}<b.$$For any positive integer $k \geq 2$, consider $n=b^{2k}+2(r-1)b^k+ab$. Since $0 \leq a <b$ and $0 \leq 2(r-1) <b$, we have $s_b(n)=1+2(r-1)+a$. Hence $$n-s_b(n)-1=b^{2k}+2(r-1)b^k+ab-a-2r+1-1=b^{2k}+2(r-1)b^k+r^2-2r+1=(b^k+r-1)^2$$is a perfect square. $\blacksquare$ Solution 2: Let $\alpha$ be any integer such that $s_b(\alpha^2)=n_0-s_b(n_0)-1=x^2$. Now, consider $n=\alpha^2\cdot b^{2N}+n_0$ for any $N$ such that $b^{2N}>n_0$. Thus, \[n-s_b(n)-1=\alpha^2\cdot b^{2N}-s_b(\alpha^2)+x^2=(\alpha b^N)^2\]is a perfect square. Now, we just need to show the existence of such an $\alpha$. Firstly, observe that since $b-1|x^2+1$, and $b \geq 3$, we can assume $x>0$. Now, let \[\alpha=\sum_{i=0}^{x-1} b^{2^i}.\]Observe that $$\alpha^2=\sum_{i=1}^x b^{2^i}+\sum_{0\le i<j\le x-1} 2b^{2^i+2^j}.$$Here, any term of the form $k=2^i+2^j$ with $i<j$ uniquely determines $i,j$ and cannot be a power of $2$. Thus, $s_b(\alpha^2)=x^2$ as desired. $\blacksquare$

Nice question but not nice during exam

@supercali Welcome back! Thanks for not giving us a bashy question unlike rmo and ioqm

I spent 45mins on this but got nothing

Supercali wrote: It's been 6 long years since one of my problems appeared in INMO Like the above commenters have observed, this is indeed a statement about numbers in base $b$. Anu can pay exactly $x$ rupees by using some collection of her notes iff $x=y-s_b(y)$ for some positive integer $y$, where $s_b$ denotes sum of digits in base $b$. Further, for a given $x$, there are only finitely many $y$ satisfying $x=y-s_b(y)$; indeed, as $y \to \infty$ the RHS also goes to $\infty$, so the set of solutions in $y$ is bounded and hence finite. Thus we have an equivalent statement (in fact this is the statement that I had originally proposed): Reformulation: Let $b \geq 2$ be a positive integer. Let $s_b(m)$ denote the sum of digits of $m$ in base $b$. Suppose there exists a positive integer $n_0$ such that $n_0-s_b(n_0)-1$ is a perfect square. Prove that there are infinitely many positive integers $n$ such that $n-s_b(n)-1$ is a perfect square. We will now work with the restatement. The proof is entirely constructive. For simplicity, we will separately deal with the cases when $b=2$ and $b>2$. Case I: $b=2:$ For any integer $k \geq 2$, take $n=2^{2k}+2^{k+1}+4+2$. Clearly $s_2(n)=4$, so \[n-s_2(n)-1=2^{2k}+2^{k+1}+1=(2^k+1)^2\]is a perfect square. Alternatively, for any integer $k\ge 3$, we can take $n=2^{2k}+2^{k+2}+8$. Clearly, $s_2(n)=3$, so \[n-s_2(n)-1=2^{2k}+2^{k+2}+4=(2^k+2)^2\]is a perfect square. Case 2: $b>2:$ Suppose for some integers $n_0>0$ and $x\geqslant 0$, we have $n_0-s_b(n_0)-1=x^2$. There are two different methods of approach. The first one is my original solution, and the second one was found by an anonymous reviewer. Solution 1: Observe that \[b-1 \mid n_0-s_b(n_0) = x^2+1.\]This means $-1$ is a quadratic residue modulo $b-1$, and that is all we'll use. Let $r$ be a residue modulo $b-1$ satisfying $r^2+1 \equiv 0 \pmod{b-1}$; so $0 \leq r \leq b-2$. Since $b \geq 3$, we must have $r>0$. Then, by replacing $r$ by $b-1-r$ if needed, we can assume $r \leq \frac{b-1}{2}$. Let $$a=\frac{r^2+1}{b-1}<\frac{(b-1)^2+1}{b-1}=b-1+\frac{1}{b-1}<b.$$For any positive integer $k \geq 2$, consider $n=b^{2k}+2(r-1)b^k+ab$. Since $0 \leq a <b$ and $0 \leq 2(r-1) <b$, we have $s_b(n)=1+2(r-1)+a$. Hence $$n-s_b(n)-1=b^{2k}+2(r-1)b^k+ab-a-2r+1-1=b^{2k}+2(r-1)b^k+r^2-2r+1=(b^k+r-1)^2$$is a perfect square. $\blacksquare$ Solution 2: Let $\alpha$ be any integer such that $s_b(\alpha^2)=n_0-s_b(n_0)-1=x^2$. Now, consider $n=\alpha^2\cdot b^{2N}+n_0$ for any $N$ such that $b^{2N}>n_0$. Thus, \[n-s_b(n)-1=\alpha^2\cdot b^{2N}-s_b(\alpha^2)+x^2=(\alpha b^N)^2\]is a perfect square. Now, we just need to show the existence of such an $\alpha$. Firstly, observe that since $b-1|x^2+1$, and $b \geq 3$, we can assume $x>0$. Now, let \[\alpha=\sum_{i=0}^{x-1} b^{2^i}.\]Observe that $$\alpha^2=\sum_{i=1}^x b^{2^i}+\sum_{0\le i<j\le x-1} 2b^{2^i+2^j}.$$Here, any term of the form $k=2^i+2^j$ with $i<j$ uniquely determines $i,j$ and cannot be a power of $2$. Thus, $s_b(\alpha^2)=x^2$ as desired. $\blacksquare$ indeed ,splendid solution!

Atmadeep wrote:

This solution fails to deal with the case when $b=2$ and this construction is indeed the first solution posted by Supercali.

This problem is quite tractable (and troll) despite appearing unapproachable during contest.

Case 1. $b=2$. For all $k \geq 2$, we see $2^k + 1$ is payable: \[\left(2^k + 1\right)^2 + 1 = 2^{2k} + 2^{k+1} + 2 = \left(2^{2k}-1\right) + \left(2^{k+1}-1\right) + \left(2^2-1\right) + \left(2^1-1\right) \]Case 2. $b>2$. Since $-1$ is a QR mod $b-1$, there exists $0 < a < \frac{b-1}{2}$ such that $b-1 \mid a^2+1$. For all $k \geq 2$, $b^k + a - 1$ is payable: \[ \left(b^k + a - 1\right)^2 + 1 = b^{2k} \;+\; a^2 \;+\; 2(b^k - 1)(a - 1) = \left(b^{2k} - 1\right) \;+\; (2a - 2)(b^k - 1) \;+\; (a^2 + 1) \](Note that $a^2+1$ can be paid for using at most $b-1$ copies of $b-1$.)

I HAD ONE CLAIM: FOR SHOWING THAT INFINITE PAYABLE NUMBERS EXISTS. CLAIM: One can find at least one $y$ ,such that $b|y$ $\boxed{b^{k-1} \le y< b^k}$, such that .$(y)_b-s_b(y)-1=x^2$ for some $x,b \in N$ Now, the proof of. this claim could be proved using the general form of the square :($b^{2k}+2(r-1)(b^k)+ab$) by changing the values $k$ ,but I want someone to prove it using some other method, can somebody help me with it.