Invasion Of The Pareraretee Parasite

Scientists have discovered a specimen, called the Pareraretee parasite. When seeded in a square grid, the Pareraretee parasite reproduces in one of 2 ways:

1) If cells $(x_1, y_1)$ and $(x_2, y_2)$ have been infected, then cells $( x_1, y_2)$ and $(x_2, y_1 )$ will become infected.
2) If cells $(x_1, y_1)$ and $(x_2, y_2)$ have been infected, and $x_1 \equiv x_2 \pmod{2}$ , $y_2 \equiv y_2 \pmod{2}$ , then the cell $( \frac{ x_1 + x_2 } { 2} , \frac{ y_1+ y_2} {2} )$ will also become infected.

If we start with a $2013 \times 2013$ board, what is the minimum number of cells we have to infect, to guarantee that the entire board eventually becomes infected?

For a general $N \times N$ board, what is $C_N$ , the minimum number of cells that we have to infect?

If we only use condition 1, then it is clear that if all the $N$ cells on the diagonal (i.e. of the form $(n, n)$ ) were infected, the entire board will become infected. Thus, $C_N \leq N$ . Can you do better?

#Combinatorics #CombinatorialGames

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

I don't think if we are using only condition 1 the bound of $C_N\leq N$ can be improved. Because if initially there is no parasite at a certain $x_i=k$ line, there will not be any parasite on that line hereafter.

Abhishek Sinha - 6 years, 12 months ago

Yes, if only condition 1 was used, then the minimum number of parasites needed is $N$ .

Calvin Lin Staff - 6 years, 12 months ago

I am pretty certain I know the answer, but there's an off chance that I could be wrong.

Note that $C_N$ is much less than $N$ for large $N$ . In particular, $C_{2013} < 100$ .

Calvin Lin Staff - 6 years, 12 months ago

I have a suspicion that $C_N \leq (\log N)^2$ . A possible arrangement could be to place parasites initially on the points $(2^i, 2^j), 0\leq i\leq \log N, 0\leq j \leq \log N$

Abhishek Sinha - 6 years, 12 months ago

I think there might be a typo in the first condition. Shouldn't it be if $(x_1,y_1)$ and $(x_2,y_2)$ are infected?

Daniel Liu - 6 years, 12 months ago

Updated. Error was in both conditions (since I copy and paste)

Calvin Lin Staff - 6 years, 12 months ago

@Calvin Lin – This may be wrong, but this is what I got:

$C_N=2$ if $N=2^x+1$ for some integer $x\ge0$ ,

$C_N=3$ if $N=2^x+2^y+1$ for distinct integers $x,y\ge0$ ,

$C_N=4$ otherwise.

Outline-type reasoning: For all $2^x$ such that $x\ge0$ , if we place parasites on $(n,n)$ and $(2^x+n,2^x+n)$ , they will infect all $(k,k)$ , where $n\le{k}\le2^x+n$ . Therefore, if $N=2^x+1$ , then we place parasites on $(1,1)$ and $(2^x+1,2^x+1)$ . If $N=2^x+2^y+1$ , then we place parasites on $(1,1)$ , $(2^x+1,2^x+1)$ or $(2^y+1,2^y+1)$ , and $(2^x+2^y+1,2^x+2^y+1)$ . Otherwise, we place parasites on $(1,1)$ , $(N-2^i,N-2^i)$ , $(2^i+1,2^i+1)$ , and $(N,N)$ (if $2^i$ is the largest power of $2$ under $N$ ). Then, we use condition 1 after all $(n,n)$ are infected.

Jeffery Li - 6 years, 12 months ago

@Jeffery Li – Can you explain why 4 parasites would be sufficient in all other cases? How do you know that the entire region from $N- 2^i$ to $N$ will be filled?

Also, another major part of this problem is showing that you found the minimum. E.g. in the case of $7 = 2^2 + 2^1 + 1$ or $4 = 2^1 + 2^0 + 1$ , how do you know that it can't be done with 2? We could check cases of placement, but this could become tedious in general.

Calvin Lin Staff - 6 years, 12 months ago

@Calvin Lin – Before I begin, I'll prove why "if we place parasites on $(n,n)$ and $(2^x+n,2^x+n)$ , then that diagonal will be filled" is true. (I forgot this last time)

If we place parasites on $(n,n)$ and $(2^x+n,2^x+n)$ , on the first cycle, they'll fill up $(n+2^{x-1},n+2^{x-1})$ . On the second cycle, they'll fill up $(n+2^{x-1}\pm2^{x-2},n+2^{x-1}\pm2^{x-2})$ (on the diagonal, so the x and y values are the same). On the third cycle, they'll fill up $(n+2^{x-1}\pm2^{x-2}\pm2^{x-3},n+2^{x-1}\pm2^{x-2}\pm2^{x-3})$ , and so on until the xth cycle, where they'll fill up $(n+2^{x-1}\pm2^{x-2}\pm2^{x-3}\pm...\pm2^1\pm1,n+2^{x-1}\pm2^{x-2}\pm2^{x-3}\pm...\pm2^1\pm1)$ , where the x and y values are the same. Each cycle filled up $2^{k-1}$ spaces on the diagonal, so the number of spaces filled on the diagonal are $2+2^0+2^1+2^2+2^3+...+2^{x-1}=(2^x-1)+2=2^x+1$ . Since there are $2^x+1$ points on the diagonal between $(n,n)$ and $(2^x+n,2^x+n)$ , inclusive, every point must've been filled. (You can probably prove this by using binary too)

Well, I know that the entire diagonal from $(N-2^i,N-2^i)$ to $(N,N)$ will be filled because it's the same thing as knowing that if we place parasites on $(n,n)$ and $(2^x+n,2^x+n)$ , then that diagonal will be filled. Substituting $n=N-2^i$ gives that "if we place parasites on $(N-2^i,N-2^i)$ and $(N-2^i+2^i,N-2^i+2^i)$ (or $(N,N)$ ), then that diagonal will be filled." The key point here is that any two parasites can produce other parasites. Not just the closest two, any two. (4 parasites are sufficient because every point on the diagonals $(1,1)$ to $(2^i+1,2^i+1)$ and $(N-2^i,N-2^i)$ to $(N,N)$ will be filled, and since $N-2^i<2^i+1$ , the diagonals overlap, so clearly every point on the diagonal from $(1,1)$ to $(N,N)$ will be filled.)

The problem about my reasoning is that, as you've pointed out, I haven't proven that it is the minimum. I'm certain that this works for larger numbers, but for smaller cases, I don't really know how to prove that this is the minimum. I think that you always need 2 parasites on opposite corners, though, and if $N\neq2^x+1$ , you need at least 1 extra parasite somewhere else.

Jeffery Li - 6 years, 12 months ago

@Jeffery Li – You are very close. You have stated all of the arguments necessary, but have not drawn the correct conclusion.

Once you figured it out, please post your solution as a new comment thread.

Calvin Lin Staff - 6 years, 12 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$