Let $A=\{1,2,...,100\}$ and $f(k), k\in N$ be the size of the largest subset of $A$ such that no two elements differ by $k$. How many solutions are there to $f(k)=50$?
Problem
Source: Malaysia National Math Olympiad - Sulong Problem 4
Tags: number theory
29.10.2019 23:20
Let $B\subset A$ such that no two elements differ by $k$. Property $P1$: in a set containing $k$ consecutive natural numbers, the difference between any two numbers is less than $k$. Property $P2$: for $k\le 50$, in a set $S=\{a,a+1,a+2,\dots,a+2k-1\}$ containing $2k$ consecutive natural numbers, exist at most $k$ numbers such that the difference between any two numbers is different from $k$. Indeed, at most one of the numbers $b,b+k\in S$ can appear in $B$, where $a\le b\le a+k-1$. Results $|S\cap B|\le k$. Property $P3$: for $k\ge 51$, using $P1$, we can choose $\{1,2,\dots,k\}\subset B$, hence $f(k)\ge |B|\ge k\ge 51$. Hence, $f(k)=50$ can have solutions only for $k\le 50$. $\textbf{Case 1: }k|50$. Results: exists $d\in\mathbb N$ such that $kd=50$. Denote $A_m=\{2mk+1, 2mk+2,\dots,(2m+2)k\}, 0\le m\le d-1$. We observe: $A=\cup_{m=0}^{d-1}A_m$. Using the property $P2$ results $|A_m\cap B|\le k\Longrightarrow |A\cap B|=|B|\le kd=50$. We construct $B=\cup_{m=0}^{d-1}B_m=\cup_{m=0}^{d-1}\{2mk+1, 2mk+2,\dots,(2m+1)k\}$. In each subset $\{2mk+1, 2mk+2,\dots,(2m+1)k\}$, the difference between any two numbers is less than $k$. For $p,q$ elements in different subsets $B_m$ results $|p-q|>k$. Results: $|B|=kd=50$. Results: the set $B$ constructed above has the maximum size. Hence, all $k\in\mathbb{N}, k|50$ are solutions of the equation $f(k)=50$. $\textbf{Case 2: }k<50, k\nmid50$. Results: exist $d,r\in\mathbb{N}, 1\le r\le k-1$ such that $50=kd+r\Longrightarrow 100=2kd+2r$. For $0\le m\le d-1$, denote $B_m=\{2mk+1, 2mk+2,\dots,(2m+1)k\}$. Let be $B_d=\{2kd+1, 2kd+2, \dots,\min{(2kd+k,100)}\}$. The set $B=\cup_{m=0}^{d}B_m$ has $|B|=\min{(kd+k,kd+100-2kd)}$. $kd+k>kd+r=50$; $kd+100-2kd=kd+2r>kd+r=50$. Hence, $f(k)\ge|B|>50$ and $k$ is not solution of $f(k)=50$. Results: The solutions of $f(k)=50$ are the numbers $k|50$. $50=2\cdot5^2$, hence $50$ has $2\cdot3=6$ natural divisors. $f(k)=50$ has $6$ solutions, $k\in\{1,2,5,10,25,50\}$.