Maths Olympiad Prep

Library / /5 of 9

Combinatorics Difficulty 6.4 National olympiad Find the answer

Can the positive integers be partitioned into 1212 subsets such that for each positive integer kk, the numbers k,2k,,12kk, 2k,\ldots,12k belong to different subsets?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine whether it is possible to partition the positive integers into 12 subsets such that for each positive integer k k , the numbers k,2k,,12k k, 2k, \ldots, 12k are in different subsets, we will examine the conditions and implications carefully.

First, consider the sequence formed by taking a positive integer k k and the multiples k,2k,,12k k, 2k, \ldots, 12k . If these 12 numbers need to be in different subsets, then each multiple must be placed in a unique subset. Therefore, for any set of 12 consecutive multiples starting with any integer k k , there must be at least 12 subsets.

Assume, for the sake of contradiction, that such a partition exists. Consider the least common multiple of the indices 1,2,,12 1, 2, \ldots, 12 , which is 27720. This means that every complete set of multiples k,2k,,12k k, 2k, \ldots, 12k repeats every 27720 integers.

Now, analyze the numbers 1,2,,12 1, 2, \ldots, 12 :
- Each of these 12 numbers must be placed in different subsets to satisfy the condition for k=1 k = 1 .

If we extend this logic to 27720, which covers every complete cycle of divisors up to 12, we see that every sub-cycle of size 12 within a full cycle of 27720 has to find distinct positions in 12 different subsets, as every base divisor and its multiples are unique within a cycle.

With only 12 subsets available, every number k,2k,,12k k, 2k, \ldots, 12k would ultimately map to a repeating subset selection as k k increases, eventually requiring some numbers within a cycle of 27720 to overlap in subsets.

This overlaps with the requirement that all sequences k,2k,,12k k, 2k, \ldots, 12k fully populate each cycle before repeating, which a mere 12 subsets cannot accommodate without conflict due to their limited count.

Hence, a contradiction arises, and it is impossible to maintain such a partition under these conditions. Therefore, the answer is:
No \boxed{\text{No}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.