wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> square to pentomino
        
(Message started by: JocK on Feb 5^th, 2005, 2:39pm)

Title: square to pentomino
Post by JocK on Feb 5^th, 2005, 2:39pm

Pentominos are the connected planar ~~rectangular~~ shapes that originate when arranging five squares of equal size such that each square has at least one side coincident with another.

Can you cut a square into pieces such that the pieces can be arranged* into any pentomino (of the same area as the square)? What is the minimum number of pieces you need?

* translations, rotations and flipping of the pieces are all allowed

Title: Re: square to pentomino
Post by rmsgrey on Feb 5^th, 2005, 6:20pm

on 02/05/05 at 14:39:24, JocK wrote:

Pentominos are the rectangular shapes that originate when arranging five squares of equal size such that each square has at least one side coincident with another.

There's only one rectangular pentomino...

Without the rectangular requirement, your definition includes all the shapes you can make by randomly placing a domino and a tromino in the plane,as well as various non-planar shapes.

An alternate way of defining them is: "the shapes you can make by picking 5 orthogonally connected squares on a chessboard"

Title: Re: square to pentomino
Post by SWF on Feb 5^th, 2005, 7:17pm

The pentomino in the shape of a "+" cannot be made from a domino and a triomino.

One easy way, but perhaps not with the minimum piece count: [hide]Cut out two square pieces and a domino. The remainder easily be can be cut into pieces that form a rectangle. The rectangle is pretty simple to cut so it can form a square. The 3 squares and a domino can make all the required shapes.[/hide].

Title: Re: square to pentomino
Post by rmsgrey on Feb 5^th, 2005, 8:04pm

on 02/05/05 at 19:17:33, SWF wrote:

The pentomino in the shape of a "+" cannot be made from a domino and a triomino.

on 02/05/05 at 18:20:30, rmsgrey wrote:

Without the rectangular requirement, your definition includes all the shapes you can make by randomly placing a domino and a tromino in the plane, as well as various non-planar shapes.

So how many planar shapes which are not pentominoes fit JocK's definition but cannot be made up of a domino and a tromino?

Title: Re: square to pentomino
Post by JocK on Feb 6^th, 2005, 1:53am

on 02/05/05 at 18:20:30, rmsgrey wrote:

OK, OK, ... :-/

Will update the 'definition'...

on 02/05/05 at 18:20:30, rmsgrey wrote:

An alternate way of defining them is: "the shapes you can make by picking 5 orthogonally connected squares on a chessboard"

Are you sure that if I use this definition here I will not be asked the question "Define chessboard" ... ?

Title: Re: square to pentomino
Post by Grimbal on Feb 7^th, 2005, 2:38am

Whatever the definition, here is a list of all possible pentominoes.
http://www.theory.csc.uvic.ca/~cos/inf/misc/PentInfo.html

It is already an interesting question how to cut a square in a minimum number of pieces to make each of the pentominoes individually. But here, it seems we have to come up with a single set that will recombine into any one of the pentominoes.

I have a solution in 5 pieces. ::[hide]##################### #__####____________## #______####_______#_# #__________####__#__# #______________##___# ###____________#____# #__####_______#_____# #__#___####__#______# #_#________####_____# ##_____________####_# #####################[/hide]::

Title: Re: square to pentomino
Post by JocK on Feb 7^th, 2005, 3:24pm

If this works it beats my own solution.... :o

But... are you sure you can create all 12 pentominos from these five pieces? How would you rearrange the five pieces into a 5x1 bar?

Title: Re: square to pentomino
Post by Grimbal on Feb 8^th, 2005, 1:07am

Oops....

Don't you want me to do the W instead? :-[

Actually the + would also be a problem.

Title: Re: square to pentomino
Post by SWF on Feb 8^th, 2005, 5:07pm

Excuse me, rmsgrey, I thought you were suggesting a clue to the solution rather than pointing out an error in the phrasing of the question.

The following uses 7 pieces (pieces of the same color pair up to form either a domino or a square, 3 squares and a domino can make any pentomino):

Title: Re: square to pentomino
Post by JocK on Feb 9^th, 2005, 3:03pm

Yes, cutting two of Grimbal's pieces does the job. As long as Barukh doesn't post a solution with fewer pieces this is the optimum. 8)

Well done SWF.