Let $k > 2$ be an integer. A positive integer $l$ is said to be $k-pable$ if the numbers $1, 3, 5, . . . , 2k - 1$ can be partitioned into two subsets $A$ and $B$ in such a way that the sum of the elements of $A$ is exactly $l$ times as large as the sum of the elements of $B$. Show that the smallest $k-pable$ integer is coprime to $k$.
Problem
Source: Netherlands TST for IMO 2017 day 2 problem 3
Tags: number theory
01.02.2018 17:46
The problem doesn't make sense now it's fixed
01.02.2018 18:19
ythomashu wrote: The problem doesn't make sense ikr...
02.03.2021 00:49
Haven't seen a solution, so I will post mine. We claim that $l_{min} = p-1$ where $p$ is the smallest prime divisor of $k$. Let $s(A)$ be the sum of all of the elements of the set $A$. From the condition given to us in the problem we must have that: $$ls(B)+s(B)=1+3+5+\dots+2k-1=k^2$$. this in turn implies that we must have that $(l+1)s(B)=k^2$. Now let's say that $k=p^a.m$, where $p$ doesn't divide $m$ and $p$ is the smallest prime divisor of $k$. Now sketch out the numbers $1,3,\dots,2p^a m-1$ in a row, we shall try and minimize the sum $p^{2a-1}m^2$, since if we show that it is possible to have a sum of $p^{2a-1}m^2$, then we have that $l_{min} = p-1$. We will minimize in the following way, we will make pairs $(i,j)$, whose sum is $2p^am$ and $i < j$, then we take away from the sum that is left (i.e. from $p^{2a-1}m^2$ we take away $2p^am$ and the from that take away $2p^am$). We minimize until the leftover sum is less than or equal to $2p^am$. Let $t$ be the maximal number of those pairs. So we must have that: $$0 < p^{2a-1}m^2-2p^amt < 2p^am$$This implies that: $$0 < p^{a-1}m-2t < 2$$thus we have that: $$\frac{p^{a-1}m-2}{2} \leq t < \frac{p^{a-1}m}{2}$$thus we have that $t \in \left\{ \frac{p^{a-1}m-2}{2}; \frac{p^{a-1}m-1}{2} \right\}$ But for this all to hold we need to have that $t$ is less than the number of pairs whose sum is $2p^am$. But this is equivalent to the following: $$t < \left \lfloor \frac{p^am}{2} \right \rfloor$$But this holds, by just checking cases when $p^am$ is either even or odd. Thus a construction exists. This means that $l_{min} = p-1$, where $p$ is the smallest prime divisor of $k$. Thus $(l_{min},k)=1$.