Friday Puzzler -- Illuminated artwork

Re: Friday Puzzler -- Illuminated artwork

Jim Rutten

OK. I am going for the obvious answer of 60 seconds. I chose that answer because as long as you are passing through straight lines that form the cube, whether you go through a partial rod or not it is going to be 10 seconds so 10 seconds for each of the three legs and then back again. I kinda figure I'm wrong.

Re: Friday Puzzler -- Illuminated artwork

Larry Barrett

I think Jim's answer is correct for one of the possible paths. But if I read the problem correctly, one cycle consists of all possible shortest paths. Even for just the the edges there are 6 possible paths going up, and 6 coming down, so 36 combinations of shortest paths.

What is not clear to me is how all 300 rods are used. Do they all lie on the surface? Does each face consist of an equal number? Are they arranged in a checkerboard fashion, or all parallel (or does it matter)? If, for example, in a checkerboard pattern, are they connected where they cross, so a path could be a zig-zag pattern? If so, there will be a LOT of possible shortest paths.

Some Answers

Alex Y

to Jim's and Larry's questions:

My reading of this puzzle is that the structure is a cube which consists of a stack of smaller cubes, each of which is 1rodx1rodx1rod. There is such an arrangement that uses exactly 300 rods.

I did not read this as the lights moving from one rod to another every ten seconds, or going up and down. I read it as one path being lit for ten seconds, then another path being lit, until all possible paths have been lit.

In other words, skipping the trivial step of multiplying by 1o seconds (trivial, but the kind of thing that often trips me up ), the problem comes down to figuring out how large the cube is, and how many unique paths of minimal length there are along the rods between the diagonally opposite corners.

P.S., Larry, yes, there are a LOT of possible paths!

Re: Some Answers

Larry Barrett

I think 300 rods make a 4x4x4 cube.

A 1x1x1 cube has 12 sides(rods).

To get to a 2x2x2 cube you need to add 7 cubes, but because adjacent edges only count once, this requires adding 42, for a total of 54.

To get to a 3x3x3 cube requires adding 90 rods, for a total of 144.

To get to a 4x4x4 cube requires adding 156 cubes, for a total of 300.

The number of shortest paths is another matter.

Re: Some Answers

Alex Y

Correct. 3*n*(n+1)^2

Re: Some Answers

Bill Earl

If you consider the cube as a 3 dimensional space with the origin at 0,0,0, and the apex at 4,4,4: You need the number of paths consisting of 12 steps in a positive direction, 4 each in each of the 3 dimensions.

Counting them up (with the help of a Core i7), I can tell you that the first four digits are not quite sequential. As for a general formula, it is shaping up as a headsplitting assembly of factorials and cubes. Haven't quite nailed it down yet.

Re: Some Answers

Larry Barrett

Headsplitting is right. I am approaching this in my ususal way.

For a 1x1x1 cube, there are 6 paths. For a 2x2x2 cube it gets headsplitting fast; I think there are 60 paths, but get different answers each time I think about it.

Clearly need a formula to go further.

Re: Some Answers

Alex Y

If you consider the cube as a 3 dimensional space with the origin at 0,0,0, and the apex at 4,4,4: You need the number of paths consisting of 12 steps in a positive direction, 4 each in each of the 3 dimensions.

Correct

Counting them up (with the help of a Core i7), I can tell you that the first four digits are not quite sequential.

Correct again, assuming you are talking about the count, not converted to time. As a check of your answer, when converted to time and expressed in common units of time, the minutes component is 15.

As for a general formula, it is shaping up as a headsplitting assembly of factorials and cubes. Haven't quite nailed it down yet.

You've got the right components, and it is head-splitting to get there, but not a very complex formula (as formulas with factorials and cubes go).

Re: Some Answers

Alex Y

There are 6 paths for the single cube, as you stated, but 60 is not correct for the 2x2x2 cube.

Re: Some Answers

Larry Barrett

I don't have an answer yet, and not approaching it same way as Bill is, but do have some insights (I think).

I have been looking at a 2D version, since it is much simpler to analyze, hoping that results can be extrapolated to the 3D actual problem.

Here is what I can see so far. The 2D problem looks like a checkerboard, instead of a cube. We want to find the number of paths from one corner (say at 0,0) to the diagonally opposite corner at (n,n). I am looking at 1x1, 2x2, 3,3, and 4X4 squares, and the data below is in that order.

# edges = 4, 12, 24, 40

minimum path length = 2, 4, 6, 8

# paths of min length = 2, 6, 20, 70

The formula for the # of edges is 2n(n+1). Note that Alex provided this formula for the 3D problem - 3n(n+1)^2

The formula for the minimum path length is 2n; for the 3D problem it is 3n.

