wu :: forums - Print Page


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

        riddles >> medium >> How to cover a 23x23 matrix with 1x1, 2x2 and 3x3
        
(Message started by: jollytall on Sep 10^th, 2012, 12:43am)

Title: How to cover a 23x23 matrix with 1x1, 2x2 and 3x3
Post by jollytall on Sep 10^th, 2012, 12:43am

Can you cover a 23x23 matrix with exactly 1 piece of 1x1 square and any number of 2x2 and 3x3 pieces?
It has to cover one single layer, no empty square left and no piece cutting.

Title: Re: How to cover a 23x23 matrix with 1x1, 2x2 and
Post by towr on Sep 10^th, 2012, 1:30am

Yes, it seems I can, see attachment.

Title: Re: How to cover a 23x23 matrix with 1x1, 2x2 and
Post by jollytall on Sep 10^th, 2012, 1:58am

Great solution. Thanks.
Once you have the 11x11 in the middle, any number from13 upwards can also be solved. Put the 11x11 in the corner and build around 2x2 or 3x3 bands on two sides.

Title: Re: How to cover a 23x23 matrix with 1x1, 2x2 and
Post by towr on Sep 10^th, 2012, 2:27am

Err, are you sure? 11 isn't divisible by two (nor three), so how would you put a 2x2 (or 3x3) band on two sides?

[e](which isn't to say I can't make solution for 13x13)[/e]

Title: Re: How to cover a 23x23 matrix with 1x1, 2x2 and
Post by jollytall on Sep 10^th, 2012, 3:39am

Ooops, no.
I can increase any number (>1) by 6 only (not 2 and 3 separately).
So indeed from 11, we have 11+6k, including 23.

13x13 I also have using a 6x7 block around the 1x1. That gives an easy 13+6k series.
Using the m*(m+1) logic in a spiral around the small piece, I can only make if m or m+1 is divedable by 6.

What other numbers are doable, if any, if we use another pattern?

Title: Re: How to cover a 23x23 matrix with 1x1, 2x2 and
Post by Grimbal on Sep 11^th, 2012, 10:07am

I know at least one other size:
[hide] 1x1 ... [/hide]

But I wonder if sizes NxN are possible where N is a multiple of 2 or 3.

Title: Re: How to cover a 23x23 matrix with 1x1, 2x2 and
Post by towr on Sep 13^th, 2012, 10:33am

I've had a program run through everything up to 18x18, and 1, 11, 13 and 17 are the only ones with solutions in that range.
I haven't found a way to prove multiples of 2 and 3 don't have solutions yet, but one of the main problem would be getting the same parity of 3x3's in every column/row that doesn't contain the 1x1. I don't see how you'd manage that if you have an odd number of 3x3's, as you'd have for a 3n x 3n square.