by showmyiq » Thu May 16, 2013 6:05 am
The puzzle is cracked by Sergey Sokolov via Facebook!
I really liked his approach, I hope you enjoy it too.
We have:
\begin{equation}
a_{n,k} = 1^n + 2^n + \cdots + k^n \\
\text{Let's define such } b_{n,k,m} \text{ that} \\
b_{n,k,m} = m^n + (k-m)^n\\
b_{n,k,m} = m^n + [{n \choose 0}k^nm^0 - {n \choose 1}k^{n-1}m^1 + {n \choose 2}k^{n-2}m^2 ] - \cdots - \\
{n \choose n-2}k^{2}m^{n-2} + {n \choose n-1}k^{1}m^{n-1} - {n \choose n}k^{0}m^{n}] \\
\text{The last element is with sign MINUS because n is an odd number}\\
b_{n,k,m} = m^n + {n \choose 0}k^nm^0 - {n \choose 1}k^{n-1}m^1 + {n \choose 2}k^{n-2}m^2 ] - \cdots - \\
{n \choose n-2}k^{2}m^{n-2} + {n \choose n-1}k^{1}m^{n-1} - m^{n} \\
b_{n,k,m} = {n \choose 0}k^nm^0 - {n \choose 1}k^{n-1}m^1 + {n \choose 2}k^{n-2}m^2 ] - \cdots - \\
{n \choose n-2}k^{2}m^{n-2} + {n \choose n-1}k^{1}m^{n-1} \\
b_{n,k,m} = k*\delta \text{ , for some random natural number } \delta
\end{equation}
As we can see b is dividable by k, no matter the values of n(odd n's),k or m.
Now let’s calculate some b’s for specific m’s.
\begin{equation}
b_{n,k,0} = 0^n + (k-0)^n = 0 + k^n = k^n \\
b_{n,k,1} = 1^n + (k-1)^n \\
b_{n,k,2} = 2^n + (k-2)^n \\
\cdots \\
b_{n,k,m} = m^n + (k-m)^n \\
\text{Therefore we can construct a's with b's} \\
\color{red}{\text{1st case: k is and odd number}} \\
a_{n,k} = b_{n,k,0} + b_{n,k,1} + \cdots + b_{n,k,{\frac{k-1}{2}}} \\
\text{You can see that such representation is adequate and correct}\\
\text{For example if k=11, we will have:} \\
a_{n,11} = b_{n,11,0} + b_{n,11,1} + \cdots + b_{n,11,{\frac{11-1}{2}}}\\
a_{n,11} = b_{n,11,0} + b_{n,11,1} + \cdots + b_{n,11,5}\\
a_{n,11} = 11^n + [1^n + 10^n] + [2^n + 9^n] + [3^n + 8^n] + [4^n + 7^n] + [5^n + 6^n]\\
a_{n,11} = 1^n + \cdots + 11^n \\
\text{So we can conclude that for some natural number }\epsilon,\\
a_{n,k} = b_{n,k,0} + b_{n,k,1} + \cdots + b_{n,k,{\frac{k-1}{2}}} = k*\epsilon \\
\text{Therefore }a_{n,k} \text{ is dividable by } k \text{, for k - odd number}\\
\color{red}{\text{2nd case: k is and even number}} \\
a_{n,k} = b_{n,k,0} + b_{n,k,1} + \cdots + b_{n,k,{\frac{k}{2}}} - (\frac{k}{2})^n \\
\text{You can see that such representation is adequate and correct}\\
\text{For example if k=10, we will have:} \\
a_{n,10} = b_{n,10,0} + b_{n,10,1} + \cdots + b_{n,10,{\frac{10}{2}}} - (\frac{10}{2})^n \\
a_{n,10} = b_{n,10,0} + b_{n,10,1} + \cdots + b_{n,10,5} - 5^n \\
a_{n,10} = 10^n + [1^n + 9^n] + [2^n + 8^n] + [3^n + 7^n] + [4^n + 6^n] + [5^n + 5^n] - 5^n \\
a_{n,10} = 10^n + [1^n + 9^n] + [2^n + 8^n] + [3^n + 7^n] + [4^n + 6^n] + 5^n \\
a_{n,10} = 1^n + \cdots + 10^n \\
\text{So we can conclude that for some natural number }\vartheta,\\
a_{n,k} = b_{n,k,0} + b_{n,k,1} + \cdots + b_{n,k,{\frac{k}{2}}} - (\frac{k}{2})^n = \frac{k}{2}*\vartheta \\
\text{Therefore }a_{n,k} \text{ is dividable by } \frac{k}{2} \text{, for k - even number} \\
\end{equation}
Ok, so far – so good. Now, let’s use another approach to construct a’s from b’s.
\begin{equation}
b_{n,k+1,1} = 1^n + (k+1-1)^n=1^n + k^n\\
b_{n,k+1,2} = 2^n + (k+1-2)^n = 2^n + (k-1)^n\\
\cdots \\
b_{n,k+1,m} = m^n +(k+1-m)^n\\
\color{red}{\text{1st case: k - an odd number}}\\
a_{n,k}=b_{n,k+1,1} + b_{n,k+1,2} + \cdots + b_{n,k+1,\frac{k+1}{2}} - {\frac{k+1}{2}}^n\\
\text{You can again substitute some odd number k to test the equation.}\\
\text{So we can conclude that for some natural number }\zeta,\\
a_{n,k}=b_{n,k+1,1} + b_{n,k+1,2} + \cdots + b_{n,k+1,\frac{k+1}{2}} - {\frac{k+1}{2}}^n = \frac{k+1}{2}*\zeta \\
\text{Therefore } a_{n,k} \text{ is dividable by } \frac{k+1}{2} \text{, for k - odd number} \\
\color{red}{\text{2nd case: k - an even number}}\\
a_{n,k}=b_{n,k+1,1} + b_{n,k+1,2} + \cdots + b_{n,k+1,\frac{k}{2}}\\
\text{You can again substitute some even number k to test the equation.}\\
\text{So we can conclude that for some natural number }\xi,\\
a_{n,k}=b_{n,k+1,1} + b_{n,k+1,2} + \cdots + b_{n,k+1,\frac{k}{2}} = (k+1)*\xi \\
\text{Therefore } a_{n,k} \text{ is dividable by } k+1 \text{, for k - even number} \\
\end{equation}
Let’s now combine the 1st and 2nd cases from first construction of a’s and second constructions of a’s.
\begin{equation}
\text{Therefore }a_{n,k} \text{ is dividable by } k \text{, for k - odd number}\\
\text{Therefore } a_{n,k} \text{ is dividable by } \frac{k+1}{2} \text{, for k - odd number} \\
\text{Therefore }a_{n,k} \text{ is dividable by } \frac{k}{2} \text{, for k - even number} \\
\text{Therefore } a_{n,k} \text{ is dividable by } k+1 \text{, for k - even number} \\
\color{green}{\text{Let's combine the statements now}}\\
\text{Therefore }a_{n,k} \text{ is dividable by } k*\frac{k+1}{2} \text{, for k - odd number}\\
\text{Therefore }a_{n,k} \text{ is dividable by } k*\frac{k+1}{2} \text{, for k - even number}\\
\color{green}{\text{Let's combine the statements again}}\\
\text{Therefore }a_{n,k} \text{ is dividable by } \frac{k*(k+1)}{2} \text{, for any k}\\
\color{green}{\text{And we have just proved the statement!}}\\
\color{green}{\text{Excellent work, Sergey!}}\\
\end{equation}