2n

First, start with a weaker question: let’s only worry about the right angles formed from “straight” lines. For example, the right angle in (0, 0), (1, 1), (0, 2) doesn’t count.

Let’s mark the points on the board as (i, j), i, j=0 to n.

For the best solution, there is at least one point in 2n+1 points on (0, 0 to n) and (0 to n, 0) that is not marked, let’s call it (0, x). If x is not 0, switch column x with column 0. So we’ll have (0,0) unmarked.

Now look at the n x n square, (1 to n, 1 to n). For any point (i,j), i,j=1,…,n. If there is another point (i,j’), j’=1,…,n, on its row, then (0,j) and (0,j’) must be unmarked. Switch marks on (i,j), (i.j’) to (0,j), (0,j’) without changing the total number of marks.

Similar if there are multiple points on a column.

If there is no other point on the row and the column of (i,j) in the n x n square . Then either (i,0) or (j,0) is unmarked or both. Switch (i,j) with the unmarked point.

At the end, the best one can do is to mark all the points on (0, 1 to n) and (1 to n, 0).

If one choose to do so to start with, there are no right angles formed from “not straight” lines.

所有跟帖： 

• 2n對了 -康MM- ♀ (0 bytes) () 07/17/2009 postreply 17:20:19