Cup of Combinatorics

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

Cup of Combinatorics

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran TST 2025 Test 4 Problem 2

The post below has been deleted. Click to close.

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

M11100111001Y1R

130 posts

M11100111001Y1R

#1 h May 27, 2025, 7:24 AM • 2 Y

Y by GA34-261, sami1618

There are $n$ cups labeled $1, 2, \dots, n$ , where the $i$ -th cup has capacity $i$ liters. In total, there are $n$ liters of water distributed among these cups such that each cup contains an integer amount of water. In each step, we may transfer water from one cup to another. The process continues until either the source cup becomes empty or the destination cup becomes full.

$a)$ Prove that from any configuration where each cup contains an integer amount of water, it is possible to reach a configuration in which each cup contains exactly 1 liter of water in at most $\frac{4n}{3}$ steps.

$b)$ Prove that in at most $\frac{5n}{3}$ steps, one can go from any configuration with integer water amounts to any other configuration with the same property.

This post has been edited 1 time. Last edited by M11100111001Y1R, May 27, 2025, 7:26 AM

Z K Y

The post below has been deleted. Click to close.

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

50 posts

#2 h May 28, 2025, 8:25 PM

Y by

Part a)
Algorithm 1: Pass all water to the cup with capacity $n$ , and then pass $n-1$ to $n-1$ , and from there $n-2$ to $n-2$ , ..., until you reach $1$ . Total number of moves: #(non-empty cups) + $n-1$ . If the number of non-empty cups is at most $n/3+1$ we are done.
Algorithm 2: While there is an empty cup, pass water to cup $1$ from a cup with at least $2$ liters and from there to the empty cup. If cup $1$ was already full start by passing the water in it to an empty cup. Total number of moves: $2*$ #(empty cups) - 1. Works if number of empty cups is at most $2n/3$ .
One of these algorithms is quick enough to finish the problem.

Z K Y

The post below has been deleted. Click to close.

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

sansgankrsngupta

164 posts

sansgankrsngupta

#3 h May 29, 2025, 8:11 AM • 1 Y

Y by sami1618

OG! Denote by $a \mapsto b$ , a transfer from $a$ -th cup to $b$ -th cup. and $v_a$ be the volume of water in $a$
a) Note that: Each cup contains exactly 1 liter of water $\iff$ No cup is empty.

If at most $\frac{n}{3}$ cups are non-empty, then in atmost $\frac{n}{3}$ transfer all the water to $n$ -th cup,
Now performing the following in order works: $n \mapsto n-1, n-1 \mapsto n-2 \dots 2 \mapsto 1$
If cups are non-empty, then at most cups are empty. We shall now demonstrate that if there is an empty cup, in at most 2 steps we can increase the no. of non-empty cups, thus in at most steps we shall ensure that no cup is empty.
Let the cup with maximal volume of water be $k$ . Since, there is an empty cup, we conclude $v_k>1$ .
Now the step(s) :
- $1 \mapsto b, k \mapsto 1$ (if glass $1$ has water)
- $k \mapsto 1$ (if glass $1$ is empty)
increase(s) the no. of non-empty cups by 1.

b)

If at most $\frac n3$ cups are empty in the final configuration, then first reach the configuration in part a) in atmost $\frac{4n}{3}$ steps. Then from the cups which are destined to empty in the final configuration transfer the 1 liter water to a cup which must be non-empty at the end.
This takes at most $\frac{n}{3}$ further moves and hence at most $\frac{5n}{3}$ moves in total.

This post has been edited 9 times. Last edited by sansgankrsngupta, Jun 4, 2025, 5:16 AM
Reason: -

Z K Y

The post below has been deleted. Click to close.

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

974 posts

#4 h May 29, 2025, 1:47 PM

Y by

Excellent Problem

a) Solution. Let $C$ be the number of non-empty cups at the beginning. We first describe two procedures:

Procedure 1A: Begin by pouring all non-empty cups (other than the $n$ -th cup) into the $n$ -th cup. This takes at most $C$ steps. After this, the $n$ -th cup is full and all the other cups are empty. Then pour the $n$ -th cup into the $(n-1)$ -th cup until the $(n-1)$ -th cup is full. Repeat this by pouring the $(n-1)$ -th cup into the $(n-2)$ -th cup and so on. After $n-1$ of such steps, all cups will have $1$ liter of water.

This procedure takes at most $n+C$ steps (we are being generous).

Procedure 2A: Follow the following algorithm.

If all cups have water, then stop.
If the first cup has water then pour it into a cup that does not have water.
Since the first cup is now empty, pour a cup with at least $2$ liters of water into the first cup.
Repeat.

Each time the algorithm repeats, at most $2$ steps are preformed and the number of cups with water increases by exactly $1$ .

This procedure requires at most $2(n-C)$ steps.

