beetles in a grid
Source: 2012 China TST Test 3 p6
March 26, 2012
vectorgeometrygeometric transformationanalytic geometrycombinatorics proposedcombinatorics
Problem Statement
In some squares of a grid there are some beetles, such that no square contain more than one beetle. At one moment, all the beetles fly off the grid and then land on the grid again, also satisfying the condition that there is at most one beetle standing in each square. The vector from the centre of the square from which a beetle flies to the centre of the square on which it lands is called the translation vector of beetle .
For all possible starting and ending configurations, find the maximum length of the sum of the translation vectors of all beetles.