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?
Problem
Source: Izho 2025 problem 4
Tags: izho, number theory, combinatorics
Titibuuu
15.01.2025 13:10
is time up?
Assassino9931
15.01.2025 13:16
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$"?
p.lazarov06
15.01.2025 13:22
The question was "this number is not divisible by $i$"
Assassino9931
15.01.2025 15:15
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.
Quite difficult and not appropriate for a competition maybe, e.g. in [1001, 1999] there are a lot of primes which we can't even count by hand, and from each of these we cannot gain a point.
alexanderhamilton124
15.01.2025 15:49
I am just reposting my solution from the other thread. Nice n easy problem
The answer is $998$. First, note that $999$ is not possible by considering $1000!, 1000! + 1, \dots, 1000! + 998$. Obviously, $1000!$ will receive a number and it's divisible by $2, 3, \dots, 999, 1000$, so we won't get a candy for this statement. Hence $999$ candies is impossible.
Consider any $999$ consecutive numbers, $x, x + 1, \dots, x + 998$. Note that $999$ can't divide both $x$, $x + 998$, so we may assign $999$ to one of $x$ and $x + 998$. Now we have $998$ consecutive numbers, call these $y, y + 1, \dots, y + 997$. Note that $998$ can't divide both $y$ and $y + 997$, so we can assign $998$ to one of them. Continuing like this, we eventually reach three consecutive numbers that don't have a number assigned, call these $z, z + 1, z + 2$, and we have $2, 3, 1000$ left to assign. Note that $3$ can't divide both $z$ and $z + 2$, so assign $3$ to one of them (WLOG $z + 2$). Then, we have $2, 1000$ left and $z, z + 1$ unassigned. $2$ can't divide both $z$ and $z + 1$ so assign $2$ to the one that isn't divisible by $2$, and assign $1000$ to the one that's left, and we have at least $998$ candies.
Ciobi_
15.01.2025 19:09
p.lazarov06 wrote: The question was "this number is not divisible by $i$" Thanks. I edited it now.
atdaotlohbh
18.01.2025 00:12
Assassino9931 wrote:
Quite difficult and not appropriate for a competition maybe, e.g. in [1001, 1999] there are a lot of primes which we can't even count by hand, and from each of these we cannot gain a point.
Wait, did you solve this version of the problem? If positive, can you please DM me the solution?
bin_sherlo
18.01.2025 14:05
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$
Hertz
18.01.2025 19:47
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.
Begli_I.
22.01.2025 09:56
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.