There are given in a table numbers $1,2,...,18$. What is minimal number of numbers we should erase such that the sum of every two remaining numbers is not perfect square of a positive integer.
Problem
Source: Kosovo MO 2019 Grade 9, Problem 5
Tags: combinatorics
bsf714
03.03.2019 22:43
Does "such that the sum of every two remaining numbers ..." allow for us to add up a number with itself, or must the numbers we add be distinct?
dangerousliri
04.03.2019 00:11
bsf714 wrote: Does "such that the sum of every two remaining numbers ..." allow for us to add up a number with itself, or must the numbers we add be distinct? Distinct.
augustin_p
26.04.2019 21:07
Solution
There are the following sums:
$4=1+3$
$9=1+8=2+7=3+6=4+5$
$25=18+7=17+8=16+9=15+10=14+11=13+12$
We'll search for common numbers. First we'll erase $1$ because $4=$1$+3$ and $9=$1$+8$. Then we'll erase $3$ (or $6$). Then $8$ (or $17$), then $7$ because $9=$7$+2$ and $15=$7$+18$. The following numbers are only in a sum: $4$ (or $5$), $16$ (or $9$), $10$ (or $15$), $14$ (or $11$), $12$ (or $13$). We've erased $9$ numbers.