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.
Problem
Source: IMO 1989/1 , ISL 22, ILL 68
Tags: combinatorics, partition, Additive combinatorics, Set systems, IMO, IMO 1989
21.01.2010 16:13
Here comes one example: Lets divide in two each $ A_i$ The first part with $ 14$ elements and equal sum of $ 16387$ $ B_1 = \{1989,1988,1987,1986,1985,1984,1983,358,357,356,355,354,353,352\}$ $ B_2 = \{1982,1981,1980,1979,1978,1977,1976,365,364,363,362,361,360,359\}$ $ \cdots$ $ B_{117} = \{1177,1176,1175,1174,1173,1172,1171,1170,1169,1168,1167,1166,1165,1164\}$ The second part with the other $ 3$ elements and equal sum of $ 528$: $ C_1 = \{351,119,58\}$ $ C_2 = \{350,121,57\}$ $ \cdots$ $ C_{58} = \{294,233,1\}$ and the subsets $ C_{59} = \{293,118,117\}$ $ C_{60} = \{292,120,116\}$ $ \cdots$ $ C_{117} = \{235,234,59\}$
20.06.2011 17:12
Other ways are possible: Take $S_i=\{39i+1,\cdots, 39i+39\}$ and take $S_{ij}=\{39i+13j+1,\cdots, 39i+13j+13\}$ And let $S_{ijk}=39i+13j+k$ Then we see see we can take for $13:$ $(4,11,6),(1,12,8),(13,3,5),(9,10,2)$ and one time $7,7,7$ as $k's$ in: for $S_{00},S_{11},S_{22}$ $S_{01},S_{12},S_{20}$ and the other $3.$ Then it was also easy we can divide each subset of $\{117k+1\cdots 117k+233\}$ symmetrically in two equal sums of sets. **** Yet an other way. Find for $S_1$ until $S_3$ $21$ subsets with equal sum and of each $S_i$ one element. Then we can make the other $96$ sets symmetrically in the easy way the maximum mistake we have is less than $108$ now. In $S_kS_{k+1}$ where $k$ is even, we search $7$ couples of points with a difference of a "mistake" and change the symmetrically points and other we let in their correctsumtransformation. So without calculating a solution, we have proved at this way also.
03.07.2014 10:29
Extension: Find all $(a,b) \in \mathbb{Z}^2$ such that the set $\{1, 2, ..., ab\}$ can be expressed as the disjoint union of subsets $A_i$, $\{i=1, 2, ..., b\}$ such that i.) each $A_i$ contains $a$ elements ii.) the sum of all the elements in each $A_i$ is the same.
13.05.2015 18:20
Extension solution: Throughout the solution congruences will be taken $mod 2$. We claim that $(a,b) \not\equiv (1,0)$,with $a \neq 1$ is the entire family of solutions for our problem. By a trivial argument on the integerness of the $A_i$ sums,$(a,b) \equiv (1,0)$ is impossible.Also we can immediately disprove the $a=1$ case. By a similarly trivial induction with step $2$ on $a$,$(a,b) \equiv (0,1),(0,0)$ works. It remains to prove that $(a,b) \equiv (1,1)$ with $a \neq 1$ is valid.Once again we resort to step-2 induction on $a$.It is trivial to go from $a$ to $a+2$,so now we only need to do the base case $a=3$ to be done($a=1$ is not valid,thus it isn't our base case).For this we have to exhibit a solution family.Since $b$ is $1 \mod 2$,we can write $b=2l+1$.Now consider the set family $A_i=\{i,4l+3-2i,5l+3+i\}$ for $i=1,2,...,l$ $A_i=\{i,6l+4-2i,3l+2+i\}$ for $i=l+1,...,2l+1$. It's easily checkable by hand that all the $A_i$ are disjoint,their union is $\{1,2,...,6l+3\}$ and the sum in each $A_i$ is $9l+6$,thus we have found a solution set family for the case $a=3$ and we are done.
17.03.2020 06:41
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$.