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.
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.
選擇“Disable on www.wenxuecity.com”
選擇“don't run on pages on this domain”
