Problem. Lets consider a binary tree T. Every node of this tree is colored by blue or red. Every leaf of this tree is colored by red. We say that node is good if it is a leaf or node is red and children are good. Node is maximal good if node is good and it's parent isn't. The tree contains at least one blue node.
There are no two maximal good nodes connected by red path. Prove that number of maximal good nodes with blue parent is greater than number of maximal good nodes with red.
I know two proofs of this fact. But I don't like both. I still think there is an elegant proof.
I think you mean 'greater or equal' or something is missing. In the attached tree A is maximal good with red parent and B is maximal good with blue parent and no other nodes are good
Yes. I said that tree is binary. I meant that every internal node has exactly two children.
There's still something that I'm missing, in the attached tree A nodes are maximal good with red parent and B nodes are maximal good with blue parent and no other nodes are maximal good. The same example holds for a complete tree where all the missing nodes are red (all goods but none maximal).
Now, the example violates constraint "There are no two maximal good nodes connected by red path".
I mean full binary tree (not complete) in wikipedia terms (http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees).
ok, so if I got it right a maximal good node with red parent has either:
1 - a blue 'brother', in this case prove that there are at least 2 maximal good nodes with blue parent descending from the brother
2 - a red 'brother' which is non-good, in this case one descendant (of the brother) must be blue and you can refer to the previous proof for at least 2 maximal good nodes with blue parent
Lastly the red path constraint should be enough to prove that the blue nodes named in 1 and 2 can not be 'shared' among maximal good nodes with red parent, so that at least one of the the 2 maximal good descending nodes with blue parent can't be 'shared'. You conclude that the maximal good nodes with blue parent are at least equal to the maximal good nodes with red parent + 1.
Sounds like you may find a very similar proof for the related Red-Black tree data structure within the constraints of your problem. I recommend looking up proofs for the properties of the Red Black tree, and I assure you, you will find the proof you're seeking. Most of the proofs for that type of tree are induction, or appeal to definition.
Marco Vassura, yes 1 and 2 are ok.
I don't understand what do you mean about "sharing" blue nodes. Could you explain it?
Daniel Page, yes, the tree structure suggests to use induction. But it's not a red-black tree. Actually, this tree is a circuit representation of a propositional formula.
with 'share' I mean more than 1 maximal good node with red parent (MGR) with the same blue brother (case 1, impossible in a binary tree) or with the same blue descendant of the brother (case 2, to prove that it is impossible the red path constraint is needed). This means that the number of blue nodes is greater or equal to the number of MGR. Now I realize that instead of defining a 'sharing' property also for the maximal good nodes with blue parent (MGB) is better to prove that number of MGB is greater than the number of blue nodes.
It's not so clear about second case. Look at example.pdf. I think that MGRs labeled '!' share same blue descendant of their brothers. You can assume that every blue node has some subtree.
ok, we can rephrase it like this: for each MGR M there is at least one blue node B in the subtree rooted at the brother of M such that if B becomes red the only MGR which could change to non-maximal is M. This again means that the number of blue nodes is greater than or equal to the number of MGR (simply change the blue nodes M to red ones one at a time).
- Badges
- Science topic
- Similar topics
- Philosophy
- Moral Philosophy
- Free Will