Coins on Chessboard
Asked in Quant Research Internship interview at Alphagrep
You are given a chessboard with 8X8 dimensions. Your friend Tim asks you how many ways there are to place coins on the chessboard such that there are even number of coins in each row and in each column. Can you find it out?
Note: You can place only one coin in each square box.
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
Let’s break this into smaller problems and try to solve those.
There are 2 ways to fill a 2x2 board, i.e., all boxes filled or empty. The sum of coins in each row is even, and the column is even ( 0 or 2 ).
Try to do this for 3x3 board; you would have counted 16 ways to fill the board.
Observe that for a given NxN board, if you consider the top left (N-1)x(N-1) board, then no matter how you fill it. There is a way to fill the rightmost column and bottom row to make the sum of all rows and columns even. For that, count the sum of all rows of (N-1)x(N-1) board, fill the rightmost column to make them even, and now do the same for all N columns. For each placement on the (N-1)x(N-1) board, there is just one unique way to fill the right column and last row.
Therefore the answer is the number of ways to fill the (N-1)x(N-1) board. Each cell has two choices; either place a coin or don’t. Therefore the total number of ways = 2^((N-1)^2)
Number of ways to fill chessboard = 2^49
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!