Graph Theory: Paths and Circuits

Isomorphism

Two graphs are thought of as equivalent and are called isomorphic if they have identical behavior in terms of graph theoretic properties.

Two graphs G and G' are said to be isomorphic to each other if there is one-to-one correspondence between their vertices and between their edges such that the incidence relationship is preserved.

In other words suppose that edge e is incident on vertieces v₁ and v₂ in G; then corresponding edge e' in G' must be incident on the vertices v₁' and v₂' that correspond to v₁ and v₂ respectively.

Two isomorphic graphs must have:

1. The same number of vertices.

2. The same number of edges.

3. And equal number of vertices with a given degree.

These conditions are by no means sufficient. Finding simple and efficient criteria for detection of isomorphism is still actively pursued and is an important unsolved problem in graph theory.

Subgraph

Graph Theory: Introduction

Your browser does not support the canvas element.

Graph Definition

Graph is a collection of edges and vertices.

G = (V, E)

V is set of vertices and E is set of edges.

Each edge is identified with pair of vertices (v_i, v_j).

Vertices associated with edge ek are called the end vertices of e_k.

A vertex is also referred to as node, junction, point.

Other terms used for an edge are a branch, a line, an element.

Loop

An edge having the same vertex as both its end vertices is called as self loop or simply a loop.

Parallel Edges

Edges having same pair of vertices as their end veritices are called parallel edges.

Simple Graph

A graph that has neither self loops nor parallel edges is called simple graph.

Incidence

When a vertex v_i is n end vertex of some edge e_j, v_i and e_j are said to be incident to each other.

Adjacent

Two non-parallel edges are said to be adjacent if they are incident on a common vertex.

Two vertices are said to be adjacent if they are the end vertices of the same edge.

Degree of a vertex

The number of edges incident on a vertex v_i with self lopps counted twice is called the defree d(v_i) of vertex v_i.

Degree of vertexd is sometimes also referred to as its valency.

Hand Shaking Theorm

Since each edge contributes two degrees, the sum of the degrees of all vertices in graph G is twice the number of edges in G.

Sum(deg(v_i)) { for i = 1 to n } = 2 . e

n = number of vertices.

e = number of edges.

Theorm 1.1

The number of vertices of odd degree in a graph is always even.

sum of degrees of all vertices = sum of degrees of vertices with even degrees + sum of degrees of vertices with odd degree

Left Hand Side is even number. The first term in Right Hand Side is even number. So the second term in RHS also needs to be an even number. Hence the theorm.

Regular Graph

A graph in which all vertices are of equal degree is called a regular graph.

Isolated vertex

A vertex having no incident edge is called an isolated vertex. Isolated vertices are vertices with zero degrees.

Pendant Vertex

A vertex of degree one is called a pendant vertex or an end vertex.

Edges in series

Two adjacent edges are said to be in series if their common vertex is of degree two.

Null Graph

A graph without any edges is called a null graph. Every vertex in a null graph is an isolated vertex.

Prefix and Suffix sums puzzle

This is a problem related to prefix and suffix sums. Before mentioning the actual problem, let me first explain what are prefix and suffix sums.

What is mean by prefix sum? 
Consider an example for sequence of 3 integer numbers: 5  -2  7
The prefix numbers are: 5  3  10
These are generated as follows:
   5  (5+ (-2))   (5 + (-2) + 7)
= 5       3             10

What are suffix sums? 
For the same above example of 3 integer numbers, the suffix sums are: 7  5  10
These are generated as follows:
   7       (7 + (-2))    (7 + (-2) + 5)
= 7            5               10

Problem: 
Determine the number of different possible sequences of integers that can generate given prefix and suffix sums.

For example, following are all the prefix and suffix sums in some random order:
3  5  7  10  5  10

Since the count of above numbers is 6, the original sequence of numbers has to be 3. So the task is to find out how many different sequences of 3 integer numbers can result in same values of above mentioned prefix and suffix sums?

For this particular example, following are all possible sequences of 3 integer numbers whose prefix and suffix sums are: 3  5  7  10  5  10

5  -2  7
7  -2  5
3   2  5
5   2  3

The count of all possible integer sequences is 4 and hence the answer is 4 for this particular example.

In general, the problem can be stated as: Find out the count of sequences of n integer numbers whose prefix and suffix sums are equal to the given 2*n integer numbers mentioned in random order.

Algorithm

Let us consider sequence of n numbers as follows:

x1  x2  x3  . . .  xn

The prefix sums are:

x1  (x1+x2)  (x1+x2+x3)   (x1+x2+x3+x4)    . . .   (x1+x2+x3+...xn)

= n.x1 + (n-1).x2 + (n-2).x3 + . . . xn

Similarly, the suffix sums are:

xn  (xn+x(n-1))   (xn+x(n-1)+x(n-2))   (xn+x(n-1)+x(n-2)+x(n-3))   . . .   (xn+x(n-1)+x(n-2)+x(n-3)...x1)

= n.xn + (n-1).x(n-1) + (n-2).x(n-2) + . . . x1

If we add all prefix and suffix sums, the combined term becomes:

n.x1 + (n-1).x2 + (n-2).x3 + . . . xn
+
  x1 +     2.x2 +     3.x3 + . . . n.xn

