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

        riddles >> easy >> Russian Math Olympiad prob (6x6 board)
        
(Message started by: Aryabhatta on Dec 14th, 2005, 2:12am)
Title: Russian Math Olympiad prob (6x6 board)
Post by Aryabhatta on Dec 14th, 2005, 2:12am
You have a 6x6 board which I tile exactly with eighteen 2x1 dominos.

Show that you can find a straight line which divides the board into two (not necessarily equal) parts, such that no domino is cut by that line.
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by pcbouhid on Dec 14th, 2005, 4:35am
What am I missing? If you place 3 dominoes in each row, the job is done, and you achieve not one by 7 lines.
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by towr on Dec 14th, 2005, 4:39am
You're supposed to show that no matter how the dominos cover the board, you can cut the board in two. Not that it's possible for at least one covering.
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by pcbouhid on Dec 14th, 2005, 4:44am
(wrong comment)
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by towr on Dec 14th, 2005, 4:51am
Well it does say that he tiles the board. So you don't have any choice in what you're presented with. ;)
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by pcbouhid on Dec 14th, 2005, 4:55am
You´re right, towr. I missed that part. What a nice problem!
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by rmsgrey on Dec 14th, 2005, 5:40am
Related problem: what (if any) is the smallest board (greater than 2*1) that can be tiled by dominoes without having fault lines - no straight line crossing the board without crossing any dominoes.

The hard part for the original problem is proving impossibility - finding examples with fault lines is easy enough...
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by Grimbal on Dec 14th, 2005, 6:41am
I have seen this problem before.  But maybe not on this forum.

hint:
1. [hide]How many dominos do you need to cross each fault line at least once?[/hide]
2. [hide]Is there a reason why you would need more than on domino on a fault line?[/hide]
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by JohanC on Dec 14th, 2005, 6:43am
Interesting problem, Aryabhatta.
I think I have a solution:
[hide]a) There are 18 dominos.
b) There are 10 (5 horizontal and 5 vertical) possible cut lines.
c) One domino interupts exactly one of these 10 lines.
d) If a cut line is interupted with one domino, there necessarily needs to be a second domino also cutting that line.
Otherwise, if you would cut the board via that line, there would be an odd number of cells (2 for each whole domino, and 1 for the cut one). This is a contradiction, as the number of element at each side is a multiple of 6.
e) So suppose all 10 lines would be interupted, there would be 20 dominos needed, while there are only 18.[/hide]
Maybe somebody finds a shorter form of an answer?
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by pcbouhid on Dec 14th, 2005, 7:09am
I made this way: coloring the cells in a chessboard way, every domino MUST cover a "1" cell and a "0" cell.

Obvously, the line that will divide the grid must be "horizontal" or "vertical" (is the same thing).

If it is impossible to divide the board with a straight line, we must have, when traced the line that cuts one or more dominoes, a different number of "1"´s and "0"´s in both sides.

Looking at the drawing we see that there´s no way to achieve this.

Anybody could tell me if this is enough or not?
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by towr on Dec 14th, 2005, 7:39am

on 12/14/05 at 05:40:33, rmsgrey wrote:
Related problem: what (if any) is the smallest board (greater than 2*1) that can be tiled by dominoes without having fault lines - no straight line crossing the board without crossing any dominoes.
8x8 seem to work
Taking JohanC's solution as a place to start, it would be the first square board that has a solution.

pcbouhid's argument seems to contradict the possibility for all boards, so given that I found a solution for 8x8 I'd have to say it's flawed.
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by Sjoerd Job Postmus on Dec 14th, 2005, 7:44am
Blegh! I can block you at a 8x8 block, but not at a 6x6 block?

Blegh! Well, I'll let you to proof it!
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by towr on Dec 14th, 2005, 7:58am
here's the covering for 8x8 btw
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by SMQ on Dec 14th, 2005, 8:19am

on 12/14/05 at 07:09:43, pcbouhid wrote:
If it is impossible to divide the board with a straight line, we must have, when traced the line that cuts one or more dominoes, a different number of "1"´s and "0"´s in both sides.

Only if an odd number of dominoes cut the line.  If an even number cut the line they can balance out the sides.

--SMQ
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by JohanC on Dec 14th, 2005, 8:21am
It's also possible to create such a cut-blocking domino covering for a 5x6 board.

Anybody got a smaller board?
(A 3xN board seems to be provable impossible too.)
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by JohanC on Dec 14th, 2005, 8:27am

