No square sums
How many numbers do you need to remove to avoid making a perfect square?
Age
14 to 16
Challenge level
Problem
Shakil wants to remove numbers from the set $\{1, 2, 3,..., 16\}$ so that no two remaining numbers add to make a perfect square. What is the smallest number of numbers that he needs to remove?
If you liked this problem, here is an NRICH task which challenges you to use similar mathematical ideas.
Student Solutions
The following seven pairs add to $16$ so at least one of each pair must be removed:
$(1,15)$, $(2,14)$, $(3,13)$, $(4,12)$, $(5,11)$, $(6,10)$, $(7,9)$.
If removing these seven is sufficient, then we would be left with $8$, $16$ and seven others.
But
$16+9 = 25$
So we must remove $9$ and keep its partner
$7$
$7+2 = 9$
So we must remove $2$ and
keep $14$
$14+11 = 25$ So we
must remove $11$ and keep $5$
$5+4 = 9$
So we must remove $4$ and keep
$12$
$12+13 = 25$ So we
must remove $13$ and keep $3$
$3+1 = 4$
So we must remove $1$ and keep
$15$
$15+10 =
25$ So we must remove $10$ and
keep $6$
But we have kept $3$ and
$6$ which add to $9$.
Hence it is not
sufficient to remove only seven. If we remove the number $6$, we
obtain a set which satisfies the condition:
$\{8,16,7,14,5,12,3,15\}$ or in ascending order
$\{3,5,7,8,12,14,15,16\}$.
Hence eight is the
smallest number of numbers that may be removed.