numbers on a blackboard

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

numbers on a blackboard

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2023 HMIC P4

The post below has been deleted. Click to close.

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

1032 posts

#1 h Apr 25, 2023, 1:55 AM • 1 Y

Y by PikaPika999

Let $n>1$ be a positive integer. Claire writes $n$ distinct positive real numbers $x_1, x_2, \dots, x_n$ in a row on a blackboard. In a $\textit{move},$ William can erase a number $x$ and replace it with either $\tfrac{1}{x}$ or $x+1$ at the same location. His goal is to perform a sequence of moves such that after he is done, the number are strictly increasing from left to right.

Prove that there exists a positive constant $A,$ independent of $n,$ such that William can always reach his goal in at most $An \log n$ moves.
Prove that there exists a positive constant $B,$ independent of $n,$ such that Claire can choose the initial numbers such that William cannot attain his goal in less than $Bn \log n$ moves.

Z K Y

The post below has been deleted. Click to close.

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

3441 posts

#2 h Apr 25, 2023, 9:20 PM • 1 Y

Y by PikaPika999

Off topic question - how did participants get invitations to HMIC? I got top 50 at february, but I never got any email or anything about the HMIC

This post has been edited 1 time. Last edited by ihatemath123, Apr 25, 2023, 9:20 PM

Z K Y

The post below has been deleted. Click to close.

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

223 posts

#3 h Apr 26, 2023, 12:40 AM • 1 Y

Y by PikaPika999

(a) Divide and conquer. Put the first half of the numbers in decreasing order, add $1$ to all of them, then take reciprocals so that they form an increasing sequence of numbers below $1$ . Put the second half of the numbers in increasing order, and add $1$ to all of them so that they form an increasing sequence of numbers above $1$ . We have the recurrence $T(n)=2T(n/2)+O(n)$ so $T(n) = O(n\log n)$ .

(b) If we operate on a single number $x$ , the reachable numbers are of the form $\frac{ax+b}{cx+d}$ where $a, b, c, d\in \mathbb{Z}_{\geq 0}$ and $ad-bc=\pm 1$ . Ignore all tuples $(a, b, c, d)$ not reachable within $n\log n$ steps, leaving finitely many choices. If we make all $x_i$ and all differences $\lvert x_i-x_j\rvert$ sufficiently large, then the final numbers will be sorted according to the tuple $(a/c, -(ad-bc), (ad-bc)x)$ . (I'm not showing all the details here but it's fairly straightforward.) This implies all occurrences of the pair $(a/c, -(ad-bc))$ occur consecutively in the final array. Finally, we add the condition $x_1 > x_2 < x_3 > x_4 < \dotsb$ . This means no three consecutive numbers are in ascending or descending order, so no tuple $(a, b, c, d)$ can appear more than twice. Therefore there are at least $n/2$ distinct tuples $(a, b, c, d)$ being used. The sum of the distances of the closest reachable tuples is $\Omega(n\log n)$ due to the bounded degree, which solves the problem.

Z K Y

The post below has been deleted. Click to close.

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

3 posts

#4 h Apr 8, 2024, 11:59 AM • 1 Y

Y by PikaPika999

Master’s theorem

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1692 posts

awesomeming327.

#5 h Apr 6, 2025, 12:10 AM • 1 Y

Y by PikaPika999

Reindex to $0$ . We note that one main roadblock is that the $+1$ operation quickly becomes expensive as numbers get big, so we begin with a crucial claim:

Claim 1:
It is possible to transform any sequence $x_0, x_1, \dots , x_{n-1}$ into $y_0, y_1, \dots , y_{n-1}$ such that $x_i<x_j\iff y_i<y_j$ and $y_i\le 1$ for all $i$ in $4n$ moves. We shall call this operation $Z$ .

