Let $p$ and $q$ be relatively prime positive odd integers such that $1 < p < q$. Let $A$ be a set of pairs of integers $(a, b)$, where $0 \le a \le p - 1, 0 \le b \le q - 1$, containing exactly one pair from each of the sets $$\{(a, b),(a + 1, b + 1)\}, \{(a, q - 1), (a + 1, 0)\}, \{(p - 1,b),(0, b + 1)\}$$whenever $0 \le a \le p - 2$ and $0 \le b \le q - 2$. Show that $A$ contains at least $(p - 1)(q + 1)/8$ pairs whose entries are both even. Agnijo Banerjee and Joe Benton, United Kingdom
Problem
Source: 2019 RMM Shortlist N1
Tags: number theory, Even
11.08.2020 11:10
Bump! Any solution?
28.01.2021 20:50
Bumping this ugly annoying problem
18.03.2022 04:37
Solved with Jeffrey Chen This problem is equivalent to showing that, the number of $k$ where $k$ is even, $k\% p$ is even, and $k\% q$ is even is at least $\frac{(p-1)(q+1)}{8}$, and the number of $k$ where $k$ is odd, $k\% p$ is even, and $k\%q$ is even is also at least $\frac{(p-1)(q+1)}{8}$. Call a number $x$ with $x\%p, x\%q$ both even as good. Consider the two numbers $0\leq x_1, x_2 < pq$ such that \[x_1 \equiv q-1\mod q, x_1 \equiv p-3 \mod p\]\[x_2 \equiv q-3 \mod q, x_2\equiv p-1\mod p\]and consider the number $X = pq - 1$. Now, let the two positive integers $t_1 = X - x_1, t_2 = X - x_2$. We have \[t_1 \equiv 0\mod q, t_1\equiv 2\mod p\]\[t_2\equiv 2\mod q, t_2\equiv0 \mod p\]Now, $t_1 + t_2\equiv 2\mod p, q$. Since $t_1, t_2$ are positive, are less than $pq$, and are greater than $1$, we must have $t_1 + t_2 = pq + 2$, which is odd. Therefore, one of $t_1, t_2$ is odd, so since $X$ is even, we have one of $x_1, x_2$ are odd. If $x_1$ was odd, then consider the set $S$ of good numbers with the remainders divided by $p,q$ at most the remainders of $x_1$ divided by $p,q$. Then, for each $x \in S$, we have $x_1 - x$ is the opposite parity to $x$, but $x_1 - x$ is still good. Thus, there are the same amount of odd good numbers as even good numbers in $S$, so there are at least $\frac{(p-1)(q+1)}{8}$ good even and good odd numbers. Similarly, if $x_2$ was odd, then there are at least $\frac{(p+1)(q-1)}{8} > \frac{(p-1)(q+1)}{8}$ good even and odd numbers. We conclude the problem.
16.02.2024 15:14
@wack I don't think this is a right solution.