Competition problem — Number theory

Library / /497 of 520

Number theory Difficulty 6.0 National olympiad Prove it

1. Let the function $y=f(x)$ be continuous and non-negative on $[a, b]$ , and the sum $\sum_{a<t \leqslant b}[f(t)]$ (where $t$ is an integer in $[a, b]$ ) represents the number of integer points in the plane region $a<x \leqslant b, 0<y \leqslant f(x)$ . Prove: If $(p, q)=1$ , then the number of integer points in the rectangular region $\left(0, \frac{q}{2}\right] \times\left(0, \frac{p}{2}\right]$ is equal to
$\sum_{0<x \leqslant \frac{q}{2}}\left[\frac{p}{q} x\right]+\sum_{0<y \leqslant \frac{p}{2}}\left[\frac{q}{p} y\right]=\frac{p-1}{2} \cdot \frac{q-1}{2}$

Solution

Prompt: As shown in Figure 2, calculate the number of elements in
$\begin{aligned} M= & \left\{p x-q y \mid x=1,2, \cdots, \frac{q-1}{2} ;\right. \\ & \left.y=1,2, \cdots, \frac{p-1}{2}\right\} \end{aligned}$
in two ways.
On one hand, when $x$ runs through $1,2, \cdots, \frac{q-1}{2}$ and $y$ runs through $1, 2, \cdots, \frac{p-1}{2}$ , $p x - q y$ runs through $\frac{p-1}{2} \cdot \frac{q-1}{2}$ numbers.

On the other hand, any number in $M$ is not zero, and any two numbers are not equal.
Furthermore, the positive numbers in $M$ are
$\sum_{x=1}^{q-1}\left[\frac{p}{q} x\right]=\sum_{0<x \leq \frac{q}{2}}\left[\frac{p}{q} x\right] \text { (numbers), }$
and the negative numbers are
$\sum_{y=1}^{p-1}\left[\frac{p}{q} y\right]=\sum_{0<y \leq \frac{p}{2}}\left[\frac{q}{p} y\right] \text { (numbers). }$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.