Call a pair of integers $a$ and $b$ square makers , if $ab+1$ is a perfect square. Determine for which $n$ is it possible to divide the set $\{1,2, \dots , 2n\}$ into $n$ pairs of square makers.
Problem
Source: Iran second round 2020 ,Day 2 ,P5
Tags: number theory, Perfect Square
15.07.2020 12:46
Numbers =2 (mod 4) can only be a pair with a number divisible by 4. When n is odd there are $\frac{n+1}{2}$ 4k+2 that is one more than number of 4k's so it's impossible. n even : pair $m,m+2$ $\{ i, i+1,i+2,i+3 \} $ $i=1 (mod 4)$ $\mathfrak{FSOCIETY}$
15.07.2020 16:20
We claim that only even $n$ work. Denote $\{1,2,\dots, n\}=[n]$ and call $n$ squakable if $[n]$ can be partitioned into $n$ pairs of square makers (hereby known as squakers). To show that any even $n$ is squakable, note that $(\ell,\ell+2)$ is always a squaker. Then we may partition any set $S_a=\{a,a+1,a+2,a+3\}$ into two pairs of squakers (namely $(a,a+2)$ and $(a+1,a+3)$), so that for $n=2k$, $$[4k]=S_1\cup S_5\cup \dots \cup S_{4k-3}$$can be partitioned into $n$ pairs of squakers as claimed. Now we show odd $n$ fail. Squares are $0,1,$ and $4\pmod 8$, so if $(a,b)$ is a squaker and $a\equiv 2\pmod 8$, we can verify that $b\equiv 0$ or $4$. Similarly, if $a\equiv 6$, we must have $b\equiv 0$ or $4$. So if $[n]$ contains $A_n$ integers $2$ or $6\pmod 8$ and $B_n$ integers $0$ or $4\pmod 8$, we must have $A_n\leq B_n$ if $n$ is squakable. Now if $n=4k+1$, then compute $A_n=2k+1$ and $B_n=2k$ so $n$ is not squakable. If $n=4k+3$, then $A_n = 2k+2$ and $B_n=2k+1$ so $n$ isn't squakable here either. Thus all odd $n$ are not squakable, completing the proof of our claim.
17.12.2020 16:35
Alireza_Amiri wrote: Call a pair of integers $a$ and $b$ square makers , if $ab+1$ is a perfect square. Determine for which $n$ is it possible to divide the set $\{1,2, \dots , 2n\}$ into $n$ pairs of square makers. Cute Problem though a bit easy!Here is my solution similar to others The answer is all even $n$ work,let $n=2k$ then the following construction verifies this $$[(i\to i+2),(i+1\to i+3)] \;\text{for i from}\; i=1,5,\cdots 4k-3$$Now we prove that such a pairing is not possible when $n$ is odd.Let $n=2k+1$,now we present the following Lemma Lemma :Any number of the form $4m+2$ can be only paired with numbers of form $4t$ Proof : Suppose a number of the form $4m+2$ can be paired with an odd $4c\pm 1$ number, then $4m+2)(4c\pm 1)+1\equiv 3\pmod{4}$ but since $3$ is a non-quadratic Residue modulo $4$ this is a contradiction.$\square$ To finish note that for $n=2k+1$ there are $k+1$ numbers $\equiv 2\mod{4}$ and $k$ numbers $\equiv 0\mod{4}$ and so using the above lemma any $4t+2$ can be only paired with a number of form $4m$ but since $k+1>k$ we cant pair up all $4m+2$ numbers in any case thus we are done.
19.08.2021 21:55
S = {1,2,...,2n} . lets consider 2n = 2 (mod4) . then the count of such numbers that x∈S , x = 2 (mod4) is 1 more than y∈S , y = 0 (mod4) . and it's easy to prove that only y makes a pair with x . so there's a number that won't have any pair . but for 2n = 0 (mod4) every k∈S makes a pair with k+2 so n must be even .
27.11.2022 13:12
Here is my solution: https://calimath.org/pdf/IranMO2020-2-5.pdf And I uploaded the solution with motivation to: https://youtu.be/s-XFhXIrl0g