Q: A diamond of size n consists of 2n rows of nodes with lengths from top to bottom being 1, 3, 5, ..., 2n-1, 2n-1, 2n-3, ..., 3, 1. The middle nodes of all rows are in the same column. For instance the following '+' show a diamond of size 3:
##+##
#+++#
+++++
+++++
#+++#
##+##
We want to partition each diamond into acyclic paths such that each node is contained in exactly one path. A path is a sequence of distinct nodes in which neighboring nodes are horizontally or vertically adjacent. Prove that for diamond of size n the number of paths is at least n.
Proof:
We'll prove by induction. The case for n=1 is trivial. Now as an example consider a diamond of size 4. We draw part of it below where 'X' denote nodes of diamond we don't quite care:
A
BC
XDE
XXFG
XXIH
XLJ
NP
Q
A useful argument we name OA (optimality argument) is that if a node has only one neighbor, connecting it to its neighbor doesn't affect optimality. Suppose x has only one neighbor y and is not connected to y. If in some optimal partitioning y is an endpoint of some path, certainly adding x to that path reduces number of paths; if y is in the middle of some path, splitting that path at y and connecting x with y gives the same number of paths.
With OA, we connect AB. If C is connected with B then regard ABC as a super node C' with only one neighbor D; if C is not connected with B then C has only one neighbor D. In either case we are allowed to connect C with D using OA. Similarly, either E or super node CDE or super node ABCDE has only one neighbor F and thus we connect E with F. By symmetry we connect N with Q, L with P, I with J.
Next we argue that at least one pair of FG and IH can be connected. If not, G and H should be connected for optimality and is regarded as a super node; if EFIJ is a sub-path then EFGHIJ reduces number of paths by 1; if EFIJ is not a sub-path then we can split EFX... and attach GH to F without increasing number of paths. In either case, connecting FG or IH does not affect optimality.
Suppose FG is connected. Because from G we can't go beyond Q and never reach D, we connect DE and hence BC. Now ABCDEFG is a super node with one neighbor H so we connect GH, IH, JL, NP in order. This leaves us a path that can't be further extended and the rest is a diamond of size 3.
Q. E. D.
No comments:
Post a Comment