Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Nov 9, 2014

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?

4 comments:

  1. What does it mean to have a non-degenerate parallelogram?

    ReplyDelete
  2. Ans: 2n – 1.
    Proof:
    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.

    ReplyDelete
  3. Ans: 2n - 1

    Proof:

    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.

    ReplyDelete
    Replies
    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.

      Delete