By observation, I found that the total number of edges used for all the paths of minimum length totaled 4, 24, and 120 for the first three 2D cases; I observed that this total is equal to the (minimum path length) x (# paths of min length). This is pretty obvious, but I actually counted then for the first three 2D cases. So by extension, for the 2D 4x4 case, there are a total of 8x70 = 560 edges required. This (multiplied by 10) would be the total time required for one cycle in the 2D case.

That is as far as I have gotten, but I am trying to extrapolate to the 3D case.

Good progress!

Alex Y

Larry, I like your problem-solving technique, and admire your tenacity on this tough problem; I never did crack it, and when I saw the formula for the answer, which was given without explanation, it took me a long time to understand why.

I think you are getting close. See some comments below:

Here is what I can see so far. The 2D problem looks like a checkerboard, instead of a cube. We want to find the number of paths from one corner (say at 0,0) to the diagonally opposite corner at (n,n). I am looking at 1x1, 2x2, 3,3, and 4X4 squares, and the data below is in that order.

# edges = 4, 12, 24, 40

minimum path length = 2, 4, 6, 8

# paths of min length = 2, 6, 20, 70

I concur.

The formula for the # of edges is 2n(n+1). Note that Alex provided this formula for the 3D problem - 3n(n+1)^2

Yes, and that is exactly how I got there. Count the number of horizontal checkerboards in the cube (n+1), and that gives you 2n(n+1)^2 rods in the checkerboards. Then add another n*(n+1)^2 rods joining the checkerboards for the formula I gave. But in retrospect, there is a better way to look at it: on your nxn checkerboard, look at the intersections. There are (n+1)^2 of them. This is where the vertical rods go. And envisioning the cube, there are n "layers" of such rods, so n(n+1)^2 vertical rods. By symmetry, there are the same number in each of the other two orientations, so 3n(n+1)^2 rods in total.

The formula for the minimum path length is 2n; for the 3D problem it is 3n.

By observation, I found that the total number of edges used for all the paths of minimum length totaled 4, 24, and 120 for the first three 2D cases; I observed that this total is equal to the (minimum path length) x (# paths of min length). This is pretty obvious, but I actually counted then for the first three 2D cases. So by extension, for the 2D 4x4 case, there are a total of 8x70 = 560 edges required. This (multiplied by 10) would be the total time required for one cycle in the 2D case.

We have a different reading of the problem here. I think the path lights up for ten seconds, not each rod in the path lighting up for that time. Not material, though; full credit if your answer is 12 times mine!

More ...

Larry Barrett

I agree with your last statement about the path; you explained this earlier, and I forgot. Nevertheless, it is interesting to 'draw' each path and keep 'score' on each edge involved in each path. This is do-able for the 2D version, at least up to 3x3 level. There is a lot of symmetry, as you would expect. Since each path starts at the origin and ends at the diagonally opposite corner (endpoint), the 2 edges that adjoin the start and endpoint (2 in the 2D case, 3 in the 3D case) are part each path - actually each of the 2 edges is part of half the total paths. If we say P is the total # of paths of min length (2 6 20 70 for the 4 2D cases) then each edge that adjoins the origin, and each edge that adjoins the endpoint is part of (1 3 10 35) paths for the same 4 2D cases. By symmetry, the same will be true for the 3D cases - each of the three edges that adjoin the origin and endpoint will be part of 1/3 P. So one observation is that the P will be divisible by 2 (for 2D) or by 3 (for 3D).

By 'drawing' the paths and keeping score, you see that edges that lie along the main diagonal are involved in the next most number of paths, and the edges that adjoin the opposite 2 corners are only involved in 1 path each. By looking at the pattern that develops for the various cases it may be possible to figure out the formula for the 'score' at each edge. All that is needed is to find the formula for the edges at the origin and endpoints (but I am not there yet ).

Re: Some Answers

Bill Earl

Had a little more time to play with this one. My formula checks out with my brute-force solution. The derivation is a little rough still.

Starting with the formula nPk (the number of permutations of k items from a set of n) which is n!/(n-k)! In the case that n=k, this reduces to n!

In a cubic lattice of dimension of N x N x N where N=4, the set of shortest paths from one corner to the opposite corner are all of length 3N or 12.

Each path consist of 3 moves in each of the X, Y and Z directions, so we will start with k = n = 3N and the number of permutations is 3N!

But, the order of moves on each of the three axis matter. (We have to move to X=1 before X=3 and X=3.) So, we need to eliminate the various permutations of the moves on each axis.

The number of moves on each axis is N, and the number of permutations NPN is N!. So dividing out N! paths on each of the three axis gives us:

3N! / N!^3

For N=4, the number of paths is 34650. I could list them if you like

Re: Some Answers

Larry Barrett

Wow - I bet that is correct. It checks out for my much simpler 2D cases when your formula is changed to (2N)!/N!^2. Thanks for solving this. I'm glad to stop thinking about it.

Correct!

Alex Y

Nice job!

Converted to time: 4 days and 15 minutes