Re: Partition a square into rectangles
- From: Risto Lankinen <rlankine@xxxxxxxxx>
- Date: Wed, 4 Jun 2008 10:32:31 -0700 (PDT)
On 2 kesä, 19:52, no.glam...@xxxxxxxxx wrote:
Hello,
Prove/disprove that a 3000X3000 square can be partitioned into 5X9
rectangles (the rectangles can be mixed, either 5X9 or 7X9).
Well this is not using graph theory, but anyway...
Define coordinates (X,Y) to all squares. Label every
square (X,Y) with a number (X+Y) MOD 9 = 0..8 .
It's easy to prove that both a 5x9 and a 9x5 rectangle
cover an equal number (=5) of each distinct label.
It's also easy to prove that a 3000x3000 square has a
different number of some labels (for example, the grand
diagonal will be labeled "3", which there will be more
than e.g. "2"s or "4"s).
In any case, because all placements of a 5x9 or 9x5
rectangle consume an equal amount of distinct labels
whilst the numbers of labels in a 3000x3000 are not
equal, then it is not possible to cover all labeled
squares simultaneously.
- Risto -
.
- Follow-Ups:
- Re: Partition a square into rectangles
- From: Dan Hoey
- Re: Partition a square into rectangles
- References:
- Partition a square into rectangles
- From: no . glamour
- Partition a square into rectangles
- Prev by Date: Re: Partition a square into rectangles
- Next by Date: Re: Validating a completed sudoku grid
- Previous by thread: Re: Partition a square into rectangles
- Next by thread: Re: Partition a square into rectangles
- Index(es):
Relevant Pages
|