= (n+1)x1 + (n+1)x2 +  (n+1)x3  + . . . (n+1)xn

= (n+1)(x1+x2+x3+...+xn)

= (n+1) . sum(x)

The value for sum(x) can be determined as follows:

sum(x) = (sum of all prefix and suffix sums) / (n+1)

Note that sum(x) may not be always the largest value especially if any of numbers in original list (x1 to xn) contains negative values. We can use above formula to determine the value of sum(x) in all cases, whether original sequence contains +ve or -ve numbers, it doesn't matter, the formula will give us the correct sum(x) value.

For example, consider following example with suffix and prefix sums (in some random order):

5  3  10  7  5  10

Sum of all above numbers is: 40 and n=3 so the sum of original numbers is 40/(3+1) = 10

I generated above prefix and suffix sums using 5  -2  7. There are other possible sequences that can result in same prefix and suffix sums, but their sum has to be 10.

Note that 10 appears twice. If sum(x) does not appear twice in given prefix and suffix sums, then, it is an invalid input and no solution is possible. So the result in such case is zero.

Remove the two sum(x) numbers from the list, and arrange the remaining numbers in ascending order:

3  5  5  7

Notice that addition of first and last numbers is also sum(x). Similarly, the addition of second and last but one is also sum(x). This is the case for all such pairs. If it is not, then, solution is not possible and the result is zero.

Why is this so? How can we draw such a conclusion?

Consider the original sequence: 5  -2  7
following table shows prefix and suffix sums for each of the position as follows:

Original numbers                       : 5  -2  7
Prefix sums(up to the position)   : 5   3  10
Suffix sums(up to next position) : 5   7  0
Addition of prefix & suffix sum  : 10  10 10

In above table, in each column, the value for prefix and suffix sums mentioned are for the two sub-lists of the original sequence. The addition of these two sub-lists equals the addition of all numbers from the entire list.

For example:
at position 1, the two sub-lists are: (5) (-2 7)
at position 2, the two sub-lists are: (5, -2) (7)
and at position 3, the two sub-lists are: () (5 -2 7)

The first sub-list is the prefix sum at that particular position, second sub-list is the suffix sum. Their sum must equal sum(x). Basically, it does not matter at which position the list of numbers is split in two parts; the sum of two sub-lists always must equal to the sum of entire list. Hence the proof.

Hence for each prefix sum there must exist one suffix sum such that their addition is equal to sum(x). If this is not the case, then, solution is not possible. And the answer is zero in such case.

So in above example, there are 2 pairs of prefix and suffix sums: (3 7) and (5 5).

One particular sequence of prefix sums uniquely defines sequence of original numbers. So to compute the number of original sequences, we need to determine the number of possible sequences of prefix sums.

For the given example, following are all possible permutations:

                                                Case 1           Case 2          Case 3          Case 4
Prefix sums                           :   3  5  10         7  5  10        5  3  10        5  7  10
Suffix sum up to next position :   7  5   0          3  5   0        5  7   0         5  3   0
original numbers                     :   3  2   5         7  -2  5        5  -2  7         5  2   3

For this example, the answer i.e. the count for different possible sequences is 4.

The prefix sums can be generated by permuting in following manner:

1. From the pair of prefix and suffix sum that adds to sum(x), any number can be prefix sum. So if these are different numbers, then, the possibilities are doubled.

2. We can arrange (n-1) prefix sums in any order. If all the prefix sum values are different, then, we will have (n-1)! number of counts for prefix sums. But if some prefix sums are repeated, then, the count can be obtained by using npr formula.

In general, there exists (n-1) pairs of prefix and suffix sums that add exactly to sum(x). Out of these, if any pair repeats, then we maintain a count of how many times that pair repeats. Let us say we have got "k" different pairs of prefix and suffix sums with counts as n1, n2, n3, . . . , nk where k is the number of unique pairs. And let us say "u" as the number of pairs containing different values for prefix and suffix sum, then the formula for count is:

     (n-1)! * 2 ^ u
________________________
(n1! * n2! * n3! . . . nk!) 

For above example:
n = 3
k = 2
n1 = 1 (pair: (3 7) appears once)
n2 = 1 (pair: (5 5) appears once)
u = 1 because there is only one pair (3 7) that has prefix sum != suffix sum.

Hence the count becomes:

(3-1)! * 2 ^ 1
________________   =  2*2 / 1  = 4
(1! * 1!)

Minimum number of weights problem

PROBLEM

Suppose a shop keeper needs to weigh all the weights from 1  kg to 121 kg (no fractions) i.e. 1 kg, 2 kg, 3 kg . . . up to 121 kg using balance. How can the shopkeeper choose minimum number of weights so that she/he will be able to weigh all the weights up to 121 kg? What are the values of individual weights?

Hint: It is allowed to put weights in both sides of measuring balance.

SOLUTION

Let { x(i) for i = 1 to n} denote the values of weights chosen.

The objective is to find values of x(i) so that weighing is possible for any number up to 121 kg. Since 121 kg is the maximum weight to be measured, we can choose all the weights such that their summation is greater than or equal to 121.