on 12/14/05 at 05:40:33, rmsgrey wrote:
Related problem: what (if any) is the smallest board (greater than 2*1) that can be tiled by dominoes without having fault lines - no straight line crossing the board without crossing any dominoes.


If your "boards" don't need to be rectangular, a 3x3 with a hole in the middle would do.
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by JohanC on Dec 14th, 2005, 8:41am
Here is my 5x6 example (after drawing it in Excel, as my droodle wasn't publishable).

Is this the only 5x6 solution (except from rotations and reflections)?
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by Aryabhatta on Dec 14th, 2005, 9:09am

on 12/14/05 at 06:43:03, JohanC wrote:
[hide]
d) If a cut line is interupted with one domino, there necessarily needs to be a second domino also cutting that line.
Otherwise, if you would cut the board via that line, there would be an odd number of cells (2 for each whole domino, and 1 for the cut one). This is a contradiction, as the number of element at each side is a multiple of 6.
[/hide]


The reasoning for d is not convincing.

For instance, what prevents

XX|YY
 A|A
 B|C
 B|C
 D|E
 D|E

from happening somewhere in the middle? (only the AA domino is cut by the vertical line)
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by SMQ on Dec 14th, 2005, 9:35am

on 12/14/05 at 09:09:34, Aryabhatta wrote:
what prevents

XX|YY
 A|A
 B|C
 B|C
 D|E
 D|E

from happening somewhere in the middle?

But there are now 6i+5 squares to the left of that formation and 6j+5 squares to the right (where i+j=4); since both of these are odd numbers, neither of the remaining areas can be completely tiled by dominoes.

--SMQ
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by Aryabhatta on Dec 14th, 2005, 9:48am
Yes.. I misread JohanC's post. I assumed he was talking about a single row of 6, not the whole sub-part which is formed.

Well done..
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by Joe Fendel on Dec 14th, 2005, 11:02am
JohanC's argument works for n x m boards where:

A) If n, m are both even and (n - 4)*(m - 4) < 8 or
B) If n is odd, m is even, and (n - 2)*(m - 4) < 2

I.e. for these boards, there is always a fault line.

If n = 3, it's also easy to see that there must be a fault line if you just work on it for a short while.

Thus the smallest conceivable no-fault boards are 5 x 6 for the odd x even case and 8 x 6 for the even x even case.  Sounds like we've found a 5 x 6 one and an 8 x 8 one.

So is there a 8 x 6 case?  And is there a process for generating no-fault arrangements for larger boards?
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by JohanC on Dec 14th, 2005, 2:12pm
Hi, Joe,

I had to think a little bit about your reasoning about the 4x5 case. We need 2 dominos for each of the 4 lines that divide the board in even parts. And 1 domino for each of the 3 lines in the other direction. So, at least 11 blocking dominos needed while there are only 10 available.


on 12/14/05 at 11:02:35, Joe Fendel wrote:
So is there a 8 x 6 case?


Yes, there is.
But I think it is not unique (contrary to the 6x5 case).


on 12/14/05 at 11:02:35, Joe Fendel wrote:
And is there a process for generating no-fault arrangements for larger boards?


It is quite straightforward: starting from a smaller board, moving all dominos from the rightmost row two places to the right and filling the gap with horizontally placed dominos. The gap is never straight, so also the new lines will be broken.
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by JohanC on Dec 15th, 2005, 1:20am

on 12/15/05 at 00:40:27, Grimbal wrote:
1x2  ;D

That would have been a solution, if [hide]rmsgrey didn't explicitely exclude it in his original post[/hide].
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by Grimbal on Dec 15th, 2005, 1:34am
OK, ok.

I checked 3xN and 4xN are impossible (generate fault lines).  So 5x6 is the smallest.
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by Joe Fendel on Dec 15th, 2005, 7:20am

on 12/14/05 at 11:02:35, Joe Fendel wrote:
B) If n is odd, m is even, and (n - 2)*(m - 4) < 2


Just rechecked this.  It should be

(n - 3)*(m - 4) < 4

This explicitly excludes the n = 3 case, also.

JohanC, your method for generating larger boards is sound (and quite simple, I'm embarrassed I couldn't think of it).
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by JohanC on Dec 15th, 2005, 8:20am
Here's another 6x8.
Anybody knows how many exist?
Title: Re: Russian Math Olympiad prob (6x6 board)
Post by JocK on Dec 16th, 2005, 11:22am
What about periodic boundary conditions?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board