I would like to see the full induction proof because I currently have a pretty weak understanding of writing proofs… Right now we have, "The idea is that the pairing for the first city must be optimum, since if it were to be paired with any other city, we could always change its pairing to be with the nearest black city without adding any road."
Do we need to mention the other pairings that this change might affect? The other white city that was originally paired with the first city’s nearest black city needs to then be paired with the black city that the first city just changed from. Do we need a step that proves that this too won’t add any road?
Bottom of page 35 in the Java book.
Edit: Had another question. Decided to add it here because it’s short and wasn’t sure if it warranted another post…
2)The Mboard problem on the previous page seems to be making many leaps, like going from a (n+1)x(n+1) board to a 2n by 2n board. It also feels unnatural to generalize from a concrete 8 x 8 board to a n x n board. I feel like I would never be able to figure out this stuff on my own?