Actually, it is Selection Test 2 Day 1 Q1

Can you please post the other problems. Most of the questions is very gibberish once translated from Chinese by the Google. I had a very hard time trying to make sense to them.

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=125&t=527628

iarnab_kundu wrote: Prove that for any positive integer $i$ there exists pair of positive integers $m>n>i$ such that $S_i(m)=S_i(n)$. Prove that for any positive integers $m>n>i $, then $S_i(m)=S_i(n)$

Set $D_i(n) = d_i(n + 1)$, and associate with $D_i(n)$ a pair $(x_{n,i}, y_{n,i}) \in \{0, 1, \dots, n\}^2$ with $n \ge x_{n,i} \ge y_{n,i} \ge 0$ and $x_{n,i}^2 + y_{n,i}^2 = D_i(n)^2$. We prove by induction on $n$ that for $1 \le i \le n$ the pairs $(x_i, y_i)$ are unique and equal, in order, \[(n, n), (n, n - 1), (n, n - 2), (n - 1, n - 1), (n, n - 3), (n - 1, n - 2) \dots \; \; \; \; (1)\] Remark that this would immediately imply the result; it would follow that $(x_{N, i}, y_{N, i}) = (x_{N - 1, i} + 1, y_{N - 1, i} + 1)$ for all $1 \le i \le N - 1$, whence inductively $(x_{N - 1 + p, i}, y_{N - 1 + p, i}) = (x_{N - 1, i} + p, y_{N - 1, i} + p)$. Furthermore, these pairs are unique and so it's easy to see that $S_i(m) = S_i(n)$ for all $m > n > i$ (extending both dimensions of a segment by one along with extending the dimension of the grid by one does not change the number of distinct placements of that segment). It remains to prove $(1)$. When $n = 1$ the result is obvious, so suppose it holds for $n = N - 1$. Notice that \[(x_{N, i}, y_{N, i}) = (x_{N - 1, i} + 1, y_{N - 1, i} + 1)\] for $1 \le i \le N - 1$. This is because when $a^2 + b^2 > c^2 + d^2$ and $a + b \ge c + d$, \[(a + 1)^2 + (b + 1)^2 = a^2 + b^2 + 2(a + b) + 1 > c^2 + d^2 + 2(c + d) + 1 = (c + 1)^2 + (d + 1)^2\] and we know $y_i > 0$ and the sum $x_{N - 1, i} + y_{N - 1, i}$ is non-increasing in $i$. Thus there is a bijection from $D_i(N - 1)$ and $D_i(N)$ for $1 \le i \le N$, so the $(x_{N, i}, y_{N, i})$ are unique and $(1)$ holds for $1 \le i \le N - 1$. Then it remains only to show that $(x_{N, N}, y_{N, N})$ obeys $(1)$ as well. Let $s = x_{N, N - 1} + y_{N, N - 1}$. If $x_{N, N - 1} - y_{N, N - 1} \le 1$, we have exhausted all possible values of $x_{N, i} + y_{N, i}$ greater than or equal to $s$, and so $x_{N, N} + y_{N, N} \le s - 1$. It follows that $x_{N, N} = n$ and $y_{N , N} = s - n - 1$ by the convexity of $f(t) = t^2$. Otherwise, using $(1)$ we can explicitly compute \[x_{N, N - 1} = N - (k - 1)\] \[y_{N + 1, N} = N + 1 + (k - 1) - \lfloor \sqrt{4N + 2} \rfloor\] where \[k = N - 1 - \lfloor \frac{\lfloor \sqrt{4N + 2} \rfloor^2}{4} \rfloor\] We claim $x_{N, N} = x_{N, N - 1} - 1$ and $y_{N, N} + y_{N, N - 1} + 1$. Again by the convexity of $f(t) = t^2$, it is sufficient to show \[(N - k)^2 + (N + 1 + k - \lfloor \sqrt{4N + 2} \rfloor)^2 > N^2 + (N - \lfloor \sqrt{4N + 2} \rfloor)^2\] \[{2k^2 - (2 \lfloor \sqrt{4N + 2} \rfloor - 2)k + (2N - 2 \lfloor \sqrt{4N + 2} \rfloor} + 1) > 0\] \[2k^2 - (2\lfloor \sqrt{4N + 2} \rfloor - 2)k + (2N - 2 \lfloor \sqrt{4N + 2} \rfloor + 1) > 0\] \[k = N - 1 - \lfloor \frac{\lfloor \sqrt{4N + 2} \rfloor ^2}{4} \rfloor < \frac{2\lfloor \sqrt{4N + 2} \rfloor - 2 - \sqrt{(2\lfloor \sqrt{4N + 2} \rfloor - 2)^2 - 8(2N - 2 \lfloor \sqrt{4N + 2} \rfloor + 1)}}{4}\] Now set $g = \lfloor \sqrt{4N + 2} \rfloor$. This can be rewritten \[N - 1 - \lfloor \frac{g^2}{4} \rfloor < \frac{g - 1 - \sqrt{(g + 1)^2 - (4N + 2)}}{2}\] \[\sqrt{(g + 1)^2 - (4N + 2)} < 2 \lfloor \frac{g^2}{4} \rfloor + g + 1 - 2N\] \[2\sqrt{(g + 1)^2 - (4N + 2)} < 4\lfloor \frac{g^2}{4} \rfloor + 2g + 4 - (4N + 2)\] By AM-GM, it's sufficient to show \[1 + [(g + 1)^2 - (4N + 2)] < 4 \lfloor \frac{g^2}{4} \rfloor + 2g + 4 - (4N + 2)\] \[g^2 < 4 \lfloor \frac{g^2}{4} \rfloor + 2\] which follows from the fact that squares are either $0$ or $1$ modulo $4$.