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

Difference between revisions of "1989 IMO Problems/Problem 1"

(Created page with "Prove that in the set <math> \{1,2, \ldots, 1989\}</math> can be expressed as the disjoint union of subsets <math> A_i, \{i = 1,2, \ldots, 117\}</math> such that i.) each <ma...")
 
(→‎Problem)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 +
== Problem ==
 +
 
Prove that in the set <math> \{1,2, \ldots, 1989\}</math> can be expressed as the disjoint union of subsets <math> A_i, \{i = 1,2, \ldots, 117\}</math> such that
 
Prove that in the set <math> \{1,2, \ldots, 1989\}</math> can be expressed as the disjoint union of subsets <math> A_i, \{i = 1,2, \ldots, 117\}</math> such that
  
Line 4: Line 6:
  
 
ii.) the sum of all the elements in each <math> A_i</math> is the same.
 
ii.) the sum of all the elements in each <math> A_i</math> is the same.
 +
 +
 +
== Solution ==
 +
 +
Let us start pairing numbers in the following fashion, where each pair sums to <math>1990</math>:
 +
<math>(1, 1990-1),
 +
(2, 1990-2),
 +
\ldots
 +
(936, 1054)</math>
 +
 +
There are a total of <math>117*8</math> pairs above. Let us start putting these pairs into each of the <math>117</math> subsets starting with the first pair <math>(1, 1990-1)</math> going into <math>A_1</math>, <math>(2, 1990-2)</math> into <math>A_2</math> and so on <math>\ldots</math> with <math>(k, 1990-k)</math> going into <math>A_{k(mod 117)}</math>.
 +
 +
Now we have <math>16</math> numbers present in each of the <math>117</math> subsets all of which have the same total sum. We need <math>1</math> more number to be filled in each subset from the remaining <math>117</math> numbers <math>(937, 938, ... 1053)</math>.
 +
 +
Let us arrange these <math>117</math> numbers in the following manner:
 +
<math>995-58, 995-57,  \ldots, 995-1, 995, 995+1, 995+2, \ldots, 995+57, 995+58</math>  <math>==> (1)</math>
 +
 +
Now notice that for each number that's off by <math>x</math> from <math>995</math>, there's a counter number off by <math>x</math> from <math>995</math> in the opposite direction.
 +
 +
So we need to create similar imbalances in the Subsets <math>A_1</math> to <math>A_{117}</math>, so that we could add the above <math>117</math> numbers to those imbalances to keep the total sum unchanged.
 +
 +
Now start swapping the <math>1st</math> number of each pair that we added to subsets <math>A_1</math> to <math>A_{117}</math> to create the above imbalances:
 +
 +
Swap <math>1</math> from <math>A_1</math> with <math>59</math> from <math>A_{59}</math> - this creates an imbalance of <math>+58</math> and <math>-58</math>
 +
 +
Swap <math>2</math> from <math>A_2</math> with <math>58</math> from <math>A_{58}</math> - this creates an imbalance of <math>+56</math> and <math>-56</math>
 +
 +
<math>\ldots</math>
 +
 +
Swap <math>29</math> from <math>A_{29}</math> with <math>31</math> from <math>A_{31}</math> - creates an imbalance of <math>+2</math> and <math>-2</math>
 +
 +
Leave <math>30</math> in <math>A_{30}</math> as it is - <math>0</math> imbalance.
 +
 +
Similarly,
 +
 +
Swap <math>60</math> from <math>A_{60}</math> with <math>117</math> from <math>A_{117}</math> - this creates an imbalance of <math>+57</math> and <math>-57</math>
 +
 +
Swap <math>61</math> from <math>A_{61}</math> with <math>116</math> from <math>A_{116}</math> - this creates an imbalance of <math>+55</math> and <math>-55</math>
 +
 +
<math>\ldots</math>
 +
 +
Swap <math>88</math> from <math>A_{88}</math> with <math>89</math> from <math>A_{89}</math> - this creates an imbalance of <math>+1</math> and <math>-1</math>
 +
 +
Now start adding the <math>117</math> numbers from <math>(1)</math> to the subsets <math>A_1</math> to <math>A_{117}</math> to counter the imbalances <math>-58</math> to <math>+58</math> so that the sum remains unchanged. Notice that each subset now has <math>17</math> elements with total sum = <math>8*1990 + 995 = 16915</math>.
 +
 +
 +
<math>- Kris17</math>
 +
 +
 +
 +
== See Also ==
 +
{{IMO box|year=1989|before=First question|num-a=2}}

Latest revision as of 23:26, 16 March 2020

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"