Hence { ∑ x(i) for i = 1 to n } >= 121

Let S(n) = { ∑ x(i) for i = 1 to n }

By definition
S(n-1) = { ∑ x(i) for i = 1 to (n-1) }

Therefore S(n) = S(n-1) + x(n)

Let us assume we know the values of x(i) for i = 1 to (n-1). And let us assume that these values are optimum values for measuring all the weights up to S(n-1). 

Given this, how can we choose the value of x(n) so that S(n) will be maximum and we will be able to measure all the additional weights from S(n-1)+1 to S(n)?

We should choose x(n) so that it satisfies following expression :

x(n) - S(n-1) = 1 + S(n-1)

Hence x(n) = 1 + 2 S(n-1)

By definition, S(n-1) = S(n-2) + x(n-1)

Hence x(n) = 1 + 2 [ S(n-2) + x(n-1) ]

                 = 1 + 2 S(n-2) + 2 x(n-1)

By definition we know 1 + 2 S(n-2) = x(n-1)

Hence x(n) = x(n-1) + 2 x(n-1) = 3 x(n-1)

Therefore x(n) = 3 x(n-1)

We know the base condition: x(1) = 1 and S(1) = 1

x(2) =  3 * x(1)      = 3 * 1 = 3
S(2) = S(1) + x(2) = 1 + 3 = 4

x(3) =  3 * x(2)      = 3 * 3 =  9
S(3) = S(2) + x(3) = 4 + 9 = 13

x(4) =  3 * x(3)      =  3 *  9 = 27
S(4) = S(3) + x(4) = 13 + 27 = 40

x(5) =  3 * x(4)      =  3 * 27 =  81
S(5) = S(4) + x(5) = 40 + 81 = 121

Since S(5) >= 121, we will stop here and the solution is 5 number of weights: [ 1  3  9  27  81]

Mathematically, { ∑ 3^i for i = 0 to n-1 } >= w (where w is the max weight to be measured, 121 in this example)

The mathematical formula for { ∑ 3^i for i = 0 to n-1 } = (3^n - 1)/2

Hence (3^n - 1)/2 >= w
(3^n - 1) >= 2w
3^n >= 1 + 2w

Hence n >= log3(1+2w)

The minimum integer value of n that satisfies above condition will be the answer for n i.e. optimum number of weights required to weigh up to w kg.

Alternatively n = log3(1+2w) 

If it comes in fraction then it needs to be rounded up.

for w = 121, n = log3(1+2*121) = log3(1+242) = log3(243) = 5

And values of weights are:

x(1) = 3^0 = 1
x(2) = 3^1 = 3
x(3) = 3^2 = 9
x(4) = 3^3 = 27
x(5) = 3^4 = 81

Generalized egg drop problem

Problem

Consider a building with f number of floors. Suppose there are e number of identical eggs. Any egg if dropped from certain floor and above, then it breaks; if it is dropped from below, then it will not break. The task is to identify such floor with minimum number of trials. If egg does not break then it can be re-dropped in next trials. 

Symbols 

Let 


    f = number floors in the building 
    e = number of eggs 
    n = number of trials 
    Fmax(e, n) = maximum number of floors that can be tested with e number of eggs and n number of trials. 

Solution

In the question, f and e are given and n i.e. optimum or minimum number of trials needs to be determined.


Let us assume we will try floors f1, f2, f3, . . . fk by assuming that egg never breaks. What this means is: first trial of egg drop is on floor f1; if it does not break then next trial of egg drop will be on floor f2 and so on up to floor fn assuming that first egg never breaks. Along with n we also need to find out the values for f1, f2, f3, . . . fk.

Now the question is: what should be the values of f1, f2, f3, . . . fk given f (number of floors) and e (number of eggs)? And how many optimum number of trials are needed?

 This problem can be solved with following 3 approaches:

1. Dynamic Programming
2. Binary Search Tree
3. Direct Mathematical formula 

Let us see each of these solutions below:

Solution using Dynamic Programming approach

Before solving the original problem of trying to find n given f and e let us shift our focus on determining the maximum number of floors that can be covered with n max trials and e number of eggs.


The answer to the optimum number of trials needed will be the minimum value of n for which Fmax(e, n) >= f


With e eggs and n drops, what is the value of Fmax(e, n) i.e. maximum number of floors that can be tested? And what should be the values of f1, f2, f3, . . . fn etc.?

Let us first try to determine the value for f1. On what basis should we choose f1?

All the floors are as follows:


1 2 3 4 . . . f1 (f1+1) (f1+2) (f1+3) . . . Fmax(e, n)


If egg breaks at f1 then we will be left with: 


    (f1-1) number of floors 
    (e-1) number of eggs and 
    (n-1) max trials that we can try further 

So we should choose f1 such that (f1-1) = Fmax(e-1, n-1)

Hence f1 = 1 + Fmax(e-1, n-1) 

If the egg does not break at f1 then we will be left with: 

    [ Fmax(e, n) - f1 ] number of floors 

    e number of eggs and 

    (n-1) max trials 

Hence we should choose Fmax(e, n) such that [ Fmax(e, n) - f1 ] is equal to the maximum number of trials possible with e number of eggs and (n-1) number of trials. 


