A four-digit positive integer is called $virtual$ if it has the form $\overline{abab}$, where $a$ and $b$ are digits and $a \neq 0$. Find all virtual numbers of the form $n^2+1$, for some positive integer $n$.

Solution

Answer: $8,282$.

The problem states that

$$ \overline{abab} = n^2+1 $$

Notice that

$$\overline{abab} = 100 \cdot \overline{ab} + \overline{ab} = 101 \cdot \overline{ab}$$

and since every virtual number is a four-digit integer, then

$$1,000 \leq n^2+1 \leq 9,999$$

and therefore $32 \leq n \leq 99$.

The initial equality becomes

$$ 101 \cdot \overline{ab} = n^2+1 $$

$$ 101 \cdot \overline{ab} -101 = n^2+1 -101 $$

$$ 101 \cdot \left( \overline{ab} -1 \right) = (n-10)(n+10) $$

Since $101$ is a prime, then $101 | (n-10)$ or $101 | (n+10)$.

If $101 | (n-10)$, then $(n-10) \in [22,89]$ and is not divisible by $101$. Contradiction.

If $101 | (n+10)$, then $(n+10) \in [42,109]$, where the only multiple of $101$ is $101$. Therefore $n+10=101$ and $n=91$. This implies that $ \overline{ab} = 82 $ and the only virtual number is $8,282$.

Problem 2

Suppose you have identical coins distributed in several piles with one or more coins in each pile. An action consists of taking two piles, which have an even total of coins among them, and redistribute their coins in two piles so that they end up with the same number of coins. A distribution is $levelable$ if it is possible by means of $0$ or more operations to end up with all the piles having the same number of coins. Determine all positive integers $n$, such that for all positive integers $k$, any distribution of $kn$ coins in $n$ piles is levelable.

 

Solution

Answer: $n=2^L$, where $L \in \mathbb{Z}$, $L \geq 0$.

First, notice that the operation is applied only to the piles with the number of stones of the same parity.

Let the values in the piles be $x_1$, $x_2$, … , $x_n$. Let us consider the quantity $S$ defined as

$$ S = x_ 1^2+x_ 2^2+ … + x_ n^2 $$

Notice that under the applied operation the quantity $S$ is not increasing. Indeed, if the operation is applied to the piles with the number of stones $a$ and $b$, then

$$ a^2 + b^2 \geq \left(\frac{a+b}{2} \right)^2 +\left(\frac{a+b}{2} \right)^2 $$

and the equality holds only for the case $a=b$. Since $S \geq 0$, then this process is finite if and only if at every step there is a pair of piles with different amounts of stones of the same parity. The process stalls if all the piles with the number of stones of the same parity have an equal number of stones, i.e. if all odd $x_i$ are equal and all even $x_j$ are equal.

Let us show that $n$ being any power of $2$ satisfies the conditions of the problem. Let us assume that the all piles with the number of stones of the same parity have equal number of stones. Let $n=2^{L}$ and let $m$ and $2^{L}-m$ be the number of piles with odd number of stones $2b+1$ and even number of stones $2a$ respectively. Notice that $m \leq 2^{L}$. Therefore we have

$$ (2b+1) \cdot m + (2a) \cdot \left( 2^{L} – m \right) = 2^{L} \cdot k $$

$$ (2b+1 -2a) \cdot m = 2^{L} \cdot ( k +2am) $$

Since $2b+1-2a$ is odd, then $2^{L} | m $ and therefore $m=2^{L}$. This means that all numbers are equal and the distribution is levelable.

Let $n=2^{L} \cdot q$, where $q$ is an odd integer greater than $1$. Let us put $k=2$ and the total number of stones in all piles thus is $2q \cdot 2^{L}$. Let us consider $2^{L} \cdot q – 2^{L}$ piles with only $1$ stone and $2^{L}$ piles with $q+1$ stones: $1$, $1$, … , $1$, $q+1$, $q+1$, … , $q+1$. Therefore we have

$$ 1 \cdot \left( 2^{L} \cdot q – 2^{L} \right) + (q+1) \cdot 2^{L} = 2q \cdot 2^{L} $$

Since $q+1$ is even, it is now obvious that we cannot only perform the operations on the piles with $1$ stone or on the piles with $q+1$ stone, which does not change the configuration. Therefore this distribution is not levelable.

Problem 3

Find all functions $f : \mathbb{Z} \to \mathbb{Z}$, satisfying the following property: if $a$, $b$, $c$ are integers, such that $a+b+c=0$, then

$$ f(a)+f(b)+f(c) = a^2+b^2+c^2 $$

Solution

Answer: $f(n)=n^2+pn$, where $p \in \mathbb{Z}$.

Let us start by substituting $a=b=c=0$:

$$ f(0)+f(0)+f(0) = 0^2+0^2+0^2 $$

$$ 3f(0)= 0 $$

$$ f(0)= 0 $$

Now let us substitute $a=x$, $b=-x$ and $c=0$:

$$ f(x)+f(-x)+f(0) = x^2+(-x)^2+0^2 $$

$$ f(x)+f(-x) = 2x^2 $$

In this formula let us put $x=a+b$:

$$ f(a+b)+f(-a-b) = 2(a+b)^2 $$

$$ f(-a-b) = 2(a+b)^2 – f(a+b)$$

Let us now substitute $c=-a-b$:

$$ f(a)+f(b)+f(-a-b) = a^2+b^2+(-a-b)^2 $$

Taking into account the previous equality we have

$$ f(a)+f(b)+2(a+b)^2 – f(a+b) = a^2+b^2+(a+b)^2 $$

which can be simplified to

$$ f(a+b) = f(a)+f(b)+2ab $$

Let us put $b=1$ and $a=n$ in the last equality:

$$ f(n+1) = f(n)+f(1)+2n $$

Let us substitute $f(1)$ for $p+1$:

$$ f(n+1) = f(n)+2n + p +1 $$

This equality holds for all $n \in \mathbb{Z}$. Now we will treat positive and negative $n$ differently. For positive $n$ we will prove by induction that $f(n)=n^2+pn$ for all $n \in \mathbb{N}$.

The basis of induction is true for $n=0$: $f(0)=(0)^2+p(0) = 0$.

For the inductive step let us assume that $f(k)=k^2+pk$ for some $k \in \mathbb{N}$. Therefore

$$ f(k+1) = f(k)+2k + p +1 = k^2+pk + 2k + p +1 = (k+1)^2 + p (k+1) $$

Therefore $f(n)=n^2+pn$ for all $n \in \mathbb{N}$.

For negative $n$ we consider the equality:

$$ f(x)+f(-x) = 2x^2 $$

and put $x=n$:

$$ f(n)+f(-n) = 2n^2 $$

$$ n^2+pn+f(-n) = 2n^2 $$

$$ f(-n) = n^2 -pn $$

$$ f(-n) = (-n)^2 + p(-n) $$

Therefore for all $n \in \mathbb{Z}$ we have $f(n)=n^2+pn$

Go to Day 2

---