For a given positive integer number $n$ find all subsets $\{r_0,r_1,\cdots,r_n\}\subset \mathbb{N}$ such that $$ n^n+n^{n-1}+\cdots+1 | n^{r_n}+\cdots+ n^{r_0}. $$ Proposed by Shayan Tayefeh
Problem
Source: Iran 2024 3rd round P4
Tags: number theory
25.08.2024 17:32
The answer is all subsets $\{r_0,r_1,\dots,r_n\}$ that form a distinct residue set modulo $n+1$ except when $n=1$ when all pairs work. Assume $n>1$. It is clear that $\{r_0,r_1,\dots, r_n\}=\{0,1,2,\dots, n\}$ works and increasing any element by $n+1$ increases the RHS by a multiple of $n^{n+1}-1$ which is a multiple of the LHS, thus all said subsets work. Using the same idea as above we can assume all $r_i$ lie in $[0,n]$. Notice that the ratio between the LHS and the RHS is at most $n-1$ thus the RHS must be equal to one of the following $$11\dots 1_n, 22\dots 2_n, \dots, (n-1)(n-1)\dots (n-1)_n$$where each number has $n+1$ digits. However when written in base $n$ the sum of the digits of the RHS is at most $n+1$ thus we must have the RHS equal to $11\dots 1_n$ leading to the above conclusion.
26.08.2024 18:51
Well, we can prove a very related statement that really helps to solve this problem. Lemma. Let $a$ and $n$ be given positive integers and $A=a^n+\cdots+a+1$ divides $a^{\alpha_1}+\cdots+a^{\alpha_n}+1$ for some positive integers $\alpha_1, \ldots, \alpha_n$, then $\alpha_i$ are indeed the complete residue systmem modulo $n+1$. Proof. Suppose that $A$ divides and let $r_i$ be the remainder of $\alpha_i$ upon division by $n+1$. It is easy to verify that $A$ divides $C=a^{r_1}+\cdots+a^{r_n}+1=c_n a^n+\cdots+c_1 a+c_0$, where $c_0, \ldots, c_n$ are nonnegative integers with the sum $n+1$. Of all numbers of the form $B=b_n a^n+\cdots+b_1 a+b_0$ that are divisible by $A\left(b_i \in \mathbb{N}_0\right)$, consider any one with the minimum possible value of the sum $b_0+\cdots+b_n$. Each $b_i$ is less than $a$, otherwise substituting $\left(b_i, b_{i+1}\right)$ with $\left(b_i-a, b_{i+1}+1\right)$ yields a representation of $B$ with a smaller sum $b_0+\cdots+b_n$ (where $b_{n+1}=b_0$ ). Therefore $B<a \cdot A$, which implies $B=k A$ for some $k \in\{1, \ldots, a-1\}$, so $b_i=k$ by uniqueness of base $a$ representation. It follows that the minimum possible value of $b_0+\cdots+b_n$ equals $n+1$ and is attained only when $b_i=1$ for all $i$. Since $c_0+\cdots+c_n=n+1$, it follows from above that $c_i=1$ for all $i$. Thus $\left\{r_1, \ldots, r_n\right\}=\{1, \ldots, n\}$. This completes our proof.
31.08.2024 00:13
For $n=1$, all subsets satisfy the condition. For $n>1$, one has $ n^{n+1}-1|\sum_{i=0}^{n} (n^{i+1}-n^i)$. Take modulo $n+1$ of right-hand side. Right/Left $<= \frac{(n+1)(n^n-n^{n-1})}{n^{n+1}-1} < 1$. Right-hand side must be $0$ implying that $A = \{r_0, r_1, ..., r_n\} = \{r_0+1, r_1+1, ..., r_n+1\}$. This means $ a \in A \implies a+1 \in A$. Performing this $n$ times gives $A = \{0,1,2,3,...,n\}$ modulo $n+1$.