wu :: forums « wu :: forums - Brick piercing » Welcome, Guest. Please Login or Register. Aug 19th, 2022, 10:49pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, Eigenray, william wu, Icarus, Grimbal, towr, ThudnBlunder)    Brick piercing « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Brick piercing  (Read 2526 times)
TimMann
Senior Riddler

Gender:
Posts: 330
 Brick piercing   « on: Oct 19th, 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 lowest-numbered 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 z-axis. 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 z-axis, 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 xy-plane, 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 z-axis 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://tim-mann.org/
TimMann
Senior Riddler

Gender:
Posts: 330
 Re: Brick piercing   « Reply #1 on: Oct 16th, 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://tim-mann.org/
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »