Track / Stage 8 / 116 of 180 #1816 of 1964

Problem 1816

IMO Shortlist mid-range; USAMO P2/P5

Combinatorics Difficulty 8.5 Prove it SAUDI ARABIAN IMO Booklet 2023 · Saudi Arabia · 2023

Determine whether or not it is possible to partition the set of positive integers in infinite subsets $A_1, A_2, \dots$ such that for every positive integer $k$ , the sum of elements of $A_k$ is $k + 2023$ .

Remark: a partition of a set $X$ is a collection of subsets of $X$ such that every element of $X$ is contained in exactly one the subsets.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

The answer is No. Suppose such partition exists. Then for every positive integer $k$ , we have
$B_k = A_1 \cup A_2 \cup \dots \cup A_k \subset \{1, 2, \dots, k + 2023\},$
since all elements of $A_i$ are at most $i + 2023$ for every $i \in \{1, 2, \dots, k\}$ and
$\sum_{b \in B_k} b = \sum_{i=2024}^{k+2023} i < \sum_{i=1}^{k+2023} i.$
Now let $t_k$ be the minimum positive integer that not in $B_k$ . Then we have
$\sum_{i=2024}^{k+2023} i = \sum_{b \in B_k} b \le \left( \sum_{i=1}^{k+2023} i \right) - t_k,$
which implies that
$t_k \le \sum_{i=1}^{2023} i,$
for every integer $k$ . But that cannot happen if $A_1, A_2, \dots$ is a partition of the positive integers. $\square$

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