Olympiad Math Problem
This is a question from Arthur Engel: "Prove that an axb chessboard can be covered by nx1 tiles iff n|a or n|b". I have seen the solution but am not 'convinced' by it. Can anyone please help?
21 Replies
@Apu
Note for OP
+solved @user1 @user2... to close the thread when your doubt is solved. Mention the users who helped you solve the doubt. This will be added to their stats.what solution did you see
there is a paper on that problem, with 10-15 different solutions
It is something like this: Colouring the pieces of the chessboard as shown and then I tried making a system of equations to show some contradiction.
aahhh
good proof
if n divides a or b then you can basically cut the board into pieces
that part is obvious to you right?
Yes.
great
see it this way
take n different colors
start painting the board, alternating between colors
if every color appears equal number of times, we are done
that makes sense?
Yeah.
great
try to see it this way now
if n does not divide a or b
let a= cn +r1
now you can basically prove that there will be some colors with unequal number of squares
this is basically that proof
Oh.
Thanks a lot.
i hope this makes sense i’m not able to put it very well
like if it is cn+r every color will be c times
except some
thats what the proof is
it’s very rigorous
ug math required (not necessarily though 😉 )
That is a good explanation. Thanks.
it’s not mine
i have worked on that book
i read a paper related to this long back
the explanation in that was similar
i just put it like that
wait let me cite
Yeah. I saw the solution in the book, but got lost somewhere in between. Now I see what the author was trying to say.
Packing a Rectangle with Congruent N-ominoes DAVID A. KLARNER
McMas'ter University, Hamilton, Ontario, Canada Communicated b)' Gian-Carlo Rota Received April 1968
ABSTRACT
Golomb defines a polyomino (a generalized domino) to be a finite set of rook-wise connected cells in an infinite chessboard. In this note we discuss problems concerning the packing of rectangles with congruent polyominoes. Many of these problems are unsolved.
this is a very good proof
Will have a look at this too. Once again, thanks a ton.
anytime :))
+solved @πrate
Post locked and archived successfully!
Archived by
<@1075951732460376214> (1075951732460376214)
Time
<t:1718803362:R>
Solved by
<@408610503376764929> (408610503376764929)