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 (x1,y1) (x_1, y_1) and (x2,y2) (x_2, y_2) have been infected, then cells (x1,y2) ( x_1, y_2) and (x2,y1) (x_2, y_1 ) will become infected.
2) If cells (x1,y1) (x_1, y_1) and (x2,y2) (x_2, y_2) have been infected, and x1x2(mod2) x_1 \equiv x_2 \pmod{2} , y2y2(mod2) y_2 \equiv y_2 \pmod{2} , then the cell (x1+x22,y1+y22) ( \frac{ x_1 + x_2 } { 2} , \frac{ y_1+ y_2} {2} ) will also become infected.

If we start with a 2013×2013 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×N N \times N board, what is CN 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 NN cells on the diagonal (i.e. of the form (n,n) (n, n) ) were infected, the entire board will become infected. Thus, CNN C_N \leq N . Can you do better?

Note by Calvin Lin
5 years, 5 months ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Abhishek Sinha - 5 years, 5 months ago

Log in to reply

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

Calvin Lin Staff - 5 years, 4 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 CN C_N is much less than NN for large NN. In particular, C2013<100 C_{2013} < 100 .

Calvin Lin Staff - 5 years, 5 months ago

Log in to reply

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

Abhishek Sinha - 5 years, 5 months ago

Log in to reply

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

Daniel Liu - 5 years, 5 months ago

Log in to reply

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

Calvin Lin Staff - 5 years, 5 months ago

Log in to reply

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

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

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

CN=4C_N=4 otherwise.

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

Jeffery Li - 5 years, 5 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 N2i N- 2^i to NN will be filled?

Also, another major part of this problem is showing that you found the minimum. E.g. in the case of 7=22+21+1 7 = 2^2 + 2^1 + 1 or 4=21+20+1 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 - 5 years, 5 months ago

Log in to reply

@Calvin Lin Before I begin, I'll prove why "if we place parasites on (n,n)(n,n) and (2x+n,2x+n)(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)(n,n) and (2x+n,2x+n)(2^x+n,2^x+n), on the first cycle, they'll fill up (n+2x1,n+2x1)(n+2^{x-1},n+2^{x-1}). On the second cycle, they'll fill up (n+2x1±2x2,n+2x1±2x2)(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+2x1±2x2±2x3,n+2x1±2x2±2x3)(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+2x1±2x2±2x3±...±21±1,n+2x1±2x2±2x3±...±21±1)(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 2k12^{k-1} spaces on the diagonal, so the number of spaces filled on the diagonal are 2+20+21+22+23+...+2x1=(2x1)+2=2x+12+2^0+2^1+2^2+2^3+...+2^{x-1}=(2^x-1)+2=2^x+1. Since there are 2x+12^x+1 points on the diagonal between (n,n)(n,n) and (2x+n,2x+n)(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 (N2i,N2i)(N-2^i,N-2^i) to (N,N)(N,N) will be filled because it's the same thing as knowing that if we place parasites on (n,n)(n,n) and (2x+n,2x+n)(2^x+n,2^x+n), then that diagonal will be filled. Substituting n=N2in=N-2^i gives that "if we place parasites on (N2i,N2i)(N-2^i,N-2^i) and (N2i+2i,N2i+2i)(N-2^i+2^i,N-2^i+2^i) (or (N,N)(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)(1,1) to (2i+1,2i+1)(2^i+1,2^i+1) and (N2i,N2i)(N-2^i,N-2^i) to (N,N)(N,N) will be filled, and since N2i<2i+1N-2^i<2^i+1, the diagonals overlap, so clearly every point on the diagonal from (1,1)(1,1) to (N,N)(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 N2x+1N\neq2^x+1, you need at least 1 extra parasite somewhere else.

Jeffery Li - 5 years, 4 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 - 5 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...