Hence Fmax(e, n) - f1 = Fmax(e, n-1) Fmax(e, n) 
                      = f1 + Fmax(e, n-1) 
                      = 1 + Fmax(e-1, n-1) + Fmax(e, n-1) 


We have expressed the values of f1 and Fmax recursively with lower values for number of eggs and/or number of trials. Hence if we solve the smaller sub-problems recursively, we can find the value of Fmax(e, n) given e and n. And also we will be able to find the values of f2, f3, f4 . . . fn etc.


Finding the value for f2 reduces to smaller sub-problem of trying to find value of f1‘ with e number of eggs and (n-1) number of trials. The value of (f2-f1) should be equal to the maximum number of floors that can be covered with (e-1) eggs and (n-2) trials. 


Hence f2 = f1 + Fmax(e-1, n-2) + 1 

Similarly if egg does not break at f1 & f2 but suppose it breaks at f3 then we will be left with: (e-1) eggs and (n-3) max trials. 

Hence f3 = f2 + Fmax(e-1, n-3) + 1 

And so on 


Hence the floors in order are: 


[Fmax(e-1, n-1) number of floors ] f1 [Fmax(e-1, n-2) number of floors ] f2 [Fmax(e-1, n-3) number of floors ] f3 [Fmax(e-1, n-4) number of floors ] . . . Fmax(e, n) 


Hence Fmax(e, n) = { ∑ Fmax(e-1,i) for i=1 to (n-1) } + n 

Here is Java code using Dynamic Programming approach:

public class EggDropPuzzle
{
  public static void main(String args[])
  {
    final int nEggs   = Integer.parseInt(args[0]);
    final int nFloors = Integer.parseInt(args[1]);

    int res = findOptNumOfDrops(nEggs, nFloors);
       
    System.out.println("Number of drops needed for "+nFloors+" floors with "+nEggs+" eggs is : "+res);
}

  private static int findOptNumOfDrops(final int nEggs, final int nFloors)
  {
    int nTrials = (int)(Math.log(1+nFloors)/Math.log(2.0));
    int fmax = getFmax(nEggs, nTrials);

    while(fmax < nFloors)
    {
      nTrials++;
      fmax = getFmax(nEggs, nTrials);
    }

    return nTrials;
  }

  private static int getFmax(final int nEggs, final int nTrials)
  {
    if((0 == nEggs) || (0 == nTrials) )
      return 0;

          if(1 == nEggs)
    return nTrials;

    int fmax = 1 + getFmax(nEggs-1, nTrials-1) + getFmax(nEggs, nTrials-1);

    return fmax;
  }
}

we may improve above program by storing the results for Fmax so that the repeated calculations are avoided.

Solution using Binary Search Tree (BST) 

This problem can also be modeled with Binary Search Tree (BST).

In order to facilitate our analysis, let us draw BST with slight modifications as follows:

        1.    If egg breaks then child node is drawn on left down side

        2.    If egg does not break then child node is drawn straight down side

If we draw BST with above kind of representation then width of the BST represents the number of eggs. Width of BST is equal to number of vertical columns in BST.

Note that, for full BST drawn with above kind of representation, width = height

Any BST with f number of nodes, drawn with above kind of representation and subjected to the constraint width of BST <= e (number of eggs) is a solution but it may not be the optimal solution. Hence obtaining the optimal solution is equivalent to obtaining the arrangement of nodes in BST with minimum height subjected to the constraint: width of BST <= e

If full BST is possible with f number of nodes and if it also satisfies above constraint then such a full BST is itself the solution and height of the BST is optimum number of trials required.

Even if full BST is not possible with given number of floors (f), but if following conditions are met then also it is a solution:

e >= h where h is the height of the next possible full BST

F_h-1 < f <= F_h

Where F_h is the total number of nodes in full BST having height = h

Hence for given number of floors, first we will have to obtain the value of h. If e >= h then solution for optimal number of trials required = h.

But if e < h then optimum number of trials required will be definitely more than h.

In the BST drawn with our special kind of representation, every column corresponds to a particular number of egg breaks. For example, to reach any node in the right most column, we will need zero egg breaks. Whereas to reach any node in the left most column, we will need (width -1) number of egg breaks.

Hence, if e < h then we need to discard all the nodes in columns requiring more than e number of egg breaks. And these nodes needs to be inserted below the leaf nodes in remaining valid columns.

But if f < F_h then we need not insert all the nodes from invalid columns. The number of nodes to be inserted below the leaf nodes of valid columns = (total number of nodes in invalid columns) – (F_h-f) ---- (1)

If above figure comes negative then our task is done, the optimal number of trials required = h. We need not perform the removal process, because we are sure that the optimal number of trials required are at least h because we did choose h based on condition:

F_h-1 < f <= F_h

If the difference in (1) is a positive number then we have to perform the process of addition/insertion of nodes. In this case, we can keep e number of columns from right side and all the nodes from (width-e) number of left columns needs to be inserted below the e number of right columns. Hence obtaining optimal solution reduces to finding a way to insert these extra nodes below the leaf nodes of e number of right columns such that the max height of the BST is minimised.

Let us consider an example as follows:

e = 2

f = 12

