Maths Olympiad Prep

Library / /56 of 92

Combinatorics Difficulty 6.6 National olympiad Prove it Iran

Find all natural numbers n2n \ge 2 such that for every pair of integers i,j[0,n]i, j \in [0, n], i+ji + j and (ni)+(nj)\begin{pmatrix} n \\ i \end{pmatrix} + \begin{pmatrix} n \\ j \end{pmatrix} have the same parity.

Solution

Lemma. Suppose n2n \ge 2 is an integer, then all of the numbers (n0),(n1),,(nn)\begin{pmatrix} n \\ 0 \end{pmatrix}, \begin{pmatrix} n \\ 1 \end{pmatrix}, \dots, \begin{pmatrix} n \\ n \end{pmatrix} are odd if and only if n=2k1n = 2^k - 1 for an integer k2k \ge 2.

*Proof*. For an integer tt, let v(t)v(t) be the greatest integer uu such that 2un2^u \mid n. We know that
" If p,qNp, q \in \mathbb{N} and 0p2q0 \le p \le 2^q then v(p)=v(2q+p)=v(2qp)v(p) = v(2^q + p) = v(2^q - p)" (1)
Because if p=2abp = 2^a b with a,bNa, b \in \mathbb{N} and bb an odd number then a<qa < q and 2q±p=2a(2qa±b)2^q \pm p = 2^a (2^{q-a} \pm b) where 2qa±b2^{q-a} \pm b are odd numbers.
Now there is one and only one mNm \in \mathbb{N} such that 2mn<2m+12^m \le n < 2^{m+1}. Let n=2m+sn = 2^m + s
with 0s<2m0 \le s < 2^m. Now consider the number (n2m1)\begin{pmatrix} n \\ 2^m - 1 \end{pmatrix}. We have
(n2m1)=(2m+s2m1)=(2m+ss+1)=(2m+s)(2m+s1)(2m+1)(2m)s(s1)(1)(s+1). \begin{pmatrix} n \\ 2^m - 1 \end{pmatrix} = \begin{pmatrix} 2^m + s \\ 2^m - 1 \end{pmatrix} = \begin{pmatrix} 2^m + s \\ s + 1 \end{pmatrix} = \frac{(2^m + s)(2^m + s - 1)\cdots(2^m + 1)(2^m)}{s(s-1)\cdots(1)(s+1)}.
By (1) we have v(2m+i)=v(i)v(2^m + i) = v(i) where 1is1 \le i \le s, therefore
v((2m+s)(2m+1))=v(s!), v((2^m + s) \cdots (2^m + 1)) = v(s!),
and by assumption (n2m1)\begin{pmatrix} n \\ 2^m - 1 \end{pmatrix} is odd therefore v(2m)=v(s+1)v(2^m) = v(s+1) and consequently
2ms+12^m \mid s+1 and s+11s+1 \ge 1. Hence we have 2m1s2^m - 1 \le s and therefore s=2m1s = 2^m - 1 and
n=2m+s=2m+11n = 2^m + s = 2^{m+1} - 1.
Now if n=2k1n = 2^k - 1 for some natural number kk, for each 1cn1 \le c \le n we have
(2k1c)=(2k1)(2k2)(2kc)(1)(2)(c)and by (1) we know for1lc \begin{pmatrix} 2^k - 1 \\ c \end{pmatrix} = \frac{(2^k - 1)(2^k - 2)\cdots(2^k - c)}{(1)(2)\cdots(c)} \quad \text{and by (1) we know for} \quad 1 \le l \le c
v(2kl)=v(l), so (2k1c) is odd for 0cn. v(2^k - l) = v(l), \text{ so } \begin{pmatrix} 2^k - 1 \\ c \end{pmatrix} \text{ is odd for } 0 \le c \le n. \quad \square

Now we return to main problem:
Positive integer nn has the property of the problem if and only if all the numbers (ni)i\begin{pmatrix} n \\ i \end{pmatrix} - i (0in0 \le i \le n) have the same parity. It means that for every 0in10 \le i \le n-1, (ni),(ni+1)\begin{pmatrix} n \\ i \end{pmatrix}, \begin{pmatrix} n \\ i+1 \end{pmatrix} have different parities. So (n+1i+1)=(ni)+(ni+1)\begin{pmatrix} n+1 \\ i+1 \end{pmatrix} = \begin{pmatrix} n \\ i \end{pmatrix} + \begin{pmatrix} n \\ i+1 \end{pmatrix} (1in11 \le i \le n-1) is odd
and as we know (n+10)=1\begin{pmatrix} n+1 \\ 0 \end{pmatrix} = 1 is also odd. Therefore by the lemma this is equivalence
to n+1=2k1n+1 = 2^k - 1 for some integer k2k \ge 2 so n=2k2n = 2^k - 2 where k2k \ge 2 is an integer.
\boxed{}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.