Let be given $n$ positive integer. Lets write with $a_n$ the number of positive integer pairs $(x,y)$ such that $x+y$ is even and $1\leq x\leq y\leq n$. Lets write with $b_n$ the number of positive integer pairs $(x,y)$ such that $x+y\leq n+1$ and $1\leq x\leq y\leq n$.
Problem
Source: Kosovo Mathematical Olympiad 2022, Grade 12, Problem 2
Tags: combinatorics
07.03.2022 17:37
Let $U_n$ be the set of pairs of first kind (hence $|U_n|=a_n$) and $V_n$ be the set of pairs of second kind (hence $|V_n|=b_n$). Induct on $n$. Verify $n\le 3$ by hand. Assume $a_n=b_n$. Note that \[ U_{n+1}\setminus U_n =\bigl\{1\le x\le n+1:x+n+1\equiv 0\pmod{2}\bigr\} \]since if $y\le n$ then $(x,y)\in U_n$ already. From here, we find $a_{n+1}-a_n = \lceil \frac{n+1}{2}\rceil$. Next, \[ V_{n+1}\setminus V_n = \bigl\{1\le x\le y\le n:x+y=n+2\bigr\}\cup\{(1,n+1)\}. \]Indeed, if $y=n+1$ then $(x,y)=(1,n+1)$ is the only pair in $V_{n+1}$; whereas for $y\ne n$ if $x+y\le n+1$ then $(x,y)\in V_n$. We easily see that \[ \Bigl|\bigl\{1\le x\le y\le n:x+y=n+2\bigr\}\Bigr| = \left\lceil \frac{n-1}{2}\right\rceil, \]which yields $b_{n+1}-b_n=a_{n+1}-a_n$. As $a_n=b_n$ by inductive hypothesis, the proof is complete.
09.03.2022 12:28
Let $A_n$ be the set of pairs counted by $a_n$ and let $B_n$ be the set of pairs counted by $b_n$. Notice that $(x, y)\mapsto ((y-x+2)/2, (x+y)/2)$ is an injection $A_n\to B_n$, so $a_n\leq b_n$. Also notice that $(x, y)\mapsto (y-x+1, x+y-1)$ is an injection $B_n\to A_n$, hence $a_n = b_n$.