Kvant Math Problem 567

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m47s
Source on kvant.digital

Problem

The natural numbers $p$ and $q$ are relatively prime. The segment $[0;1]$ is divided into $p+q$ equal segments. Prove that each of these segments, except for the two end ones, contains exactly one of the $p+q-2$ numbers $$\dfrac1p,\quad\dfrac2p,\quad\ldots,\quad\dfrac{p-1}p,\quad \dfrac1q,\quad\dfrac2q,\quad\ldots,\quad\dfrac{q-1}q.$$

A. A. Egorov

13th All-Union School Students' Olympiad, Grade 9

Exploration

Take a small example, say $p=2$, $q=3$. Then $p+q=5$, and the interval $[0,1]$ is divided into

$$\left[0,\frac15\right],\ \left[\frac15,\frac25\right],\ \left[\frac25,\frac35\right],\ \left[\frac35,\frac45\right],\ \left[\frac45,1\right].$$

The numbers are

$$\frac12,\ \frac13,\ \frac23.$$

Indeed,

$$\frac13\in\left(\frac15,\frac25\right),\qquad \frac12\in\left(\frac25,\frac35\right),\qquad \frac23\in\left(\frac35,\frac45\right),$$

so each interior segment contains exactly one of them.

The statement suggests that the fractions with denominator $p$ and those with denominator $q$ never fall into the same small interval. Since the interval length is $1/(p+q)$, it is natural to compare the distance between two such fractions with $1/(p+q)$.

For two fractions of the same family,

$$\frac{k+1}{p}-\frac{k}{p}=\frac1p>\frac1{p+q},$$

and similarly for denominator $q$. Hence two fractions with the same denominator cannot lie in one small interval.

The crucial point is the mixed case. Suppose

$$\frac{a}{p},\qquad \frac{b}{q}$$

belong to the same interval. Then

$$\left|\frac{a}{p}-\frac{b}{q}\right|<\frac1{p+q}.$$

Since $p$ and $q$ are coprime,

$$\frac{a}{p}-\frac{b}{q} =\frac{aq-bp}{pq},$$

and if the fractions are distinct then $|aq-bp|\ge1$. Hence

$$\left|\frac{a}{p}-\frac{b}{q}\right| \ge\frac1{pq}.$$

This lower bound is not enough, because $1/pq$ may be smaller than $1/(p+q)$. A stronger observation is needed.

Assume the two fractions lie in the same interval between consecutive points $m/(p+q)$ and $(m+1)/(p+q)$. Then

$$m<\frac{(p+q)a}{p}<m+1, \qquad m<\frac{(p+q)b}{q}<m+1.$$

Since

$$\frac{(p+q)a}{p}=a+\frac{aq}{p},$$

the integer part is determined by $\frac{aq}{p}$. Likewise for $\frac{bp}{q}$. This hints that the residues $aq\bmod p$ and $bp\bmod q$ may be relevant.

A counting argument is also attractive. There are exactly

$$(p-1)+(q-1)=p+q-2$$

fractions and exactly $p+q-2$ interior intervals. If one proves that no interior interval contains more than one fraction, it remains only to show that every fraction lies in an interior interval, and then counting forces each interior interval to contain exactly one fraction.

The step most likely to hide an error is proving that two fractions with different denominators cannot belong to the same interval.

Problem Understanding

We divide $[0,1]$ into $p+q$ equal subintervals

$$\left[\frac{m}{p+q},\frac{m+1}{p+q}\right], \qquad m=0,1,\dots,p+q-1,$$

where $p$ and $q$ are coprime positive integers. We must prove that every interior subinterval, namely those with

$$m=1,2,\dots,p+q-3,$$

contains exactly one number from the set

$$\left{\frac1p,\dots,\frac{p-1}{p}, \frac1q,\dots,\frac{q-1}{q}\right}.$$

This is a Type B problem. The core difficulty is to show that no interior subinterval can contain two such fractions. Once that is established, the numbers of fractions and interior subintervals coincide, so counting completes the argument.

Proof Architecture

