Maths Olympiad Prep

Library / Argentina competition problems /11 of 20

Argentina competition problems

Combinatorics Difficulty 5.9 AIME, harder Prove it Argentina

A set of natural numbers is regular if each of the subsets has sum different from 18101810. Partition the numbers 452452, 453453, …\ldots, 18091809 into a minimum number of regular sets.

Solution

Such a partition clearly needs at least 22 regular sets (e.g., 900900 and 910910 must be in different regular sets). Here is a partition with 22 regular sets:

A={452,…,602}∪{906,…,1207},B={603,…,905}∪{1208,…,1809}. A = \{452, \ldots, 602\} \cup \{906, \ldots, 1207\}, \quad B = \{603, \ldots, 905\} \cup \{1208, \ldots, 1809\}.

Let us check that AA and BB are indeed regular. Suppose on the contrary that one of them has a subset XX with sum 18101810. Note that XX has at most 33 elements as the sum of the 44 smallest numbers among 452452, 453453, …\ldots, 18091809 is 452+453+454+455>1810452+453+454+455>1810. Let XX have exactly 33 elements x,y,zx, y, z with x+y+z=1810x+y+z=1810. If X⊂BX \subset B then x+y+z≥603+604+605>1810x+y+z \ge 603+604+605>1810, which is impossible. Hence X⊂AX \subset A and clearly one of x,y,zx, y, z is in {452,…,602}\{452, \ldots, 602\}. In addition one of them is in {906,…,1207}\{906, \ldots, 1207\} because the three largest numbers in {452,…,602}\{452, \ldots, 602\} have sum less than 18101810. If, e.g., x≥906x \ge 906 then y+z≤904y+z \le 904; in particular y,z∈{452,…,602}y, z \in \{452, \ldots, 602\}. However then y+z≥452+453=905y+z \ge 452+453=905, a contradiction.

Let XX have exactly 22 elements x,yx, y with x+y=1810x+y=1810 and x<yx < y; then x≤904x \le 904, y≥906y \ge 906. It follows that if X⊂AX \subset A then x≤602x \le 602. On the other hand y≤1207y \le 1207, so that x+y≤602+1207<1810x+y \le 602+1207<1810. Similarly if X⊂BX \subset B then y≥1208y \ge 1208. Because x≥603x \ge 603, this yields x+y≥603+1208>1810x+y \ge 603+1208>1810. In both cases we reach a contradiction.

Because XX has more than 11 element, the conclusion is that AA and BB are both regular.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.