wu :: forums - Print Page


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

        riddles >> medium >> Checkerboard Puzzle from AMC 2017
        
(Message started by: dudiobugtron on Aug 9^th, 2018, 7:44pm)

Title: Checkerboard Puzzle from AMC 2017
Post by dudiobugtron on Aug 9^th, 2018, 7:44pm

I saw this puzzle in the 2017 Australian Mathematics Competition (https://www.amt.edu.au/mathematics/amc/), and thought it was interesting enough to share. It's a problem intended for high achieving secondary school maths students, and prepared from memory so might differ from the actual puzzle slightly:

---------------------------------------------------

Imagine an 8x8 checkerboard where we are free to choose the colour of each square to be black or white as needed, as long as we preserve the following property: each 2x2 group of squares on the checkerboard must contain exactly 2 black squares and 2 white squares. How many different such colourings of an 8x8 checkerboard are possible? (The orientation of the checkerboard is fixed, which means two patterns that are rotations of one another can still count as distinct.)

------------------------
And just so I can include it in the medium forum:
Can you extend this to an nxn checkerboard? An nxm one?

(PS: I am interested to see different approaches as well, so please feel free to include your answer even if someone else has already solved the puzzle.)

Title: Re: Checkerboard Puzzle from AMC 2017
Post by Grimbal on Aug 10^th, 2018, 5:12am

For an MxN board it shoud be
[hide] 2^M + 2^N - 2. [/hide]
because
[hideb]
Consider the separation lines between black and white.
If you take a 2x2 square there are only 3 possibilities: either it is split horizontally, or vertically, or both.
In all cases a separation line continues straight to the next column or row. This means that the separation lines always run across the whole board, either horizontally or vertically, They never stop or turn at a crossing.

You just need to see what combination of horizontal and vertical separation lines are valid.

If a horizontal line is not a separation line, then all vertical lines must be separation lines, or the crossing of the two would be a 2x2 unicolor square. Therefore, either all horizontal or all vertical lines are separation lines.

To count the possibilities, we have to consider the 2 cases. Either all horizontal lines are separation lines and any combination of the (N-1) vertical lines are, which gives 2^(N-1) ways, or it is the other way round with 2^(M-1) ways. You need to subtract 1 because you count twice the case of all separation lines present, and multiply by 2 because the top left corner can be black or white.

This gives the answer:
2*(2^(M-1) + 2^(N-1) - 1) = 2^M + 2^N - 2
[/hideb]

Title: Re: Checkerboard Puzzle from AMC 2017
Post by rmsgrey on Aug 10^th, 2018, 9:20am

I agree with Grimbal's answer, but vary slightly in my solution:

[hideb]The first key insight is the same - if you take any adjacent pair of squares (say, horizontal neighbours), then if they're different colours, then the pair of squares directly above (or below) them must also differ, and similarly for the pair matching. In other words, if you split your board by separating each square from orthogonally adjacent squares of the other colour, any splits will run fully across the board - you can't have any splits starting/ending in the middle of the board. Further, if you have two the same colour next to each other (horizontally, say) then the 2-wide column they're in must switch colours every row as you go down the column. So you must have every possible horizontal split or every possible vertical split.

My second insight is that once you have a single row and a single column from a solution, you have enough information to uniquely determine that solution - where the two cross you have three of four squares, which determines the fourth, giving you a new L-shape that lets you iterate along the row, and one that lets you start the next row.

Combine the two insights, and you get that either the first row or the first column must alternate, while the other can be any combination of colours (if you have two columns of alternating colours next to each other, then they can be in matching or opposing phase and either will work). So there are 2^n boards with alternating columns and an arbitrary row, and 2^m boards with alternating rows and an arbitrary column. However, there are the two checkerboard patterns which each are both an alternating row with an arbitrary column and an alternating column with an arbitrary row, so get counted twice.

Final total: 2^m + 2^n - 2[/hideb]

Title: Re: Checkerboard Puzzle from AMC 2017
Post by dudiobugtron on Aug 19^th, 2018, 7:15pm

Awesome solutions, thanks!!

I am especially fond of rmsgrey's 'second insight'.