Waste less time on Facebook — follow Brilliant.
×

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?

Note by Calvin Lin
2 years, 9 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 · 2 years, 9 months ago

Log in to reply

@Abhishek Sinha Yes, if only condition 1 was used, then the minimum number of parasites needed is \(N\). Calvin Lin Staff · 2 years, 9 months ago

Log in to reply

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 · 2 years, 9 months ago

Log in to reply

@Calvin Lin 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 · 2 years, 9 months ago

Log in to reply

@Calvin Lin 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 · 2 years, 9 months ago

Log in to reply

@Daniel Liu Updated. Error was in both conditions (since I copy and paste) Calvin Lin Staff · 2 years, 9 months ago

Log in to reply

@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 · 2 years, 9 months ago

Log in to reply

@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 · 2 years, 9 months ago

Log in to reply

@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 · 2 years, 9 months ago

Log in to reply

@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 · 2 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...