Sweet sweet combo

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

Sweet sweet combo

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Izho 2025 problem 4

The post below has been deleted. Click to close.

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

9 posts

Ciobi_

#1 h Jan 15, 2025, 9:53 AM • 1 Y

Y by alexanderhamilton124

Vaysha has a board with $999$ consecutive numbers written and $999$ labels of the form "This number is not divisible by $i$ ", for $i \in \{ 2,3, \dots ,1000 \}$ . She places each label next to a number on the board, so that each number has exactly one label. For each true statement on the stickers, Vaysha gets a piece of candy. How many pieces of candy can Vaysha guarantee to win, regardless of the numbers written on the board, if she plays optimally?

This post has been edited 1 time. Last edited by Ciobi_, Jan 15, 2025, 4:08 PM
Reason: Miswrote what the labels said

Z K Y

The post below has been deleted. Click to close.

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

42 posts

#2 h Jan 15, 2025, 10:10 AM

Y by

is time up?

Z K Y

The post below has been deleted. Click to close.

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

1199 posts

#3 h Jan 15, 2025, 10:16 AM

Y by

Are you sure that the labels are "this number is divisible by $i$ "? I think they should be "this number is not divisible by $i$ "?

This post has been edited 2 times. Last edited by Assassino9931, Jan 15, 2025, 10:19 AM

Z K Y

The post below has been deleted. Click to close.

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

54 posts

#4 h Jan 15, 2025, 10:22 AM

Y by

The question was "this number is not divisible by $i$ "

Z K Y

The post below has been deleted. Click to close.

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

1199 posts

#5 h Jan 15, 2025, 12:15 PM

Y by

Hmm, straightforward once you realize russian-and-neighbours easy problems like concrete numbers on which you should induct?

Suppose the cards are $n\geq 1$ , from $2$ to $n+1$ . Then in a sequence starting with LCM $(2,3,\ldots,n,n+1)$ one cannot get a candy from the starting number, as it is divisible by each label of a card, so the candies are at most $n-1$ in this case. For the bound, note that $n-1\geq 0$ points are vacuously obtained in the base case $n=1$ . In general for $n\geq 2$ , in a sequence $a+1, a+2, \ldots, a+n$ at most one of the numbers $a+1$ and $a+n$ is divisible by $n+1$ (as their difference is $n-1$ and $n+1$ does not divide $n-1$ for $n\geq 2$ ), so we put the card with $n+1$ in the other number, then consider the remaining sequence of $n-1$ consecutive numbers with cards from $2$ to $n$ , where by the inductive hypothesis we can obtain at least $n-2$ points.

Comment on the version with is divisible by i

This post has been edited 4 times. Last edited by Assassino9931, Jan 15, 2025, 12:31 PM

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

379 posts

alexanderhamilton124

#6 h Jan 15, 2025, 12:49 PM • 1 Y

Y by dhfurir

I am just reposting my solution from the other thread. Nice n easy problem

my solution

This post has been edited 1 time. Last edited by alexanderhamilton124, Jan 15, 2025, 12:51 PM

Z K Y

The post below has been deleted. Click to close.

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

9 posts

Ciobi_

#7 h Jan 15, 2025, 4:09 PM

Y by

p.lazarov06 wrote:

The question was "this number is not divisible by $i$ "

Thanks. I edited it now.

Z K Y

The post below has been deleted. Click to close.

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

171 posts

#8 h Jan 17, 2025, 9:12 PM

Y by

Assassino9931 wrote:

Comment on the version with is divisible by i

Wait, did you solve this version of the problem? If positive, can you please DM me the solution?

Z K Y

The post below has been deleted. Click to close.

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

668 posts

#9 h Jan 18, 2025, 11:05 AM

Y by

