Author 
Topic: Brick piercing (Read 2526 times) 

TimMann
Senior Riddler
Gender:
Posts: 330


Brick piercing
« on: Oct 19^{th}, 2002, 7:17pm » 
Quote Modify

I'll do this in steps so that if someone needs a hint, they can reveal them one by one. Let's assume one corner of the cube is at the origin and the edges lie along the x,y,z coordinates. Name each cube by its lowestnumbered corner. 1.The hard part is to block the lattice lines, i.e., lines that are perpendicular to a face and intersect it in a point with integral coordinates. 2.Each brick can block at most one lattice line (the one that goes through the centers of its 2x2 faces). There are 19*19*3 = 1083 lattice lines that pierce the cube, but 2000 bricks, so at first it seems there are enough to do the job, but... 3.Consider the lattice line that goes through (1,1,0) parallel to the zaxis. Can you have just one brick blocking this line and still be able to fill the rest of the cubes exactly into the brick? 4.No. Think of the stack of twenty 1x1 cubes that touch the zaxis, numbered from (0,0,0) to (0,0,19). If exactly one of these cubes comes from a brick that's laid flat in the xyplane, that leaves an odd number to come from bricks that aren't laid flat. But each of those bricks must contribute 2 cubes, so they can't cover an odd number. Therefore there are an even number of bricks blocking the line parallel to the zaxis through (1,1,0). 5.Once we've set the (even) number of bricks that block the line through (1,1,0), we know that they are responsible for an even number of blocks in the stack from (0,1,0) to (0,1,19) as well. Besides those, at least one more block in that stack must come from a brick laid flat to block the line through (1,2,0). But again, the total number of bricks laid flat that contribute to that stack must be even, since the total height of the stack is even, so there must be an even number of bricks blocking this lattice line as well. We can iterate this argument over the whole cube, starting from (1,1,0), working along the edge to (1,19,0), then repeating from (2,1,0) to (2,19,0), etc. 6.So it takes at least two bricks to block each lattice line. But there are 1083 lattice lines and only 2000 bricks, so we don't have enough. Followup: Can you solve the problem for a 22x22x22 cube built from 2x2x1 bricks?


IP Logged 
http://timmann.org/



TimMann
Senior Riddler
Gender:
Posts: 330


Re: Brick piercing
« Reply #1 on: Oct 16^{th}, 2003, 12:20am » 
Quote Modify

p.s. I see Icarus has noted the followup question I gave above in his list of unsolved problems in the hard forum. Looking back at it now, I'm not sure whether I had a solution in mind when I posed the question. If I did, I've forgotten it.


IP Logged 
http://timmann.org/



