Author |
Topic: Russian Math Olympiad prob (6x6 board) (Read 7433 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Russian Math Olympiad prob (6x6 board)
« on: Dec 14th, 2005, 2:12am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #1 on: Dec 14th, 2005, 4:35am » |
Quote Modify
|
What am I missing? If you place 3 dominoes in each row, the job is done, and you achieve not one by 7 lines.
|
|
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #2 on: Dec 14th, 2005, 4:39am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #3 on: Dec 14th, 2005, 4:44am » |
Quote Modify
|
(wrong comment)
|
| « Last Edit: Dec 14th, 2005, 4:55am by pcbouhid » |
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #4 on: Dec 14th, 2005, 4:51am » |
Quote Modify
|
Well it does say that he tiles the board. So you don't have any choice in what you're presented with. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #5 on: Dec 14th, 2005, 4:55am » |
Quote Modify
|
You´re right, towr. I missed that part. What a nice problem!
|
| « Last Edit: Dec 14th, 2005, 5:42am by pcbouhid » |
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #6 on: Dec 14th, 2005, 5:40am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #7 on: Dec 14th, 2005, 6:41am » |
Quote Modify
|
I have seen this problem before. But maybe not on this forum.
hint:
1. How many dominos do you need to cross each fault line at least once?
2. Is there a reason why you would need more than on domino on a fault line?
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #8 on: Dec 14th, 2005, 6:43am » |
Quote Modify
|
Interesting problem, Aryabhatta.
I think I have a solution:
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.
Maybe somebody finds a shorter form of an answer?
|
|
IP Logged |
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
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?
|
|
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #10 on: Dec 14th, 2005, 7:39am » |
Quote Modify
|
on Dec 14th, 2005, 5:40am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #11 on: Dec 14th, 2005, 7:44am » |
Quote Modify
|
Blegh! I can block you at a 8x8 block, but not at a 6x6 block?
Blegh! Well, I'll let you to proof it!
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #13 on: Dec 14th, 2005, 8:19am » |
Quote Modify
|
on Dec 14th, 2005, 7:09am, 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
|
|
IP Logged |
--SMQ
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #14 on: Dec 14th, 2005, 8:21am » |
Quote Modify
|
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.)
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #15 on: Dec 14th, 2005, 8:27am » |
Quote Modify
|
on Dec 14th, 2005, 5:40am, 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.
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
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)?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #17 on: Dec 14th, 2005, 9:09am » |
Quote Modify
|
on Dec 14th, 2005, 6:43am, JohanC wrote:
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.
|
|
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)
|
| « Last Edit: Dec 14th, 2005, 9:10am by Aryabhatta » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #18 on: Dec 14th, 2005, 9:35am » |
Quote Modify
|
on Dec 14th, 2005, 9:09am, 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
|
|
IP Logged |
--SMQ
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #19 on: Dec 14th, 2005, 9:48am » |
Quote Modify
|
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..
|
|
IP Logged |
|
|
|
Joe Fendel
Junior Member
Posts: 68
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #20 on: Dec 14th, 2005, 11:02am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
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 Dec 14th, 2005, 11:02am, 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 Dec 14th, 2005, 11:02am, 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.
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #22 on: Dec 15th, 2005, 1:20am » |
Quote Modify
|
on Dec 15th, 2005, 12:40am, Grimbal wrote:
1x2  |
|
That would have been a solution, if rmsgrey didn't explicitely exclude it in his original post.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #23 on: Dec 15th, 2005, 1:34am » |
Quote Modify
|
OK, ok.
I checked 3xN and 4xN are impossible (generate fault lines). So 5x6 is the smallest.
|
|
IP Logged |
|
|
|
Joe Fendel
Junior Member
Posts: 68
|
|
Re: Russian Math Olympiad prob (6x6 board)
« Reply #24 on: Dec 15th, 2005, 7:20am » |
Quote Modify
|
on Dec 14th, 2005, 11:02am, 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).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
noncutabledominocovering.png
5x6-uncutable.zip