There is a subset $T \subset S$ with $|T| = k+1$ such that for every $a,b \in T$, the number $a^2-b^2$ is divisible by $10$.

Question

Let $k \ge 1$ be an integer.

If $S$ is a set of positive integers with $|S| = N$, then there is a subset $T \subset S$ with $|T| = k+1$ such that for every $a,b \in T$, the number $a^2-b^2$ is divisible by $10$.

What is the smallest value of $N$ as a function of $k$ so that the above statement is true?

---

I have observed that perfect squares end with $0,1,4,5,6$ and $9$. If we have two perfect squares that end with the same as one of $0,1,4,5,6$ and $9$, then we are done.

I think by PHP we should have $\left\lceil\frac{N}{k}\right\rceil = 6$.

Answer 1

Let $N_k$ be the smallest value of $N$ with this property.

As observed, perfect squares end with 0,1,4,5,6 or 9, and then by the Pigeonhole Principle, every set $S$ of size $6k+1$ has a subset $T$ such that for every $a,b \in T$, $10|a^2-b^2$.

This shows that $N_k\leq 6k+1$.

Let's prove that in fact $N_k=6k+1$, that is, there is a set $S$ with $|S|=6k$ such that for every $T \subset S$ with $T=k+1$ there is $a,b\in T$ with $a^2-b^2$ not a multiple of 10.

Then we can define $S$ to be a set such that for each $i \in \{0,1,4,5,6,9\}$, $S$ has exactly $k$ numbers such that its square ends with $i$.

Thus, every subset of size $k+1$ of $S$ has $a,b$ with $a^2-b^2$ not a multiple of $10$.

The only thing we are using to construct $S$ is that this families $\mathcal{F}_i=\{n\in\mathbb{N}:n^2\equiv i \text{ (mod 10)}\}$ are infinity for every $i \in \{0,1,4,5,6,9\}$.