No Square Sums

How many numbers do you need to remove to avoid making a perfect square?
Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving
Being curious Being resourceful Being resilient Being collaborative

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.