a virus problem, playing a game with the doctor

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

w

15 users

TOPICS

No tags match your search

M

No tags match your search

M

a virus problem, playing a game with the doctor

G H J

Reveal topic tags

combinatorial geometry

L

G H BBookmark kLocked kLocked NReply

Source: 2014 Kurchatov Olympiad 11 p6 - Russia

The post below has been deleted. Click to close.

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

30650 posts

#1 h Mar 7, 2021, 10:50 PM • 2 Y

Y by samrocksnature, Nofancyname

Vasya, an invisible virus, is sitting on a square plate with a side of $1$ cm. He and the doctor Petya take turns. With the next $n$ -th move, Petya draws with the vaccine like ink a segment $1$ micron long, and then Vasya must choose a direction and crawl in this straight line a direction of $1 / n$ micron distance (without going beyond the edge of the plate). If Vasya crawls through any of the points with the vaccine or touches it, he will die. Petya can act with any precision. Can Petya within a finite number of moves for sure kill the virus?

original wording

This post has been edited 2 times. Last edited by parmenides51, Mar 7, 2021, 11:22 PM

Z K Y

The post below has been deleted. Click to close.

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

4917 posts

pog

#2 h Mar 7, 2021, 11:05 PM • 6 Y

Y by Inconsistent, L567, Galinagames, snoozingnewt, samrocksnature, GianDR

No matter what happens in the future, here is one thing that I can guarantee will remain constant: if there are two people in a Russian Olympiad problem, there is at least an $80\%$ chance that they are named Vasya and Petya.

Z K Y

The post below has been deleted. Click to close.

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

2463 posts

#3 h Mar 10, 2021, 2:50 PM • 3 Y

Y by pog, parmenides51, samrocksnature

Petya can kill the virus. Suppose doctor Petya is at his $2^k$ th move. During his next $2^k$ number of moves he draws $2^{k-1}$ aligned vertical segments at a distance of $2^{-k-2}$ microns between any two consecutive ones, and another $2^{k-1}$ aligned horizontal segments, at a distance of $2^{-k-2}$ microns between any adjacent ones, so that they form a sieve.
Thus, he makes a square $Q$ of side length $\left(2^{k-1}-1\right)\cdot 2^{-k-2}>2^{-4}$ microns full of cells of size $2^{-k-2}\times 2^{-k-2}$ inside it, and all borders are drawn.
Next, consider the $2^{k+1}$ th move of the virus. If it is inside $Q$ he will be killed. In this way, Petya eliminates, one by one, squares with a side length greater than $2^{-4}$ microns, and finally kills the virus.

Z K Y

The post below has been deleted. Click to close.

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

678 posts

#4 h Mar 11, 2021, 6:53 AM • 5 Y

Y by samrocksnature, Nofancyname, Mango247, Mango247, Mango247

I think it's a bit troll, anyways idea is similar to that of #3 , with a different bounding.

Consider the non-overlapping squares of size $0.2\times 0.2$ , if Vasya the Virus is on one of the diagonals of it and goes on it in his first (or few first) move(s) he'll die obviously as the length of his allowed path would be $0.2\sqrt{2}<1$ microns. So he moves to inner part of a $0.2\times 0.2$ table and we may wlog assume he was inside. Let Petya check these tables, and suppose he checks some of them in $k$ moves without success and eventually he's checking the board where Vasya the Virus is located. Then he draws $k$ rows and $k$ columns in order to partition the table into squares of size $\frac{0.2}{k}\times\frac{0.2}{k}$ . If the virus died when running away from one line by hitting some other we're done, so assume he's still alive and now he's inside some of these squares,the next time he'll go $\frac{1}{3k}$ microns away which exceeds $\frac{0.2}{k}$ , so he dies .

Z K Y

The post below has been deleted. Click to close.

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

102 posts

#5 h Mar 11, 2021, 10:02 AM • 1 Y

Y by Mango247

@above. I don't understand the first few sentences in your proof , why "its allowed path" instead of just "path" , why is it bounded ?

Z K Y

The post below has been deleted. Click to close.

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

678 posts

#6 h Mar 11, 2021, 11:02 AM

Y by

Petya is the one who draws these tables , that's why :huh:

:huh:

. These moves are counted in the part

Kamran011 wrote:

Let Petya check these tables, and suppose he checks some of them in $k$ moves without success and eventually he's checking the board where Vasya the Virus is located.

Z K Y

The post below has been deleted. Click to close.

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

2463 posts

#7 h Mar 11, 2021, 12:28 PM

Y by

Funny, but the problem can be made a bit more complicated. There is no need the virus to be framed in an unit square. So, the virus is somewhere on the plane, no one knows exactly where, and Petya (the doctor) is at the origin. The rest of the rules are the same. Still, Petya can kill the virus after finite amount of time!

With $4\cdot 10^6$ consecutive moves Petya can frame any unit square on the plane. He begins to frame the unit squares on the lattice points, so that he consecutively fills the squares with corners at $(-N,-N), (-N,N), (N,N),(N,-N)$ for $N=1,2,\dots.$ One move for every $4\cdot 10^6$ ones, he saves for another goal. With these moves he begins a process of killing the virus, as described in #3, inside each of the framed unit squares, such that he eliminates them, one after another. It can be easily checked that after $n$ moves, the doctor frames all unit squares at a distance $C\sqrt{n}$ from the origin, where $C$ is a constant. At the same time, at its $n$ th move the virus is at a distance $C_1+1+\frac{1}{2}+\dots+\frac{1}{n}\le C_1+C_2\log n$ from the origin. Since the growth rate of $\sqrt{n}$ is faster than $\log n,$ the virus will be framed after finite amount of time, and later it will be killed. The only drawback is the doctor will not know exactly when this will happen.

This post has been edited 1 time. Last edited by dgrozev, Mar 11, 2021, 12:28 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a