8
$\begingroup$

In the land of the tetrominos, the twins L. and J. have set out to revolutionize travel by rail. Contemporaries' passenger cars are boxy and boring, and humdrum symmetric passenger arrangements are all too common when the car gets full. "Not on our lines!" vow L. & J. No, when travelers completely fill the polymino interior of an L. & J. railcar, the entrepreneurs promise that both reflection-symmetric and rotation-symmetric seating will be impossible by design.

That is, if they can only get one of their interiors approved by the railcar authorities, I., T., and O. Prior submissions have fallen afoul of one or more of the safety regulations:

  • Polymino cells must be axis-aligned. (By convention, the $\pm x$ directions are the car's directions of travel.)

  • The car should be balanced on the tracks; the interior must be symmetric about the $x$ axis.

  • The car should travel equally well in both directions; the interior must be symmetric about the $y$ axis.

Besides all that, L. and J., being good businessminos, don't like wasting space; it should be possible to fill their cars to the brim.

How can L. and J. build the railcar of their dreams? Bonus: What is the least capacity such a car could have?

(Since this is an aha-moment sort of puzzle, please spoiler your answers.)

$\endgroup$
  • $\begingroup$ So we're supposed to design a shape (subject to the constraints) that we tile with tetrominoes so that the tetromino tiling is is neither rotationally or reflectionally symmetric? $\endgroup$ – GentlePurpleRain Jul 13 '15 at 17:07
  • 2
    $\begingroup$ @GentlePurpleRain Yes, a doubly reflection-symmetric shape that can be tiled with tetrominos, but where no tiling has reflection or rotational symmetry. $\endgroup$ – Edward Jul 13 '15 at 17:14
7
$\begingroup$

Is it okay if my solution has a

hole in the middle? It does seem to waste space a bit, but the space that is there can be filled.

If so,

enter image description here


As per Edward's comment, let me try to prove that it can't be done with a smaller train car. (It seems like there might be a better way to answer this though)

This is a bit of a cheat, but heading over to the Wikipedia page on octominoes, we see there are only five octominoes symmetric about the x and y axes and axis aligned. Each of these can easily be symmetrically seated with two passengerominoes. Two other cases to consider are a completely disconnected 2-passenger car, or a 1-passenger car, in which case the symmetry requirements on the cars force symmetry on the passengers.

$\endgroup$
  • $\begingroup$ That was fast. You have my +1, and an accept if you explain why a two-passenger car is impossible. $\endgroup$ – Edward Jul 13 '15 at 18:19
  • $\begingroup$ Oops, I see that I had made minimality the bonus, so you deserved the accept without the edit. Sorry! As for the proof, I was thinking of something without case splitting, but you're right, this works, not to mention deserves some style points for "passengerominoes". $\endgroup$ – Edward Jul 13 '15 at 23:03
  • $\begingroup$ @Edward: BTW, I'd be curious about what you were thinking for the proof. $\endgroup$ – Tyler Seacrest Jul 15 '15 at 4:20
  • 1
    $\begingroup$ One that hints at your insight: Assume such an octomino. An axis cut will break it into two mirrored components that must not be tetrominos, so both axes split cells, and there is a cell centered at the origin. It is unoccupied because octominos are even. For our octomino to still satisfy connectedness and reflection symmetry, it must cross both axes on either side of the origin cell, and these four crossings must be joined by at least four other occupied cells; our octomino, if it exists, is an "O". But an "O" admits a rotationally symmetric tiling, a contradiction. $\endgroup$ – Edward Jul 15 '15 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.