Since $(n+C)+(n+C)+2(n-C)=4n$ , one of these procedures must require at most $4n/3$ steps, as required.
@below

This post has been edited 1 time. Last edited by sami1618, May 29, 2025, 7:26 PM
Reason: tried to make my solution clearer

Z K Y

The post below has been deleted. Click to close.

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

974 posts

#5 h May 29, 2025, 1:48 PM

Y by

b) Solution. Let $C'$ be the number of non-empty cups in the final configuration. We first describe three procedures:

Procedure 1B: Begin by preforming procedure 1A. Then for each cup that is empty in the final configuration, pour it into a cup that needs more water in the final configuration.

This procedure takes at most $2n+C-C'$ steps.

Procedure 2B: Begin by preforming procedure 2A. Then for each cup that is empty in the final configuration, pour it into a cup that needs more water in the final configuration.

This procedure takes at most $3n-2C-C'$ steps.

Procedure 3B: Begin by pouring all cups with water into the $n$ -th cup. This take at most $C$ steps. Then let $c_1<c_2<\dots< c_m$ be all the cups (other then $n$ ) that need water in the final configuration. Suppose they need respective water amounts of $l_1,l_2,\dots,l_m$ liters. Now pour the $n$ -th cup into the $l_m$ -th cup until it becomes full and the pour all the $l_m$ -th cup into the $c_m$ -th cup. Since $l_i\leq c_i$ repeating this process with $c_{m-1}$ and $l_{m-1}$ will not interfere. Thus we can do this for all cups that need water, with at most $2$ moves per cup.

This procedure takes at most $C+2C'$ steps.

Since $(2n+C-C')+(3n-2C-C')+(C+2C')=5n$ , one of these procedures will require at most $5n/3$ steps, as required.

This post has been edited 1 time. Last edited by sami1618, May 29, 2025, 1:51 PM

Z K Y

The post below has been deleted. Click to close.

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

MathematicalArceus

58 posts

MathematicalArceus

#6 h May 29, 2025, 5:59 PM • 1 Y

Y by sami1618

sami1618 wrote:

Excellent Problem

a) Solution. Let $C$ be the number of non-empty cups at the beginning. We first describe two procedures:

Procedure 1A: Begin by pouring all non-empty cups (other than the $n$ -th cup) into the $n$ -th cup. This takes at most $C$ steps. After this, the $n$ -th cup is full and all the other cups are empty. Then pour the $n$ -th cup into the $(n-1)$ -th cup until the $(n-1)$ -th cup is full. Repeat this by pouring the $(n-1)$ -th cup into the $(n-2)$ -th cup and so on. After $n-1$ of such steps, all cups will have $1$ liter of water.

This procedure takes at most $n+C$ steps (we are being generous).

Procedure 2A: Follow the following algorithm.

If all cups have water, then stop.
If the first cup has water then pour it into a cup that does not have water.
Since the first cup is now empty, pour a cup with at least $2$ liters of water into the first cup.
Repeat.

Each time the algorithm repeats, at most $2$ steps are preformed and the number of cups with water increases by exactly $1$ .

This procedure requires at most $2(n-C)$ steps.

Since $2(n+C)+2(n-C)=4n$ , one of these procedures must require at most $4n/3$ steps, as required.

Amusingly, I did all of this, but I still don't get how you got the last line or the finish... Is it because you have 2 algos and 1 default order where everything is filled, and hence you do the $\frac{\text{total}}{3} = \frac{4n}{3}$ ?

This post has been edited 2 times. Last edited by MathematicalArceus, May 29, 2025, 6:37 PM

Z K Y

The post below has been deleted. Click to close.

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

2698 posts

#7 h May 29, 2025, 7:17 PM • 1 Y

Y by sami1618

That's confusing. Think of the number of steps required for algorithm 1A ( $x$ ) and for algorithm 2a ( $y$ ). Since $2x+y \le 2n(n+C) + 2n(n-C) = 4n$ , one of $x$ or $y$ must be under $4n/3$ . If both $x,y \ge 4n/3$ , then the inequality becomes false, which contradicts our observations. This concept is similar to the pigeonhole principle.

This post has been edited 1 time. Last edited by aaravdodhia, May 29, 2025, 7:18 PM

Z K Y

The post below has been deleted. Click to close.

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

MathematicalArceus

58 posts

MathematicalArceus

#8 h May 29, 2025, 7:28 PM

Y by

aaravdodhia wrote:

That's confusing. Think of the number of steps required for algorithm 1A ( $x$ ) and for algorithm 2a ( $y$ ). Since $2x+y \le 2n(n+C) + 2n(n-C) = 4n$ , one of $x$ or $y$ must be under $4n/3$ . If both $x,y \ge 4n/3$ , then the inequality becomes false, which contradicts our observations. This concept is similar to the pigeonhole principle.

ohh yes ! Nice idea, I will keep this in mind! Thanks...

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a