To each term we apply the following sequence of four moves:
$x_i\to x_i+1\to \frac{1}{x_i+1}\to \frac{x_i+2}{x_i+1}\to \frac{x_i+1}{x_i+2}=y_i$ One can easily verify that both conditions are satisfied.

Now, let $2^{k-1}<n\le 2^{k}$ . If $n<2^k$ we can imagine $x_{n}, x_{n+1}, \dots, x_{2^k-1}$ and simply discard them at the end of the problem. Therefore, we proceed with the problem on the case $n=2^k$ for some $k$ .

Suppose we can complete the task for $2^{k-1}$ in some $P(k-1)$ moves. Then complete the task for the first $2^{k-1}$ numbers and then for the last $2^{k-1}$ . We have used $2P(k-1)$ moves. Next, apply $Z$ , using $2^{k+2}$ moves. Now, if the first number of the last $2^{k-1}$ is less than or equal to the last number of the first $2^{k-1}$ , we add one to each term in the last $2^{k-1}$ , using at most $2^{k-1}$ moves. After this, we are done. We therefore have $P(k)\le 2P(k-1)+5\cdot 2^{k-1}$ . Now if $P(k-1)\le 5k\cdot 2^{k-2}$ then $P(k)\le 5(k)\cdot 2^{k-1}+5\cdot 2^{k-1}=5(k+1) \cdot 2^{k-1}$ . Note that $P(1)\le 2$ because we can invert both numbers so $P(1)\le 5\cdot 2^{-1}$ so we have for all $k$ ,
$P(k)\le 2.5 k\cdot 2^k$ Part B is incorrect because of a reading error

This post has been edited 2 times. Last edited by awesomeming327., Apr 6, 2025, 1:12 AM

Z K Y

The post below has been deleted. Click to close.

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

2956 posts

#6 h Apr 6, 2025, 4:17 AM

Y by

awesomeming327. wrote:

Reindex to $0$ . We note that one main roadblock is that the $+1$ operation quickly becomes expensive as numbers get big, so we begin with a crucial claim:

Claim 1:
It is possible to transform any sequence $x_0, x_1, \dots , x_{n-1}$ into $y_0, y_1, \dots , y_{n-1}$ such that $x_i<x_j\iff y_i<y_j$ and $y_i\le 1$ for all $i$ in $4n$ moves. We shall call this operation $Z$ .

To each term we apply the following sequence of four moves:
$x_i\to x_i+1\to \frac{1}{x_i+1}\to \frac{x_i+2}{x_i+1}\to \frac{x_i+1}{x_i+2}=y_i$ One can easily verify that both conditions are satisfied.

Now, let $2^{k-1}<n\le 2^{k}$ . If $n<2^k$ we can imagine $x_{n}, x_{n+1}, \dots, x_{2^k-1}$ and simply discard them at the end of the problem. Therefore, we proceed with the problem on the case $n=2^k$ for some $k$ .

Suppose we can complete the task for $2^{k-1}$ in some $P(k-1)$ moves. Then complete the task for the first $2^{k-1}$ numbers and then for the last $2^{k-1}$ . We have used $2P(k-1)$ moves. Next, apply $Z$ , using $2^{k+2}$ moves. Now, if the first number of the last $2^{k-1}$ is less than or equal to the last number of the first $2^{k-1}$ , we add one to each term in the last $2^{k-1}$ , using at most $2^{k-1}$ moves. After this, we are done. We therefore have $P(k)\le 2P(k-1)+5\cdot 2^{k-1}$ . Now if $P(k-1)\le 5k\cdot 2^{k-2}$ then $P(k)\le 5(k)\cdot 2^{k-1}+5\cdot 2^{k-1}=5(k+1) \cdot 2^{k-1}$ . Note that $P(1)\le 2$ because we can invert both numbers so $P(1)\le 5\cdot 2^{-1}$ so we have for all $k$ ,
$P(k)\le 2.5 k\cdot 2^k$ Part B is incorrect because of a reading error

very nice! :10:

:10:

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a