First, prove that every listed fraction lies in an interior subinterval. This follows because all listed fractions are strictly between $0$ and $1$.

Second, prove that no endpoint $m/(p+q)$ of the subdivision coincides with any listed fraction. If $a/p=m/(p+q)$, then $p+q$ divides $aq$; since $(p,p+q)=1$, this forces $p+q\mid a$, impossible because $0<a<p<p+q$. The argument for denominator $q$ is analogous.

Third, prove that two fractions with denominator $p$ cannot lie in the same subinterval, and similarly for denominator $q$. Consecutive such fractions are separated by $1/p$ or $1/q$, both larger than $1/(p+q)$.

Fourth, prove that a fraction $a/p$ and a fraction $b/q$ cannot lie in the same subinterval. If they do, then

$$\left\lfloor \frac{(p+q)a}{p}\right\rfloor = \left\lfloor \frac{(p+q)b}{q}\right\rfloor .$$

After subtracting the integer parts $a$ and $b$, this yields

$$\left\lfloor \frac{aq}{p}\right\rfloor = \left\lfloor \frac{bp}{q}\right\rfloor .$$

Since $aq$ is not divisible by $p$ and $bp$ is not divisible by $q$, the two fractional parts are nonzero. Writing

$$\frac{aq}{p}=r+\alpha,\qquad \frac{bp}{q}=r+\beta,$$

with $0<\alpha,\beta<1$, one obtains

$$aq-bp=p\alpha-q\beta.$$

The right-hand side lies strictly between $-q$ and $p$. Because $aq-bp$ is an integer, divisibility considerations force $aq-bp=0$, contradicting the distinctness of the fractions.

A cleaner route is to show that the map sending each fraction to the index of its subinterval is injective. Since the number of fractions equals the number of interior intervals, injectivity implies bijectivity.

The hardest step is proving injectivity in the mixed case.

Solution

Let

$$I_m=\left[\frac{m}{p+q},\frac{m+1}{p+q}\right], \qquad m=0,1,\dots,p+q-1.$$

The intervals $I_0$ and $I_{p+q-1}$ are the two end intervals. There are exactly

$$p+q-2$$

interior intervals.

The given set consists of

$$(p-1)+(q-1)=p+q-2$$

numbers.

Every number of the form $a/p$ with $1\le a\le p-1$ satisfies

$$0<\frac ap<1,$$

and every number of the form $b/q$ with $1\le b\le q-1$ satisfies

$$0<\frac bq<1.$$

Hence each of these numbers belongs to one of the interior intervals unless it coincides with a subdivision point $m/(p+q)$.

We show that this never happens.

Assume

$$\frac ap=\frac{m}{p+q}$$

for some $1\le a\le p-1$. Then

$$a(p+q)=mp.$$

Reducing modulo $p$ gives

$$aq\equiv0\pmod p.$$

Since $(p,q)=1$, it follows that $a\equiv0\pmod p$. Because $1\le a\le p-1$, this is impossible. Thus no fraction $a/p$ is a subdivision point. The same argument with $p$ and $q$ exchanged shows that no fraction $b/q$ is a subdivision point.

Consequently every one of the $p+q-2$ fractions lies in a unique interior interval.

Now suppose two fractions from the given set lie in the same interval $I_m$. We shall derive a contradiction.

Two fractions with denominator $p$ cannot lie in the same interval, because distinct such fractions differ by at least

$$\frac1p>\frac1{p+q},$$

while the length of $I_m$ is $1/(p+q)$.

Similarly, two fractions with denominator $q$ cannot lie in the same interval.

It remains to exclude the mixed case. Assume

$$\frac ap,\qquad \frac bq$$

belong to the same interval $I_m$. Then

$$m<\frac{(p+q)a}{p}<m+1, \qquad m<\frac{(p+q)b}{q}<m+1,$$

because neither fraction is an endpoint of the interval.

Hence

$$\left\lfloor \frac{(p+q)a}{p}\right\rfloor = \left\lfloor \frac{(p+q)b}{q}\right\rfloor .$$

