Figuring out # of possible paths?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

merfed
Posts: 3
Joined: Fri Jun 26, 2009 2:41 pm UTC

Figuring out # of possible paths?

You have a cube placed in a infinity large cube. It can fit an equal amount of these little cubes inside it. Given these rules:

1. Cannot come back to the same location twice.
2. Cannot stay on the same Y twice.
3. Cannot move diagonally on the X and Z axis.

How would you figure out the number of possible paths a cube could take without breaking any of those.

NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Figuring out # of possible paths?

I don't think I'm understanding your wording or something. If it's infinite, what do you mean it can fit "an equal amount of these little cubes in it"? Are we even trying to fit cubes in it in this problem? Can you not *ever* return to the same Y that you have been at before, or can you just not be on the same Y two turns in a row? By "cannot move diagonally on the X and Z axis" do you mean that it cannot move diagonally in any plane that is parallel to the XZ-plane?

Most importantly: paths to/from where? Are we restricted to some bounded subset of the "infinite cube" (if not, there are obviously infinitely many paths)? Are we restricted to moving along lattice points (that is, what types of lengths of moves are we allowed to do -- does a move from (0,0,0) to (0,0,1/2) count as a move)?

After you pin down all those things, the answer to "how to figure out the number of paths" is almost surely "write a computer program to brute-force it" or "look it up in the OEIS."
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

merfed
Posts: 3
Joined: Fri Jun 26, 2009 2:41 pm UTC

Re: Figuring out # of possible paths?

Infinite was just to set up a "size", you can equally fit these little cubes in. It's not going to be longer on one side, or another. So it's large. But for sake of ease lets say its 3x3. If you return to the same spot before you mess up the cube as that spot is taken. Navigating to any open spot by the amount of moves you have from the present location is fine. So if it start at 0,0,0 you can go 0,1,0 and 0,-1,0.

sparks
Posts: 119
Joined: Sat May 17, 2008 7:24 pm UTC
Contact:

Re: Figuring out # of possible paths?

merfed wrote:It's not going to be longer on one side, or another. So it's large. But for sake of ease lets say its 3x3.

If it's longer on one side, I don't think it actually counts as a cube? And even if it were longer on one side, that doesn't invalidate it being large. Your wording is making this a bit confusing
(icon by clockwork-harlequin.net)

"An idea that is not dangerous is unworthy of being called an idea at all." ~ Oscar Wilde

merfed
Posts: 3
Joined: Fri Jun 26, 2009 2:41 pm UTC

Re: Figuring out # of possible paths?

Each color is represented on the above picture.

The starting variable in this situation would be . '''1 possible present at 0,0,0'''.
The following branching possible future would be '''2 different futures at 0,1,0 and 0,-1,0'''.
The next move can only be '''4 possible futures on the y=0 plane'''. At this state, the '''Change Y axis''' rule overrides the '''No Diagonal moves''' rule.
The new present branches to '''8 possible futures on the y=1 & y=-1 planes'''.
The next move goes back to beiing '''4 possible futures on the y=0 plane'''. At this state, the '''Change Y axis''' rule overrides the '''No Diagonal moves''' rule.
The last branching future possible for this 3x3 system is '''8 possible futures on the y=1 & y=-1 planes'''.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Figuring out # of possible paths?

merfed wrote:At this state, the '''Change Y axis''' rule overrides the '''No Diagonal moves''' rule.

What does this mean? When is one allowed to "override" certain rules?

Posts: 809
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Figuring out # of possible paths?

Okay, I'm going to rephrase the question as well as I can understand it.

Take a 3x3x3 cube. Split it into 27 1x1x1 cubes in the obvious way. Fill in the center 1x1x1 cube. Then continue filling in 1x1x1 cubes one by one, according to the following rules:

-Each cube you fill in must be adjacent to the previous cube you filled in (diagonals count as adjacent).

-You can't fill in the same cube twice.

-Each cube you fill in must have either a different x or a different z coordinate from the previous cube, but cannot change both (i.e., each cube you fill in must have either the same x or same z coordinate as the previous one).

How many ways can you do this?

Is that your question, merfed? Also, do you have to fill in every cube, or can you stop at some point?
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!