Pebble Placement
An exciting puzzle asked in the World's biggest Investment bank
Larry aims to place pebbles on an n × n chessboard in the following way. He must place each pebble at the center of a square and no two pebbles can be in the same square. To keep it interesting, Larry makes sure that no four pebbles form a non-degenerate parallelogram. A non degenerate parallelogram means a parallelogram with non zero area.
What is the maximum number of pebbles Larry can place on the chessboard?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
Solution
Short Solution → 2n -1 ; Place pebbles on every cell of first row and first column
Proof : Let’s say we can have max number of N pebbles on chessboard.
Consider the ith row has N_i pebbles. Let these N_i pebbles be located in columns
Now define,
Basically D_ij measures distance between first pebble in a row and the jth pebble in the same row. It is crucial to note that for the same row all D_ij are unique. Therefore we have N_i -1 unique values from each row.
If we sum these number of unique values across all rows we get →
For there to exist a non-degenerate parallelogram, there has to be two rows with the same distance between two beads. There are only n-1 possible distinct distances {1, 2, 3, … n-1 }.
By Pigeonhole principle, for N >= 2n there will be atleast two rows with pebbles having the same distances between them. We made sure that all the distances in the same row are distinct.
All that is left is to give one possible configuration in which 2n-1 pebbles can be placed following the given rules. We already did that in the short answer !!
.
.
😃 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!