Since

$$\frac{(p+q)a}{p} = a+\frac{aq}{p}, \qquad \frac{(p+q)b}{q} = b+\frac{bp}{q},$$

we obtain

$$a+\left\lfloor\frac{aq}{p}\right\rfloor = b+\left\lfloor\frac{bp}{q}\right\rfloor . \tag{1}$$

Because $(p,q)=1$ and $1\le a\le p-1$, the number $aq/p$ is not an integer. Likewise $bp/q$ is not an integer. Therefore

$$\left\lfloor\frac{aq}{p}\right\rfloor = \frac{aq-r}{p}, \qquad \left\lfloor\frac{bp}{q}\right\rfloor = \frac{bp-s}{q},$$

where

$$r\in{1,\dots,p-1},\qquad s\in{1,\dots,q-1}$$

are the remainders of $aq$ modulo $p$ and $bp$ modulo $q$.

Substituting into (1) and multiplying by $pq$ gives

$$apq+q(aq-r) = bpq+p(bp-s).$$

After rearrangement,

$$(a-b)pq+(aq-bp)(p+q) = qr-ps. \tag{2}$$

The left-hand side of (2) is divisible by $p+q$, hence so is the right-hand side.

Since

$$1\le r\le p-1,\qquad 1\le s\le q-1,$$

we have

$$-(p+q)+1 < qr-ps < (p+q)-1.$$

The only multiple of $p+q$ in this interval is $0$. Thus

$$qr-ps=0.$$

Because $(p,q)=1$, this implies $p\mid r$. But $1\le r\le p-1$, a contradiction.

Hence a fraction with denominator $p$ and a fraction with denominator $q$ cannot belong to the same interval.

We have proved that no interior interval contains more than one of the given fractions. Since there are exactly $p+q-2$ fractions and exactly $p+q-2$ interior intervals, and every fraction belongs to an interior interval, each interior interval contains exactly one of the given fractions.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is showing that none of the fractions coincides with a subdivision point. From

$$\frac ap=\frac{m}{p+q}$$

we obtain

$$a(p+q)=mp.$$

Reducing modulo $p$ yields $aq\equiv0\pmod p$. Coprimality of $p$ and $q$ gives $a\equiv0\pmod p$, impossible because $1\le a\le p-1$. The argument uses coprimality essentially; without it, coincidences can occur.

The second delicate point is the mixed case. Equality of interval indices gives equality of the floors. The danger is to conclude too quickly that the fractions themselves are equal. Instead, one must translate the floor equality into the arithmetic relation (2), then exploit the bounds on the remainders. The estimate

$$-(p+q)+1<qr-ps<(p+q)-1$$

is the crucial numerical input. It forces a multiple of $p+q$ to be zero.

A third place where an error could occur is the counting step. The proof first establishes that every listed fraction lies in some interior interval and that no interior interval contains two fractions. Only after both facts are proved does counting imply that every interior interval contains exactly one fraction.

Alternative Approaches

A more conceptual proof labels each interior interval by its index $m$. For a fraction $a/p$, the interval containing it is determined by

$$m=\left\lfloor \frac{(p+q)a}{p}\right\rfloor = a+\left\lfloor\frac{aq}{p}\right\rfloor .$$

As $a$ runs through $1,\dots,p-1$, these indices are all distinct. The analogous statement holds for fractions $b/q$. One then proves directly that the two sets of indices are disjoint. Since together they contain $(p-1)+(q-1)=p+q-2$ elements, they must be exactly the set of all interior interval indices.

Another approach uses lattice points. The fractions $a/p$ and $b/q$ correspond to lattice points on the sides of the rectangle $[0,p]\times[0,q]$. Coprimality implies that the diagonal from $(0,0)$ to $(p,q)$ contains no interior lattice points. The interval decomposition corresponds to slicing the diagonal into $p+q$ equal parts, and the desired statement becomes a geometric reformulation of the fact that the diagonal crosses each interior strip exactly once. The arithmetic proof above is shorter and stays entirely within elementary number theory.