Problem 763

[eskaug]

https://projecteuler.net/problem=763

I have read this problem through a couple of times, and I'm still not seeing what distinguishes one "arrangement" from another. Is it the ancestry that's important? Is it that an amoeba will divide only if all three of the cubes it wants to divide into are empty, not not otherwise?

Perhaps it would be helpful if someone who understands the problem could describe the three arrangements indicated by D(2)=3?

Thank you so much for your time,
Eric

[eskaug]

Per Murphy's Law, once I typed up and submitted my question, I was able to read more clearly. It seems clear to me now (2N+1 was an obvious clue) that only one amoeba can divide in each step. If anyone with the knowledge wants to confirm this understanding, I'd still appreciate it, but I'm no longer pulling my hair out

[FransM]

Per Murphy's Law, once I typed up and submitted my question, I was able to read more clearly. It seems clear to me now (2N+1 was an obvious clue) that only one amoeba can divide in each step. If anyone with the knowledge wants to confirm this understanding, I'd still appreciate it, but I'm no longer pulling my hair out

I feel your assumption that only one amoeba can divide in each step is incorrect.
After step N there are 2N+1 amoeba's so after the first step there are 3 amoeba's (at (1,0,0), (0,1,0), (0,0,1))
and after 2 steps there are 5 according to the formula, although I would expect 6.
(2,0,0), (1,1,0), (1,0,1), (0,2,0), (0,1,1), (0,0,2)

And it is still unclear to me what constitute an arrangement. I suspect it would be good to give some additional explanation.

[mdean]

I don't see the word "step" anywhere in the problem. The problem mentions N "divisions". Are you arguing that 3 amoebas dividing at the same time is a single division?

[FransM]

It seems I totally misread/misunderstood the problem. Somehow I grasped that a cell would divide in all three directions but that is obviously not correct.
Blame it on me for being a bad reader (and a non-native English speaker).

The confusion was triggered by

An amoeba in cube (x, y, z) can divide itself into three amoebas to occupy the cubes (x + 1, y, z), (x, y + 1, z) and (x, y, z + 1), provided these cubes are empty.

This suggested to me that one amoeba would divide into three others. and that the original amoeba is gone
And that is what I called a "step", but actually I feel this is what the problem calls a division (and yeah, maybe that is leaning towards an implementation)

Then the problem follows with

After N divisions there will be 2N+1 amoebas arranged in the grid.

This makes it more confusing. We start with N = 1 and then there is indeed one amoeba at (0,0,0).
But this line says that after the first division (N=1) there will be 3 amoebas.
Hence I became more convinced that a single cell would divide into 3 new cells (given space of course).
Still not sure if that is correct.

And then there is the term "arrangement". What is exactly meant by that? Maybe use the word shape, or add some explanation.

Lastly it says that D(2) = 3, and then I become completely lost. Does arrangement mean the same shape irrespective of orientation? Otherwise how do we get to this value.
I suspect it would help if there is some explanation (maybe with a picture) for D(2).

After writing this and thinking a bit more about it I suspect that the following is supposed to happen:
There is a sequence of amoeba splits. Each time a split occurs the three neighbouring fields are split into and the original amoeba is gone. Even if all surrounding locations are occupied.
And of course depending on what amoeba splits first we get a different constellation, and the question is about the number of constellations.

Correct?

[mdean]

To my understanding, a division is when 1 amoeba splits into 3 as described in the first paragraph of the problem. I think an arrangement just refers to the locations where an amoeba can be found. You seem to understand the first division: the amoeba at (0,0,0) is replaced by 3 new amoebas at (0,0,1),(0,1,0), and (1,0,0). For the second division, one of those 3 amoebas will split in the same fashion and the other 2 will continue to exist in their current locations. An amoeba will not split if any of the 3 locations that would receive a new amoeba is already occupied.

Does this answer your question?

[FransM]

@mdean That ansers most of my questions.
If none of the 3 locations would receive a new amoeba is the existing amoeba gone?

I still feel the wording of the problem could use some improvement.

[mdean]

From the second line of the problem statement, "An amoeba in cube $(x,y,z)$ can divide itself..., provided these cubes are empty." This last line sets a condition for when the amoebas can divide. If any of the cubes is not empty, that amoeba cannot divide yet. That's why the number of amoebas increases with 2 at each division: 1 amoeba is replaced with 3 new ones.

[FransM]

Ah ok, I didn't link it to the 2N+1 line.
I read it (obviously incorrectly) as the amoeba only replicating to non-empty cells.