Large and small number

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Large and small number

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2022 Taiwan TST Round 2 Independent Study 2-N

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

528 posts

USJL

#1 h Apr 8, 2022, 4:58 PM

Y by

For any two coprime positive integers $p, q$ , define $f(i)$ to be the remainder of $p\cdot i$ divided by $q$ for $i = 1, 2,\ldots,q -1$ . The number $i$ is called a large number (resp. small number) when $f(i)$ is the maximum (resp. the minimum) among the numbers $f(1), f(2),\ldots,f(i)$ . Note that $1$ is both large and small. Let $a, b$ be two fixed positive integers. Given that there are exactly $a$ large numbers and $b$ small numbers among $1, 2,\ldots , q - 1$ , find the least possible number for $q$ .

Proposed by usjl

This post has been edited 2 times. Last edited by USJL, Jun 24, 2022, 5:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

196 posts

#2 h Apr 9, 2022, 5:23 AM

Y by

I believe the answer is ab+1. We induct on p+q.
Let h(p,q) be the number of minimal integers in 1,2,...,q-1
Let g(p,q) be the number of maximal integers in 1,2,...,q-1
Let s(p,q)=h(p,q)g(p,q). We will prove that s(p,q)<=q-1 for all p,q.
If p>q/2 then s(p,q)=s(q-p,q) then induct.
If p<q/2 let q=kp+r where k>=2.
It is easy to see that g(p,kp+r)=g(p,p+r)+k-1 and h(p,kp+r)=h(p,p+r)
It is easy to see that h(p,kp+r)<=p for all p,k,r
Finally s(p,kp+r)=s(p,p+r)+(k-1)h(p,p+r)<=p+r-1+(k-1)(p+r)=kp+r-1, done.
Please tell me if there is something wrong.

This post has been edited 5 times. Last edited by Justanaccount, Apr 9, 2022, 7:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#3 h Apr 9, 2022, 6:51 AM

Y by

Throughout the solution, let $m,n$ replace $p,q$ and $\gcd(m,n)=1$ . Let $R(x,y)$ denote the unique integer in $[0,y)$ st $y\mid x-R(x,y)$

The answer is $ab+1$ . Construction: $m=b, n=ab+1$ .

Let $a(m,n)$ denote the number of "peaks" (we'll use peaks instead of large numbers) in $R(mt,n)$ as $t$ goes from $1$ to $n-1$ . For convenience, $a(m,n)=a(m-n,n)$ . Let $b(m,n)$ denote the number of valleys (we'll use valleys instead of large numbers) in $R(mt,n)$ , as $t$ goes over $1$ to $n-1$ . Observe $R(mt,n)+R(-mt,n)=n$ so if $t$ is a peak in the sequence $R(mt,n)$ , it must be a valley in the sequence $R(-mt,n)$ , and vice versa.

Claim: Suppose $0<m<\frac n2$ . We have $a(-m,n)=a(-m,n-m)$ and $a(m,n)=a(m,n-m)+1$ .

Proof: We first prove $a(m,n)=a(m,n-m)+1$ . To prove this, we note $t=1,\cdots,\lfloor \frac nm \rfloor$ are all peaks. Let $S_t=\{x| x\equiv t(\bmod\; m)\}$ . If I consider the sequence of $R(mt,n)$ as $t$ goes from $1$ to $n-1$ , I can see I traverse $S_0, S_{-n}, S_{-2n}, \cdots$ in this order and go through each $S_i$ in ascending order. There is at most one peak in each of $S_{-n}, S_{-2n}, \cdots$ and moreover these peaks don't depend on $n$ as long as $n (\bmod\; m)$ is fixed.

The proof for $a(-m,n)=a(-m,n-m)$ is analogous; notice we go through each $S_j$ in descending order, and each $|S_j|\ge 2$ so I can remove one element from each.

Now we proceed by strong induction on $a+b$ to prove that the answer for $a,b$ is $ab+1$ . The base case, $(1,1)$ is trivial. Let $f(a,b)$ denote our answer. Note $f(b,a)=f(a,b)$ because if $a(m,n)=a, b(m,n)=b$ then it must follow $a(-m,n)=b, b(-m,n)=a$ .

Suppose $m$ satisfies $a(m,f(a,b))=a, b(m,f(a,b))=b$ . Suppose $m<\frac{f(a,b)}{2}$ or we replace $m$ with $-m$ and focus on $f(b,a)=f(a,b)$ . In this case, $m\ge b$ because the number of valleys is at most $m$ because only $1,\cdots,m$ are eligible to be valleys. Therefore, $f(a,b)-m$ satisfies $a(m,f(a,b)-m)=a-1, b(m,f(a,b)-m)=b$ , so $f(a,b)\ge m+f(a-1,b)\ge b+(a-1)b+1=ab+1$ , completing the induction.

This post has been edited 2 times. Last edited by CANBANKAN, Apr 18, 2022, 3:40 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a