Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1989 IMO Problems/Problem 1

Problem

Prove that in the set $\{1,2, \ldots, 1989\}$ can be expressed as the disjoint union of subsets $A_i, \{i = 1,2, \ldots, 117\}$ such that

i.) each $A_i$ contains 17 elements

ii.) the sum of all the elements in each $A_i$ is the same.


Solution

Let us start pairing numbers in the following fashion, where each pair sums to $1990$: $(1, 1990-1), (2, 1990-2), \ldots (936, 1054)$

There are a total of $117*8$ pairs above. Let us start putting these pairs into each of the $117$ subsets starting with the first pair $(1, 1990-1)$ going into $A_1$, $(2, 1990-2)$ into $A_2$ and so on $\ldots$ with $(k, 1990-k)$ going into $A_{k(mod 117)}$.

Now we have $16$ numbers present in each of the $117$ subsets all of which have the same total sum. We need $1$ more number to be filled in each subset from the remaining $117$ numbers $(937, 938, ... 1053)$.

Let us arrange these $117$ numbers in the following manner: $995-58, 995-57, \ldots, 995-1, 995, 995+1, 995+2, \ldots, 995+57, 995+58$ $==> (1)$

Now notice that for each number that's off by $x$ from $995$, there's a counter number off by $x$ from $995$ in the opposite direction.

So we need to create similar imbalances in the Subsets $A_1$ to $A_{117}$, so that we could add the above $117$ numbers to those imbalances to keep the total sum unchanged.

Now start swapping the $1st$ number of each pair that we added to subsets $A_1$ to $A_{117}$ to create the above imbalances:

Swap $1$ from $A_1$ with $59$ from $A_{59}$ - this creates an imbalance of $+58$ and $-58$

Swap $2$ from $A_2$ with $58$ from $A_{58}$ - this creates an imbalance of $+56$ and $-56$

$\ldots$

Swap $29$ from $A_{29}$ with $31$ from $A_{31}$ - creates an imbalance of $+2$ and $-2$

Leave $30$ in $A_{30}$ as it is - $0$ imbalance.

Similarly,

Swap $60$ from $A_{60}$ with $117$ from $A_{117}$ - this creates an imbalance of $+57$ and $-57$

Swap $61$ from $A_{61}$ with $116$ from $A_{116}$ - this creates an imbalance of $+55$ and $-55$

$\ldots$

Swap $88$ from $A_{88}$ with $89$ from $A_{89}$ - this creates an imbalance of $+1$ and $-1$

Now start adding the $117$ numbers from $(1)$ to the subsets $A_1$ to $A_{117}$ to counter the imbalances $-58$ to $+58$ so that the sum remains unchanged. Notice that each subset now has $17$ elements with total sum = $8*1990 + 995 = 16915$.


$- Kris17$


See Also

1989 IMO (Problems) • Resources
Preceded by
First question 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_IMO_Problems/Problem_1&oldid=119616"