Olympiad Maths Prep

Track / Stage 6 / 91 of 400 #1091 of 2000

Problem 1091

National olympiad, first round
Combinatorics Difficulty 6.1 Prove it

2332 \cdot 33 Find a positive integer kk, such that the set X={1990,1990+1,,1990+k}X=\{1990,1990+1, \cdots, 1990+k\} can be partitioned into two disjoint subsets AA and BB, where the sum of the elements in AA equals the sum of the elements in BB.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

[Solution] We prove that if and only if:
(1) k3(mod4)k \equiv 3(\bmod 4), or
(2) k0(mod4)k \equiv 0 \quad(\bmod 4) and k92k \geqslant 92, XX can be divided into subsets AA and BB that meet the requirements.
First, we determine the conditions that kk should satisfy.
The sum of the elements in XX
1990(k+1)+k(k+1)2 1990(k+1)+\frac{k(k+1)}{2}

should be even, so 4k(k+1)4 \mid k(k+1).
k0(mod4), k \equiv 0 \quad(\bmod 4),

or
k3(mod4). k \equiv 3 \quad(\bmod 4).

If k0(mod4)k \equiv 0 \quad(\bmod 4), then X=k+1|X|=k+1 is odd. Let k=2mk=2m, where mm is even, and
Am+1,Bm, |A| \geqslant m+1,|B| \leqslant m,

At this time, the sum of the elements in AA
a1990+(1990+1)++(1990+m)=1990(m+1)+m(m+1)2, \begin{aligned} a & \geqslant 1990+(1990+1)+\cdots+(1990+m) \\ & =1990(m+1)+\frac{m(m+1)}{2}, \end{aligned}
the sum of the elements in BB
b(1990+m+1)++(1990+2m)=1990m+m2+m(m+1)2. \begin{aligned} b & \leqslant(1990+m+1)+\cdots+(1990+2 m) \\ & =1990 m+m^{2}+\frac{m(m+1)}{2}. \end{aligned}

Therefore, m21990\quad m^{2} \geqslant 1990.
Since mm is even, we have
m46,k92. m \geqslant 46, k \geqslant 92.

Next, we prove that the conditions are also sufficient.
Case 1: k3(mod4)k \equiv 3 \quad(\bmod 4).
In this case, the number of elements in XX is a multiple of 4. Since any set of 4 consecutive integers can be divided into two disjoint subsets with the same sum, XX has the same property.
Case 2: k0(mod4),k92k \equiv 0 \quad(\bmod 4), k \geqslant 92.
When k=92k=92, let
A1={1990,1991,1992,,1990+46},B1={1990+47,1990+48,,1990+92}, \begin{array}{l} A_{1}=\{1990,1991,1992, \cdots, 1990+46\}, \\ B_{1}=\{1990+47,1990+48, \cdots, 1990+92\}, \end{array}

then the sum of the elements in the latter is more by (471)×461990=126(47-1) \times 46-1990=126. By swapping 1990 in A1A_{1} with 1990+63 in B1B_{1}, the resulting two sets meet the requirements (i.e., the sums of the elements are equal).
When k>92k>92, by Case 1,
{1990+93,1990+94,,1990+k} \{1990+93,1990+94, \cdots, 1990+k\}
(its number of elements is a multiple of 4) can be divided into two disjoint subsets with the same sum. Therefore, combining the discussion for k=92k=92, XX has the same property.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.