for above example h = 4 because 2³ -1 < f <= 2⁴-1

Full BST with our special kind of representation of height = 4 is shown in the image above and its details are as follows:

Column number (left to right)	Nodes	Number of nodes	Leaf nodes	Number of leaf nodes	Number of egg breaks required to reach these nodes
0	1	1	1	1	3
1	2  3  5  9	4	3  5  9	3	2
2	4  6  7  10  11  13	6	7  11  13	3	1
3	8  12  14  15	4	15	1	0

This full BST has width = 4 and hence is not a valid solution because we have only 2 eggs. We need to move the nodes from columns 0 & 1 below the leaf nodes under columns 2 & 3.

The number of nodes at different columns follows the pattern of binomial coefficients as follows:

Number of nodes at column c = n_c = h!/(c! (h-c)!)

Where c starts from 0 and ends at (h-1)

Hence the total number of nodes in first two columns to be removed from full BST  = n₀ + n₁ = 4!/(0! (4 – 0)!) + 4!/(1! (4 – 1)!) = 1 + 4 = 5

But we need not insert all the 5 nodes, because f < F_h

Number of nodes to be inserted below the leaf nodes of columns 2 & 3 = 5 – (F_h-f) = 5 – (15 - 12) = 2

The number of leaf nodes at different columns also follows the pattern of binomial coefficients as follows:

Number of leaf nodes at column c = nl_c = (h-1)!/( c! (h-1-c)! )

Hence number of leaf nodes at columns 2 & 3 = 3!/(2! (4–1-2)!) + 3!/ (3! (4–1-3)!)= 3 + 1 = 4

Since in this case the number of leaf nodes is more than the number of nodes to be inserted, solution is trivial and is equal to 4 + 1 = 5

But if number of leaf nodes is less than the number of nodes to be inserted then insertion of nodes needs to be done iteratively and the leaf nodes at each iteration goes on increasing as follows :

Suppose the number of leaf nodes at valid columns = [4 6 1] and the number of nodes to be inserted = 30 then we have to perform two iterations as follows and the height will be 2 + height of full BST

Iteration number	Number of nodes that can be inserted in this iteration = number of leaf nodes at left most valid column + 2 * number of leaf nodes at remaining valid columns	Cumulative number of nodes inserted	New leaf nodes at valid columns =  Current number of leaf nodes + current number of leaf nodes at right column At right most column the number of leaf nodes stays same at all the iterations.
1	= 4 + 2*6 + 2 * 1  = 18	18	(4+6) (6+1)   1 =    10     7       1
2	= 10 + 2*7 + 2*1  = 26	44	(10+7) (7+1) 1 =   17      8    1

Here is the Java code written with this approach: 


public class EggBST
{
    public static void main(String args[])
    {
        final int nEggs = Integer.parseInt(args[0]);
        final int nFloors = Integer.parseInt(args[1]);

        int res = findOptNumOfDrops(nEggs, nFloors);

        System.out.println("Number of drops needed for " + nFloors
                + " floors with " + nEggs + " eggs is : " + res);
    }

    private static int findOptNumOfDrops(final int nEggs, final int nFloors)
    {
        int nTrials = (int)(Math.log(1+nFloors)/Math.log(2.0));
        int fmax = (int)Math.pow(2, nTrials) - 1;
        while(fmax < nFloors)
        {
            nTrials++;
            fmax = (int)Math.pow(2, nTrials) - 1;
        }

        if(nTrials <= nEggs)
            return nTrials;

        int extraNodes = fmax - nFloors;

        int leftNodes = 0;
        long kmod = fact(nTrials);
        for(int i=0; i < nTrials - nEggs ; i++)
            leftNodes += kmod/(fact(i)*fact(nTrials-i));

        if(extraNodes >= leftNodes)
            return nTrials;

        if(extraNodes < leftNodes)
        {
            int nNodes = leftNodes - extraNodes;
            int[] leafNodes = new int[nEggs];
            kmod = fact(nTrials-1);
            for(int i=0; i < nEggs ; i++)
                leafNodes[i] = (int)(kmod/(fact(nTrials-nEggs+i)*fact(nEggs-i-1)));

            int h = 0;
            while(nNodes > 0)
            {
                h++;
                for(int i=0;i < nEggs ; i++ )
                {
                    if(i == 0)
                        nNodes = nNodes - leafNodes[0];
                    else
                        nNodes = nNodes - leafNodes[i] * 2;
                }

                for(int i=0;i < nEggs-1 ; i++)
                    leafNodes[i] = leafNodes[i]+leafNodes[i+1];
            }

            nTrials = nTrials + h;
        }

        return nTrials;
    }

    private static long fact(int n)
    {
        if (n == 0)
            return 1;

        long res = 1;
        for (int i = 1; i <= n; i++)
            res = res * i;

        return res;
    }
}

3. Solution using Direct Mathematical formula for Fmax

from the analysis done with Dynamic Programming approach, we already know the recursive formula for Fmax as follows:

Fmax(e, n) = { ∑ Fmax(e-1,i) for i=1 to (n-1) } + n

with slight modification, it can be expressed as follows:



