From May 2012, Communications of the ACM (wording reverse-engineered from the solution given in the June 2012 edition as I don't have the May 2012 edition handy).
Given a 5x5 grid of boxes, place diagonals within the boxes such that:
- each diagonal connects opposite corners of one of the 25 boxes;
- each box contains at most one diagonal; and
- each grid intersection (i.e. box corner) can have at most 1 diagonal touching it.
In the grid above, the diagonal at the top-left is ok. The top-left box has 2 corners with 1 diagonal touching and 2 corners with 0 diagonals touching. Note that the box on its right cannot have a NW-SE diagonal ('\') since the NW corner already touches a diagonal). The 2 red diagonals can't both be used because they touch a common grid intersection. You can flip one of the red diagonals so they are arranged like '//' or '\\' (either way would be ok in this example), or drop one or both of them.
Challenge: find the maximum number of diagonals that can be placed to satisfy the conditions, and prove that the number you found is maximal.