Answer is $998$ . If one picks the numbers as $1000!,\dots,1000!+998$ then Vaysha cannot label each number. Let's show that Vaysha can guarantee $998$ labelings. Since the difference between the least and most number is $998$ , at lesat one of the largest or smallest integer on the board is not divisible by $1000$ , Vaysha labels that number with $1000$ . If the difference between the largest and smallest number is $k$ , then Vaysha labels one of them (if both of them are not divisible by $k+2$ , then Vaysha chooses one of them randomly) with $k+2$ until the difference is $1$ . At least one of them is not divisible by $3$ and Vaysha labels $3$ which guarantees $998$ as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

31 posts

Hertz

#10 h Jan 18, 2025, 4:47 PM

Y by

replace 999 with n and let the n consecutive numbers be $m+2, m+3, ... , m+n+1$ . now we will show with induction that answer is $n-1$ .

it's simple to obtain in base case $n=3$ that you can get a minimum of 2 candies

now let $n-1$ be minimum amount of candies you can obtain from $n$ . now added number on the board is $m+n+2$ and an added label is "this number is not divisible by $n+2$ ".

if $n+2 \nmid m+n+2$ , then place that label under $m+n+2$ and we will get an extra candy giving us a minimum of $(n+1)-1 = n$ candies.

if $n+2 \mid m+n+2 \Longrightarrow n+2 \mid m$ , and we split it in two cases:

Case I - the number of candies we had was $n$ , after which we still put $n+2$ next to $m+n+2$ and have $(n+1)-1 = n$ candies

Case II - the number of candies we had before was $n-1$ , then we have a number $x$ and number $m+a$ , such that $x \mid m+a$ . now we swap $x$ and $n+2$ . since $n+2 \mid m$ and $n+2 \leq a$ we get $n+2 \nmid m+a$ , so we have $(n-1) + 1 = n$ candies.

showing that $n-1$ occurs is easy. if $(n+1)!$ is in one of these $n$ consecutive integers, then any of the $n+1$ labels divides it, hence leaving us with a maximum of $n-1$ candies.

Z K Y

The post below has been deleted. Click to close.

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

9 posts

#11 h Jan 22, 2025, 6:56 AM

Y by

Assume our numbers are $a+1,a+2,a+3,...,a+999$ . One of $a+1$ and $a+2$ is not divisible by 2, so let's put first label on that, then one of $a+1,a+2,a+3$ is occupied so we have two empty numbers from them and one of them is not divisible by 3 so let's put 2nd label on that, and so on for k, k-2 numbers occupied from $a+1,a+2,a+3,...,a+k$ so there is 2 number which there is not label on them and one of them is not divisible by k so let's put (k-1)th label on that. So with same strategy we can put 998 label true and we take at least 998 candies. And example for we can't take candy for 999th label everytime is let our numbers start from $1000!$ so we can't take any candies from that. So problem is solved.

This post has been edited 1 time. Last edited by Begli_I., Jan 22, 2025, 6:56 AM

Z K Y

The post below has been deleted. Click to close.

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

66 posts

Haris1

#12 h Mar 24, 2025, 7:28 PM

Y by

Hmm I'm mistaking something or is it this easy we have $\lceil 999-\frac{999}{k}\rceil$ choices for some integer $k$ we can see that this decrease as $k$ decreases worst case scenario we have $k=2$ which has only $500$ choices. If we start from $2$ and move upward s.t we get $1$ candy per card we place if we say that per move of card place we take places of others. We know that moves for number $998$ and smaller are always positive because at first we have 500 and then for $k>500$ its easy to see $\lceil 999-\frac{999}{k} \rceil$ - $k$ is positive for $k=997,...,1$ however when we place $998$ card we see that for $k=998$ the last number can or can't be included so we have at least $998$ candies. For the case when the sequence of $999$ numbers include $1000!$ we can see that it isn't possible to have more than $998$ . So we can guarantee $998$ candies.

This post has been edited 1 time. Last edited by Haris1, Mar 24, 2025, 7:37 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a