Fmax(e, n) = { ∑Fmax(e-1,i) for i = 1 to n } - Fmax(e-1, n) + n 


Above expression for Fmax is the basis for obtaining direct formula for Fmax for any value of e and n.

Let us determine Fmax for increasing values of e

Fmax(1, n) = n - this is the base condition we already know

Fmax(2, n) = { ∑Fmax(1,i) for i = 1 to n } - Fmax(1, n) + n 
                   = ∑n – n + n 
                = ∑n

Fmax(3, n) = { ∑Fmax(2,i) for i = 1 to n } - Fmax(2, n) + n 
                   = ∑∑n – ∑n + n 

Fmax(4, n) = { ∑Fmax(3,i) for i = 1 to n } - Fmax(3, n) + n 
                   = ∑∑∑n – ∑∑n + ∑n - (∑∑n – ∑n + n) + n 
                   = ∑∑∑n - 2 ∑∑n + 2 ∑n 
  
Fmax(5, n) = { ∑Fmax(4,i) for i = 1 to n } - Fmax(4, n) + n 
                   = ∑∑∑∑n - 2 ∑∑∑n + 2 ∑∑n - (∑∑∑n - 2 ∑∑n + 2 ∑n) + n 
                   = ∑∑∑∑n - 3 ∑∑∑n + 4 ∑∑n - 2 ∑n + n

. . .

In general the equation for F_max(e, n) can be obtained by finding the coefficients for different summations as follows:

Number of eggs	Coefficients of summations
1	1 Hence Fmax(1, n) = n
2	1  1         --- append 1 to the right side of previous coefficients [1] -       1    --- subtract previous coefficients = 1  0    --- result for new coefficients Hence Fmax(2, n) = ∑n
3	1   0   1  --- append 1 to the right side of previous coefficients [1 0] -       1  0  --- subtract previous coefficients = 1  -1  1  --- result for new coefficients Hence Fmax(3, n) = ∑∑n - ∑n + n
4	1   -1   1   1  --- append 1 to the right side of previous coefficients [1 -1  1] -        1  -1   1 --- subtract previous coefficients =  1   -2  2   0 --- result for new coefficients Hence Fmax(4, n) = ∑∑∑n – 2 ∑∑n + 2 ∑n
5	1   -2   2   0   1  --- append 1 to the right side of previous coeffs [1 -2 2 0] -         1  -2   2   0 --- subtract previous coefficients =  1   -3   4   -2  1 --- result for new coefficients Hence Fmax(5, n) = ∑∑∑∑n – 3 ∑∑∑n + 4 ∑∑n – 2 ∑n + n
…	…

The formula for ∑∑∑ … k times sum … ∑ n = n (n+1) (n+2) … (n+k-1) / (k+1)!

Hence the procedure for  obtaining the value of optimum number of required drops for given e number of eggs and f number of floors is as follows:

• Based on given value for e, first obtain the formula for Fmax in terms of n.
• Start with log2(1+f) as a value for n and determine value of Fmax. Go on incrementing the value of n till Fmax < f. When Fmax >= f then the value of n is the answer for optimum number of trials required.

The formula for Fmax is a polynomial equation whose degree is equal to e.

Now let us consider specific cases of e =2, 3, 4 for understanding the way to obtain solution using Mathematical approach:

2 eggs case

Let us solve the puzzle for 2 eggs case. Let us first obtain the formula for Fmax(2, n) i.e. maximum number of floors that can be covered with 2 eggs and n number of max trials.


Fmax(2, n) = { ∑Fmax(1,i) for i = 1 to n } - Fmax(1, n) + n
           =  ∑n + n - n
           =  ∑n
           = n(n+1)/2

Alternatively, from the table for determination of coefficients for summations, we already know the coefficients in case of e=2 are : [1 0 ] and hence we will directly obtain the same above formula.

Note: We know Fmax(1,i) = i because with one egg and i number of trials we can cover at the most i number of floors.

Hence, given 2 eggs and max n number of trials, we can cover at the most n(n+1)/2 number of floors. 

Hence the problem of finding optimum number of trials given 2 eggs and f number of floors reduces to finding the value of n such that:


n(n+1)/2 >= f


The minimum value of n that satisfies above condition will be the answer. If it comes in fraction then we have to round it up.


And the floor numbers are as follows:


f1 =  1 + Fmax(1, n-1)     = 1 + n-1               = n 
f2 = f1 + Fmax(1, n-2) + 1 = n + (n–2) + 1         = n + (n-1) 
f3 = f2 + Fmax(1, n-3) + 1 = n + (n-1) + (n–3) + 1 = n + (n-1) + (n–2) 

. . . 

Fmax(2, n) = n + (n - 1) + (n – 2) + . . . + 1 = n(n+1)/2 


Given a building with 100 floors and 2 eggs, the optimum number of trials needed are : 14 because it is the minimum integer value of n that satisfies the condition n(n+1)/2 >= 100. 

And the floor numbers are :


