Maths Olympiad Prep

Library / /119 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Partition 12002,12003,12004,,12017\frac1{2002},\frac1{2003},\frac1{2004},\ldots,\frac{1}{2017} into two groups. Define AA the sum of the numbers in the first group, and BB the sum of the numbers in the second group. Find the partition such that AB|A-B| attains it minimum and explains the reason.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve the problem of partitioning the numbers 12002,12003,,12017\frac{1}{2002}, \frac{1}{2003}, \ldots, \frac{1}{2017} into two groups such that the absolute difference AB|A - B| is minimized, we can follow these steps:

1. Identify the sequence and its properties:
The sequence consists of the reciprocals of consecutive integers from 2002 to 2017. There are 16 terms in total.

2. Sum of the sequence:
Let S S be the sum of all the terms in the sequence:
S=k=200220171k S = \sum_{k=2002}^{2017} \frac{1}{k}

3. Partition into two groups:
We need to partition the sequence into two groups, say X X and Y Y , such that the sums of the reciprocals in each group are as close as possible. Let A A be the sum of the reciprocals in group X X and B B be the sum of the reciprocals in group Y Y .

4. **Minimize AB|A - B|:**
To minimize AB|A - B|, we need to ensure that the sums A A and B B are as close as possible. Since A+B=S A + B = S , we aim to have ABS2 A \approx B \approx \frac{S}{2} .

5. Consider partitions modulo 5:
To simplify the problem, consider the indices of the terms modulo 5. The indices 2002 to 2017 modulo 5 are:
20022(mod5),20033(mod5),20044(mod5),20050(mod5),20061(mod5) 2002 \equiv 2 \pmod{5}, \quad 2003 \equiv 3 \pmod{5}, \quad 2004 \equiv 4 \pmod{5}, \quad 2005 \equiv 0 \pmod{5}, \quad 2006 \equiv 1 \pmod{5}
20072(mod5),20083(mod5),20094(mod5),20100(mod5),20111(mod5) 2007 \equiv 2 \pmod{5}, \quad 2008 \equiv 3 \pmod{5}, \quad 2009 \equiv 4 \pmod{5}, \quad 2010 \equiv 0 \pmod{5}, \quad 2011 \equiv 1 \pmod{5}
20122(mod5),20133(mod5),20144(mod5),20150(mod5),20161(mod5),20172(mod5) 2012 \equiv 2 \pmod{5}, \quad 2013 \equiv 3 \pmod{5}, \quad 2014 \equiv 4 \pmod{5}, \quad 2015 \equiv 0 \pmod{5}, \quad 2016 \equiv 1 \pmod{5}, \quad 2017 \equiv 2 \pmod{5}

6. Count elements in each residue class:
Let xr x_r denote the number of elements in X X that are congruent to r(mod5) r \pmod{5} , and similarly define yr y_r for Y Y . We have:
x0+y0=4,x1+y1=3,x2+y2=4,x3+y3=3,x4+y4=2 x_0 + y_0 = 4, \quad x_1 + y_1 = 3, \quad x_2 + y_2 = 4, \quad x_3 + y_3 = 3, \quad x_4 + y_4 = 2

7. Balance the sums:
To balance the sums, we need to distribute the elements such that the sums of the reciprocals are as close as possible. One possible way to achieve this is to ensure that the number of elements in each residue class is balanced between the two groups.

8. Construct the partition:
A possible partition that balances the sums is:
X={2005,2010,2015,2002,2007,2012,2003,2008,2013,2004,2009,2014} X = \{2005, 2010, 2015, 2002, 2007, 2012, 2003, 2008, 2013, 2004, 2009, 2014\}
Y={2006,2011,2016,2017} Y = \{2006, 2011, 2016, 2017\}

This partition ensures that the sums A A and B B are as close as possible.

The final answer is X={2005,2010,2015,2002,2007,2012,2003,2008,2013,2004,2009,2014},Y={2006,2011,2016,2017}\boxed{X = \{2005, 2010, 2015, 2002, 2007, 2012, 2003, 2008, 2013, 2004, 2009, 2014\}, Y = \{2006, 2011, 2016, 2017\}}.

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