Maths Olympiad Prep

Library / /17 of 18

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Belarus

Find all positive integers nn (n<60n < 60) such that the set M={n,n+1,,60}M = \{n, n+1, \dots, 60\} can be partitioned into disjoint subsets so that in each subset one of the numbers is equal to the sum of all other numbers of this subset.
(V. Kaskevich)

Solution

A number aa from a subset of the desired partition is called major if aa is equal to the sum of all other numbers of this subset. All numbers in each subset must be distinct, since one of them is major we see that there exist at least three numbers in each subset. Let kk be the number of the subsets of the desired partition. Since we have 61n61 - n numbers in the initial set M={n,n+1,,60}M = \{n, n+1, \dots, 60\}, we have k61n3k \le \frac{61-n}{3}. On the other hand, if aa is the major number of some subset, then the sum of the numbers of this subset is equal to 2a2a. So the sum S(n)S(n) of all numbers of the set MM must be even

(S(n)=(n+60)(61n)2S(n) = \frac{(n+60)(61-n)}{2}, and the sum of all numbers of all subsets is less than or equal to
2(60+59+58++(61k))=2(60+61k)k2=(121k)k 2 \cdot (60 + 59 + 58 + \dots + (61-k)) = 2 \cdot \frac{(60+61-k) \cdot k}{2} = (121-k) \cdot k \le
(12161n3)61n3=(302+n)(61n)9. \le \left(121 - \frac{61-n}{3}\right) \cdot \frac{61-n}{3} = \frac{(302+n)(61-n)}{9}.
(The last inequality holds because k(61n)/3121/2k \le (61-n)/3 \le 121/2 and the function (121x)x(121-x)x increases for x121/2x \le 121/2.) Therefore, the following condition is necessary to exist the desired partition:
S(n)(302+n)(61n)9(n+60)(61n)2(302+n)(61n)9 S(n) \le \frac{(302+n)(61-n)}{9} \Leftrightarrow \frac{(n+60)(61-n)}{2} \le \frac{(302+n)(61-n)}{9} \Leftrightarrow
9(n+60)2(302+n)7n64, 9(n+60) \le 2(302+n) \Leftrightarrow 7n \le 64,
i.e., n91/7n \le 9^{1/7}, and since nn is an integer number, we have n9n \le 9.
The sum S(n)=(n+60)(61n)2S(n) = \frac{(n+60)(61-n)}{2} is even, so either n=4mn = 4m or n=4m+1n = 4m+1, i.e., n{1,4,5,8,9}n \in \{1, 4, 5, 8, 9\}.
If n=9n=9, then S(9)=(9+60)(619)2=6926=1794S(9) = \frac{(9+60)(61-9)}{2} = 69 \cdot 26 = 1794. The number kk of the subsets is less than or equal to k6193=1713k \le \frac{61-9}{3} = 17\frac{1}{3}, i.e., k17k \le 17. But for these kk the sum of all numbers in the subsets is less than or equal to (121k)k=10417=1768<S(9)(121-k) \cdot k = 104 \cdot 17 = 1768 < S(9), a contradiction. Similarly, if n=8n=8, then S(8)=1804S(8) = 1804, k=[53:3]=17k = [53:3] = 17, and 1768<S(8)1768 < S(8), a contradiction.

<table><tr><td>60</td><td>59</td><td>58</td><td>57</td><td>56</td><td>55</td><td>54</td><td>53</td><td>52</td></tr><tr><td>43</td><td>41</td><td>39</td><td>37</td><td>35</td><td>33</td><td>31</td><td>29</td><td>27</td></tr><tr><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td></tr></table>
<table><tr><td>51</td><td>50</td><td>49</td><td>48</td><td>47</td><td>46</td><td>45</td><td>44</td><td>26</td></tr><tr><td>42</td><td>40</td><td>38</td><td>36</td><td>34</td><td>32</td><td>30</td><td>28</td><td>8,6</td></tr><tr><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>7,5</td></tr></table>

<table><tr><td>60</td><td>59</td><td>58</td><td>57</td><td>56</td><td>55</td><td>54</td><td>53</td><td>52</td></tr><tr><td>43</td><td>41</td><td>39</td><td>37</td><td>35</td><td>33</td><td>31</td><td>29</td><td>27</td></tr><tr><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td></tr><tr><td>51</td><td>50</td><td>49</td><td>48</td><td>47</td><td>46</td><td>45</td><td>44</td><td>28</td></tr><tr><td>42</td><td>40</td><td>38</td><td>36</td><td>34</td><td>32</td><td>30</td><td>26</td><td>16</td></tr><tr><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>8,6,4</td><td>7,5</td></tr></table>
n=4n=4

If we add the subset {1,2,3}\{1,2,3\} to the given partition for n=4n=4 we obtain the desired partition for n=1n=1.

The desired partitions exist for n=1,4,5n=1,4,5. The following tables give the examples of the desired partition for n=5n=5 and n=4n=4:
<table><tr><td>60</td><td>59</td><td>58</td><td>57</td><td>56</td><td>55</td><td>54</td><td>53</td><td>52</td></tr><tr><td>43</td><td>41</td><td>39</td><td>37</td><td>35</td><td>33</td><td>31</td><td>29</td><td>27</td></tr><tr><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td></tr></table>
<table><tr><td>51</td><td>50</td><td>49</td><td>48</td><td>47</td><td>46</td><td>45</td><td>44</td><td>26</td></tr><tr><td>42</td><td>40</td><td>38</td><td>36</td><td>34</td><td>32</td><td>30</td><td>28</td><td>8,6</td></tr><tr><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>7,5</td></tr></table>

n=5n=5

If we add the subset {1,2,3}\{1,2,3\} to the given partition for n=4n=4 we obtain the desired partition for n=1n=1.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.