f1  = 1   + Fmax(1, 13)      = 1 + 13      = 14 
f2  = f1  + Fmax(1, 12) + 1  = 14 + 12 + 1 = 27 
f3  = f2  + Fmax(1, 11) + 1  = 27 + 11 + 1 = 39 
f4  = f3  + Fmax(1, 10) + 1  = 39 + 10 + 1 = 50 
f5  = f4  + Fmax(1, 9)  + 1  = 50 + 9 + 1  = 60 
f6  = f5  + Fmax(1, 8)  + 1  = 27 + 8 + 1  = 69 
f7  = f6  + Fmax(1, 7)  + 1  = 39 + 7 + 1  = 77 
f8  = f7  + Fmax(1, 6)  + 1  = 14 + 6 + 1  = 84 
f9  = f8  + Fmax(1, 5)  + 1  = 27 + 5 + 1  = 90 
f10 = f9  + Fmax(1, 4)  + 1  = 39 + 4 + 1  = 95 
f11 = f10 + Fmax(1, 3)  + 1  = 39 + 3 + 1  = 99 
f12 = f11 + Fmax(1, 2)  + 1  = 39 + 2 + 1  = 102 stop here & perform trial for 100 instead. 
f13 = f12 + Fmax(1, 1)  + 1  = 39 + 1 + 1  = 104 
f14 = f13 + Fmax(1, 0)  + 1  = 39 + 0 + 1  = 105 

Notice that since 100 < 102, we will have to try from f1 to f11 and then last try for floor 100. Although the count of trials at this level is only 12, but still the optimum number of trials required are 14. 


3 eggs case


Now let us determine Fmax for the 3 eggs case


The floors in order can be expressed as follows:


[Fmax(2, n-1) number of floors ] f1 [Fmax(2, n-2) number of floors ] f2 [Fmax(2, n-3) number of floors ] f3 [Fmax(2, n-4) number of floors ] . . . Fmax(3, n) 

We already know that the coefficients of summations in case of e=3 are [1 -1 1]
Hence Fmax(3, n) = ∑∑n - ∑n + n
                 = n(n+1)(n+2)/6 - n(n+1)/2 + n
                 = n/6 [ (n+1)(n+2) - 3(n+1) + 6 ]
                 = n/6 [ n*n+3n+2 -3n-3 + 6 ]
                 = n/6 [ n*n + 5 ]
                 = [n*n*n + 5n]/6

Hence, given 3 eggs and max n number of trials, we can cover at the most [ n*n*n + 5n ] / 6 number of floors. 


Hence the problem of finding optimum number of trials given 3 eggs and f number of floors reduces to finding the value of n such that:

[ n*n*n + 5n ]/6 >= f


The minimum value of n that satisfies above condition will be the answer. If it comes in fraction then we have to round it up.


And the floor numbers are as follows:


f1 = 1 + Fmax(2, n-1) = 1 + n(n-1)/2 
f2 = f1 + Fmax(2, n-2) + 1 = 2 + n(n-1)/2 + (n-1)(n-2)/2 
f3 = f2 + Fmax(2, n-3) + 1 = 3 + n(n-1)/2 + (n-1)(n-2)/2 + (n-2)(n-3)/2 

. . . 

Fmax(3, n) = [ n*n*n + 5n ]/6 


Given a building with 100 floors and 3 eggs, the optimum number of trials needed are : 9 because it is the minimum integer value of n that satisfies the condition:
[ n*n*n + 5n ]/6 >= 100. 

And the floor numbers are : 


f1 = 1  + Fmax(2, 8)     = 1   + 8*9/2      = 37 
f2 = f1 + Fmax(2, 7) + 1 = 37  + 7*8/2 + 1  = 66 
f3 = f2 + Fmax(2, 6) + 1 = 66  + 6*7/2 + 1  = 88 
f4 = f3 + Fmax(2, 5) + 1 = 88  + 5*6/2 + 1  = 104 stop here & perform trial for 100 instead. 
f5 = f4 + Fmax(2, 4) + 1 = 104 + 4*5/2 + 1  = 115 
f6 = f5 + Fmax(2, 3) + 1 = 115 + 3*4/2 + 1  = 122 
f7 = f6 + Fmax(2, 2) + 1 = 122 + 2*3/2 + 1  = 126 
f8 = f7 + Fmax(2, 1) + 1 = 126 + 1*2/2 + 1  = 128 
f9 = f8 + Fmax(2, 0) + 1 = 134 + 0 + 1      = 129 

Notice that since 100 > 104, we will have to try from f1 to f3 and then last try for floor 100. Although the count of trials at this level is only 4, but still the optimum number of trials required are 9.

4 eggs case

Now let us determine Fmax for the 4 eggs case

The floors in order can be expressed as follows:

[Fmax(3, n-1) number of floors ]    f1    [Fmax(3, n-2) number of floors ]    f2    [Fmax(3, n-3) number of floors ]    f3    [Fmax(3, n-4) number of floors ]   .  .  .   Fmax(4, n)

We already know that the coefficients of summations in case of e=4 are [1 -2  2  0]

Hence Fmax(4, n) = ∑∑∑n - 2 ∑∑n + 2 ∑n 
                 = n(n+1)(n+2)(n+3)/24 - 2 n(n+1)(n+2)/6 + n(n+1)
                 = n(n+1)/24 [ (n+2)(n+3) - 8(n+2) + 24 ]
                 = n(n+1)/24 [ n*n+5n+6 -8n-16 + 24 ]
                 = n(n+1)/24 [ n*n-3n+14 ]
                 = n[n*n*n -3n*n + 14n + n*n-3n+14 ]/24
                 = n [n*n*n - 2n*n + 11n + 14]/24

