CSE Blog - quant, math, computer science puzzles

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? Solution: Highlight the part between the * symbols for the answer. * Answer: 2n - 1. Construction: fill the entire first row and first column - 2n - 1 pebbles. Any further pebble at (r, c) completes a rectangle (a non-degenerate parallelogram) with the pebbles at (r, 1), (1, c) and (1, 1), so nothing more can be added. Upper bound: suppose row i contains N_i pebbles in columns C_i1 < C_i2 < ... . Within row i, consider the N_i - 1 differences C_ij - C_i1 (j >= 2). Across all rows this gives N - n differences, where N is the total number of pebbles, e...

Source: AUSTMS Gazette 35 Problem: There are several pebbles placed on an n × n chessboard, such that each pebble is inside a square and no two pebbles share the same square. Perry decides to play the following game. At each turn, he moves one of the pebbles to an empty neighboring square. After a while, Perry notices that every pebble has passed through every square of the chessboard exactly once and has come back to its original position. Prove that there was a moment when no pebble was on its original position. Solution: Highlight the part between the * symbols for the answer. * Consider the moment just before the FIRST pebble (call it x) completes its tour - i.e. x has visited every square exactly once and is about to step back onto its original square. At that moment, look at any other pebble y. If y were sitting on its own original square, there are two possibilities. Either y left at some point and came back - but then y had already completed a full tour and returned...