Pebble Placement Puzzle 2
Source: AUSTMS Gazette 35
Related Problem: Pebble Placement Puzzle 1
Problem: Peggy aims to place pebbles on an n × n chessboard in the following way. She must place each pebble at the center of a square and no two pebbles can be in the same square. To keep it interesting, Peggy makes sure that no four pebbles form a non-degenerate parallelogram.
What is the maximum number of pebbles Peggy can place on the chessboard?
What does it mean to have a non-degenerate parallelogram?
ReplyDeleteAns: 2n – 1.
ReplyDeleteProof:
Let the ith row have Ni pebbles. Let the column in which jth of these lies be denoted by Cij (1 <= j <= Ni). Now if there exist 2 rows, each of which have 2 pebbles, equal number of columns apart, we’d get a non-degenerate parallelogram.
Let’s denote the total number of pebbles by N = ∑i Ni
Consider the differences Dij = Cij - Ci1 … (2 <= j <= Ni). Thus, across all the rows, we have ∑i (Ni – 1) = N-n such differences. Now, the distinct values which a difference can have, are 1,2,..,n-1 i.e. n-1 of them. Thus, if N >= 2n, we’d have 2 (among >=n) differences which are equal (by pigeon hole :P). Note that these 2 differences are not in the same row, as per their construction. Hence, we’d have a non-degenerate parallelogram. Now, we show with an example, that N=2n-1 is possible -> just completely fill the 1st row and the 1st column.
Ans: 2n - 1
ReplyDeleteProof:
Put all the pebbles in the first row and first column i.e. 2n - 1 pebbles (as the corner square is common). With this configuration, placing a pebble anywhere on the board results in a parallelogram. Therefore, we cannot place any other pebble anywhere on the board, giving the maximum pebbles as 2n - 1.
Hey Tushar, I think proving that you cannot add pebbles to one particular configuration, only ensures that the configuration is optimal, but it need not be optimum.
DeleteNon-degenerate means having >0 area.
ReplyDelete