Hence, given 4 eggs and max n number of trials, we can cover at the most n[ n*n*n - 2n*n + 11n + 14]/24 number of floors.

Hence the problem of finding optimum number of trials given 4 eggs and f number of floors reduces to finding the value of n such that:

n[ n*n*n - 2n*n + 11n + 14] / 24 >= f

The minimum value of `n` that satisfies above condition will be the answer. If it comes in fraction then we have to round it up.

And the floor numbers are as follows:

f1  =  1 + Fmax(3, n-1)     = 1  + [(n-1)(n-1)(n-1) + 5(n-1)]/6

f2  = f1 + Fmax(3, n-2) + 1 = f1 + [(n-2)(n-2)(n-2) + 5(n-2)]/6 + 1

f3  = f2 + Fmax(3, n-3) + 1 = f2 + [(n-3)(n-3)(n-3) + 5(n-3)]/6 + 1

. . .

Fmax(4, n) = n[ n*n*n - 2n*n + 11n + 14] / 24

Given a building with 100 floors and 4 eggs, the optimum number of trials needed are 8 because it is the minimum integer value of n that satisfies the condition:

    n[ n*n*n - 2n*n + 11n + 14] / 24 >= 100

And the floor numbers are :

f1  =  1  + Fmax(3, 7)      =  1  + (7*7*7+5*7)/6     = 1   + 63     = 64

f2  = f1  + Fmax(3, 6) + 1  =  64 + (6*6*6+5*6)/6 + 1 = 64  + 41 + 1 = 106 stop here and perform trial for 100 instead

f3  = f2  + Fmax(3, 5) + 1  = 106 + (5*5*5+5*5)/6 + 1 = 106 + 25 + 1 = 132

f4  = f3  + Fmax(3, 4) + 1  = 132 + (4*4*4+5*4)/6 + 1 = 132 + 14 + 1 = 147

f5  = f4  + Fmax(3, 3) + 1  = 147 + (3*3*3+5*3)/6 + 1 = 147 + 25 + 1 = 155

f6  = f5  + Fmax(3, 2) + 1  = 155 + (2*2*2+5*2)/6 + 1 = 155 +  3 + 1 = 159

f7  = f6  + Fmax(3, 1) + 1  = 159 + (1*1*1+5*1)/6 + 1 = 159 +  1 + 1 = 161

f8  = f7  + Fmax(3, 0) + 1  = 161 + 0             + 1 = 161 +  0 + 1 = 162

Notice that since 100 < 106, we will have to perform trials for f1 and 100 only. 

Although the count of trials at this level is only 2, but still the optimum number of trials required are 8.

Here is the Java code for determining optimum number of drops for given eggs and given number of floors:


public class EggDropMath
{
   
    public static void main(String[] args)
    {
        int nEggs   = Integer.parseInt(args[0]);
        int nFloors = Integer.parseInt(args[1]);

        int res = GetOptimumNumOfTrials(nEggs, nFloors);
        System.out.print("Optimum number of drops required = "+res);
    }

    private static int GetOptimumNumOfTrials(int nEggs, int nFloors)
    {
        if( (nEggs == 0) || (nFloors == 0) )
            return 0;
       
        if(nEggs == 1)
            return nFloors;
   
        int n = (int)(Math.log(nFloors+1)/Math.log(2));
       
        int[] coeffs = getCoeffs(nEggs);
       
        long sums[] = getSums(n, nEggs);
       
        int fmax = GetFmax(coeffs, sums);
       
        while(fmax < nFloors)
        {
            n++;
            getNextSums(sums);
            fmax = GetFmax(coeffs, sums);
        }

        return n;
    }

    private static void getNextSums(long[] sums)
    {
        int n = (int)sums[sums.length-1];
       
        for(int i=0; i < sums.length ; i++)
            sums[sums.length-i-1] = (sums[sums.length-i-1]*(n+i+1))/n;
    }

    private static long[] getSums(int n, int nEggs)
    {
        long[] sums = new long[nEggs];
       
        sums[nEggs-1] = n;
       
        for(int i = nEggs-2 ; i >= 0 ; i--)
        {
            sums[i] = n;
            for(int j = 1 ; j < nEggs-i ; j++)
                sums[i] = sums[i]*(n+j)/(j+1);
        }
       
        return sums;
    }

    private static int[] getCoeffs(int nEggs)
    {
        int[] coeffs = new int[nEggs];
       
        coeffs[0] = 1;
       
        for(int i = 1 ; i < nEggs ; i++)
        {
            coeffs[i] = 1;
            for(int j=i; j > 0 ; j--)
                coeffs[j] =  coeffs[j]-coeffs[j-1];
        }

        return coeffs;
    }
    private static int GetFmax(int[] coeffs, long[] sums)
    {
       
        int fmax = 0;
       
        for(int i=0;i < coeffs.length ; i++)
            fmax += coeffs[i]*sums[i];
       
        return fmax;
    }
}