Problem #151
The Pebble Game
Given a Directed Acyclic Graph ( DAG ) , at a given instant of time we can do one of the following two operations:
1) Place pebble on a node,if all its immediate ancestors have a pebble
2) Remove pebble from a node.
Initially, there are no pebbles on any node of the DAG.
Our goal is to minimize the maximum number of pebbles over time such that finally, pebbles are on all leaf nodes (nodes with no outgoing edges) . Assume all DAGs of the form: 2 equal height full binary trees, one kept inverted. The leaves of each binary tree are at the same level.
Eg.: This is a DAG made to resemble 2 binary trees of height 2.
Say F(n) = Answer for a DAG similar to 2 binary trees of height n .
Find \sum_{i=0}^{20} F(i)