Maths Olympiad Prep

Library / /260 of 520

Number theory Difficulty 6.5 National olympiad Prove it

Let k>2k>2 be an integer. A positive integer \ell is called kk-able if we can partition the numbers 1,3,5,,2k11,3,5, \ldots, 2 k-1 into two sets AA and BB such that the sum of the elements of AA is exactly \ell times the sum of the elements of BB. Prove that the smallest kk-able number is relatively prime to kk.

Solution

We will prove that if pp is the smallest prime divisor of kk, then p1p-1 is the smallest kk-pable number. This implies the desired result, as it then follows that ggd(p1,k)=1\operatorname{ggd}(p-1, k)=1. We know that 1+3+5++(2k1)=k21+3+5+\ldots+(2 k-1)=k^{2}. If \ell is a kk-pable number and ss is the sum of the elements in BB, then the sum of the elements in AA is s\ell s, so the total sum is (+1)s(\ell+1) s and this must equal k2k^{2}. Thus, +1k2\ell+1 \mid k^{2}. Since +12\ell+1 \geq 2, it follows that +1p\ell+1 \geq p, where pp is the smallest prime divisor of kk. Therefore, p1\ell \geq p-1. We will now prove that =p1\ell=p-1 is a kk-pable number, which immediately implies that it is the smallest kk-pable number. And we are done, because ggd(k,p1)=1\operatorname{ggd}(k, p-1)=1 since there are no prime divisors smaller than pp in kk.
First, assume that kk is even, so p=2p=2. We need to prove that we can partition the set {1,3,,2k1}\{1,3, \ldots, 2 k-1\} into two sets with equal sums of the elements. We prove this by induction on kk. For k=4k=4 and k=6k=6, we have {1,7},{3,5}\{1,7\},\{3,5\} and {1,3,5,9},{7,11}\{1,3,5,9\},\{7,11\}, respectively. If we can partition the set {1,3,,2k1}\{1,3, \ldots, 2 k-1\} in this way, we can also do it for the set {1,3,,2(k+4)1}\{1,3, \ldots, 2(k+4)-1\} by placing the new elements {2k+1,2k+3,2k+5,2k+7}\{2 k+1,2 k+3,2 k+5,2 k+7\} into the sets such that 2k+12 k+1 and 2k+72 k+7 go into one set and 2k+32 k+3 and 2k+52 k+5 go into the other. This completes the induction. Now assume that kk is odd. Write k=pmk=p m. It is sufficient to find a subset BB of {1,3,,2k1}\{1,3, \ldots, 2 k-1\} whose sum of elements is pm2p m^{2}, because then the sum of the elements in the set A={1,3,,2k1}\BA=\{1,3, \ldots, 2 k-1\} \backslash B is k2pm2=p2m2pm2=(p1)pm2k^{2}-p m^{2}=p^{2} m^{2}-p m^{2}=(p-1) p m^{2}, which is exactly (p1)(p-1) times the sum of the elements in BB. Consider the set B={p,3p,,(2m1)p}{1,3,,2k1}B=\{p, 3 p, \ldots,(2 m-1) p\} \subset\{1,3, \ldots, 2 k-1\}. Then the sum of the elements in BB is

p+3p++(2m1)p=p(1+3++(2m1))=pm2 p+3 p+\cdots+(2 m-1) p=p(1+3+\cdots+(2 m-1))=p m^{2}

exactly as intended.

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.