Library / /25 of 30

, 2023

Combinatorics Difficulty 8.5 Shortlist Prove it Saudi Arabia

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.

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$

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.