Loading web-font TeX/Math/Italic

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)

Contributed by Aashaka Shah

Solved by 38 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.