April 2015

[Batalov]

http://domino.research.ibm.com/Comm/...April2015.html

[science_man_88]

my first thought when I looked at it is a outer wrapping of just wendy's but unless two or more peter pans can be in one cell that's destroyed because the outer layer is 2*(49+35+25) = 218 which only leaves 125 cells in which to put 161 peter pans.

[TheMawn]

I have to say the wording feels a bit clunky on this one. I suppose it's for the Peter Pan theme. I wouldn't mind a more technical explanation of the problem without the flavour just for the sake of better clarity.

From what I can tell, we're drawing lines with direction [u v w] where u, v, and w can be -1, 0 or 1. These lines start at any cell outside the cube and pass through the cube, and every possible line going through the cube must contain at least one Wendy OR no Peters.

Lucky for me I happen to have one of these sitting around.


I have a funny feeling that having all 125 inner cells being P is not correct. Until then though I'm happy to entertain that possibility. That would leave 36 other cells and that number is interesting because it leaves 6 per face.

The corners have to be W because there are lines which pass through just them. That's not just the 8 corners but all edge pieces too.

That leave 6 5x5 faces which have to have 6 P's on them somewhere. I suppose one way to do it is to just pick one at random and add a Wendy to every line that passes through that cell.

[TheMawn]

Yep, that's definitely how I would do it. I'll have to think of a way to implement this idea with the tools I have at my disposal.

Set the inner 5x5x5 cube to P, and all outer edges to W leaving six 5x5 faces unset.

Pick a cell at random on the inner 5x5 square of any one face, set it to P and run all 9 lines through it into the cube. Any unset cell that a line passes through is set to W. If any of the lines have no unset cells AND no W's, then that line contains all P's and then whatever cell you started with becomes W itself.

If I get around to this I'll have to see if I need a more structured approach for deciding what cells to start painting P.

[Batalov]

Like the March problem (and many ProjectEuler problems), it will probably help to think of smaller cubes first.
For 1x1x1, no Peter Pans are possible.
For 2x2x2, the answer is practically trivially 0; no mystery here, no use to spoilerize.
For 3x3x3, if the outer layer was necessary, then the answer would be "1", but it isn't.
And so on...

[LaurV]

This is a 3D extension of the 8 queens problem, which we solved years ago when in college (both by hand and by computer). In fact, a Wendy is a 3D-queen, which can move in all orthogonal and diagonal directions, and you are requested to show a maximal explicit solution (this is a relative of the "domination problem" - what is the minimum number of queens to cover the chess board completely?) - for which we also made a program in the past. See the explanation on the "related problems" on the given link, and also on wolfram for better explanation and a solution for the domination problem (couldn't find a wiki link).

Remark that I stressed the "maximal", in the sense that the board has to be covered in any direction, for example, at the first link on wiki, the first solution given in the photo on the right is not "maximal", because, for example, there is no queen on the a1-h8 diagonal. One could make a maximal solution by placing 22 queens on columns A and H and line 1. Can you do it with less queens? How.

Then try with 7 squares instead of 8. **

Then try with Wendies, i.e. 7 planes instead of 1.

---------
** you will need the covering condition for Wendies to be satisfied on every plan, so you will need to solve the planar problem before moving to the 3D cube. You will need to find as many planar solutions as you need, and combine them on the seven planes to have the planar solutions satisfied on the other perpendicular planes, I think that is the simplest approach, computationally. You may still need to "add" Wendies when you put the planes together.

[LaurV]

We solved the "planar" problem, by proving there are no solutions with 14 wendies, the minimal solution is with 15, and there are 112 such solutions including the symmetries. So the problem complexity lays in 112^5 (because you have to pick 5 of them for the intermediary 5 layers, which is 60 wendies, do this on 3 axes, some wendies "overlap", so you have less then 180, and you still need 8 wendies for the corners (the edges of the cube are covered by the planar solutions, which always have a wendy in the corner.

[TheMawn]

All the edge cubes need to be Wendy, not just the 8 corners. You can make a bunch of lines which pass through only one of the edge pieces which is just a corner of a plane

[LaurV]

Originally Posted by TheMawn

All the edge cubes need to be Wendy, not just the 8 corners. You can make a bunch of lines which pass through only one of the edge pieces which is just a corner of a plane

All the planar solutions have a wendy in the corner, for the same reason, and when you put them in the cube, those corners become edges. Read the last sentence of my former post

[axn]

since none of you are actually posting solutions, could you please knock off with the spoilers? it is annoying.

[TheMawn]

Well we're not posting solutions but we're posting fairly heavy hints that people might not want to see.

EDIT: @LaurV yeah I misunderstood that. I focused more on the "8 corners" thing.