Maths Olympiad Prep

Library / /10 of 17

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 XBX \subset B then x+y+z603+604+605>1810x+y+z \ge 603+604+605>1810, which is impossible. Hence XAX \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., x906x \ge 906 then y+z904y+z \le 904; in particular y,z{452,,602}y, z \in \{452, \ldots, 602\}. However then y+z452+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 x904x \le 904, y906y \ge 906. It follows that if XAX \subset A then x602x \le 602. On the other hand y1207y \le 1207, so that x+y602+1207<1810x+y \le 602+1207<1810. Similarly if XBX \subset B then y1208y \ge 1208. Because x603x \ge 603, this yields x+y603+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,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.