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?

## Comments

Sort by:

TopNewestI 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

– Calvin Lin Staff · 2 years, 9 months ago

Yes, if only condition 1 was used, then the minimum number of parasites needed is \(N\).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

– Abhishek Sinha · 2 years, 9 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\)Log in to reply

– Daniel Liu · 2 years, 9 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?Log in to reply

– Calvin Lin Staff · 2 years, 9 months ago

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

\(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

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

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

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