COMMATICS

Dedicated to Mathematicians.

This page is a collection of problems from Computer science and Mathematics. Hence the title. The list shall grow as I encounter interesting problems. Correct me if I am wrong in any approach. I would be glad if you could offer me alternate/better approaches for solving a problem. (Identity will not be hidden.) NONE OF THESE PROBLEMS HAVE ORIGINATED FROM MY BRAIN. I had tried to give a solution. I believe that there will not be any copyright issues involved. If you feel that you should be given credit for inventing the problem, I am glad to do that. If you feel that your problem should not be featured here, I am glad to remove it. Thanks for your patience.

Sarnath.K (sparc64@rediffmail.com and sarnath@lycos.com )

Zero Dominated Binary String.

Here is a small mathematical puzzle. There are classical solutions available for this problem on NET, algorithm Books etc. I have just added my solution (and hence perspective) to this problem.
(I think this category of problems belong to catalan numbers.).

Problem statement
Given                    Binary String of Length "N"
Given Property     The string is such that the number of 0's is greater than or equal the number of 1's.
                             And, all prefixes of this string exhibit this property.
Assume                 Assume that the string has "K" zeroes ( and hence N-K One's )
Find what ?           Find the number of such strings which exhibit this property in terms of  N and K.
Correct Answer    Combination (N, K) - Combination(N,K-1)

Solution
Let us call a string exhibiting this property as a "zero dominated string", ZDS for short. (This is my own nomenclature).
Lets start with a string of length N with K zeroes. Lets denote the P(i,j) as the set of all strings of length "i" with "j" number of zeroes such that the above properties are maintained. Finding the cardinality of  P(N,K) in terms of N and K should solve the problem.

• It can be noted that P(N,K) is grown from either P(N-1, K) and P(N-1, K-1) by addition of 1 or 0.
• It can be noted that appending a "0" to all strings in the set P(N-1, K-1) would result in a ZDS with length N and K number of zeroes.
• Appending  "1"s to certain strings in the set P(N-1,K) would result in ZDS with length N and K zeroes.  Not all strings would generate a ZDS because strings which have equal number of zeroes and ones would not generate a ZDS if a 1 is appended to them. Thus if (2*K == N-1) we cannot generate P(N,K) from the set P(N-1,K). Otherwise we can generate.

Taking the above two points in consideration, we can deduce a recurrence relation as follows:

If ( 2 * K  != N-1)
    Cardinality of P(N,K) = Cardinality of P(N-1, K-1)   +  Cardinality of  P(N-1, K)  
ELSE
    Cardinality of P(N,K) = Cardinality of P(N-1, K-1)

P(1,1) = {0}. Cardinality = 1.
P(1,0) = {}. Cardinality = 0.

Feed this recurrence relation to your computer and get answer ;-) If u expand the sequence , u should end up with the above mentioned "correct answer". There are people who had taken a combinatorial approach to the problem. That should capture the big picture behind the problem. The ZDS solved by a LDB ( Left Hemisphere Dominated Brain) would look like mine. The same solved by a RDB would make use of combinatorics.

The following is a small "C" program which would do it for us.
The perfect mathematician would rather expand the recurrence than feeding this to computer.

/*
 *  Program demonstrating ZDS. Zero Dominated String.
 */
int main()
{
        printf("\nValue = %d\n",f(20,13));
        return 0;
}

int f( int n, int k )
{
        if (k <= 0 || k > n) /* Trap awkward inputs */
                return 0;

        if ( n == 1 )
                return 1;

        if ( 2*k != n-1 )
                return f(n-1,k-1)  + f(n-1,k);
        else
                return f(n-1,k-1);
}

Complexity of AVL_DELETION

·          This section assumes that the reader knows about the standard AVL_DELETION algorithm.

·          Tree always refers to a "binary tree".

·          LS(N) -> Height of left Sub tree of a node N.

·          RS(N) -> Height of Right Sub tree of a node N.

·          H(N) -> Maximum of LS(N) or RS(N).

Aim: 
    To prove that the worst case complexity of AVL_DELETION algorithm is exactly "(Log(N) to base 2) / 2" where "N" represents the number of nodes in the AVL tree.

Proof:
   It is very easy to see that the worst case complexity of AVL_DELETION is really Log(N) to base 2 under the light that the algorithm loops from a leaf to the root. But still it can be further proved that the worst case number of deletions is really "Log(N) to base 2 / 2". It cannot be greater that that.

   In order to evaluate the number of operations involved in AVL_DELETION algorithm (We shall consider the double rotations as a single operation) let us consider an AVL_DELETION happening in a tree which results in a ripple that is carried to the ROOT of the tree. (This is the worst case scenario). We shall investigate about what properties the tree should exhibit so that an AVL_DELETION produces such a ripple.

    Let us consider a scenario in which a node is being deleted in the system. (just deleted.. not avl_deleted). We can always identify the first nearest node to get imbalanced by this deletion. Let us call this node as "N". Now lets assume that "N" has got RIGHT_IMBALANCED, without losing any generality. Let us say LS(N) ="h" and RS(N)="h+2". H(N) = h+2 (both before deletion and after the deletion. Because RIGHT_IMBALANCED occurs because of a deletion in the LEFT_SUBTREE.). During the process of AVL_DELETION the Node "N" is replaced by some other node called "N1" (In order to balance "N" the algorithm does a rotation operation which makes a node N1 as the new root of the sub tree. Since we are investigating the worst case scenario, such a balancing will cause a reduction in the height of the sub tree. Since we are assuming the worst case scenario, this reduction in height will cause an imbalance to the parent of the sub tree). Now LS(N1) = h+1 and RS(N1) = h+1 and H(N1) = h+1. Thus if the ripple has to proceed up to root, this ripple needs to reach N1's parent. Further without losing generality we can assume that "N1" forms the LEFT_SUBTREE of its parent. ( One can also choose RIGHT_SUBTREE. No hassles). Lets call this parent as "P".

Before Deletion
    LS (P) = 1 + H(N) before deletion = h+3
    RS (P) = {h+3, h+4, h+2}. We cannot predict. It can be any of them.

After Deletion
  LS(P) = 1 +  H(N1) = h+2.
  RS(P) = h+4. This is because we want the ripple to be carried away to the root. Thus only if RS(P) were h+4. the ripple caused by the deletion would be carried to the parent.

Thus for a ripple to be carried over to a parent from his left sub tree, the height of his right sub tree should be one more than his left sub tree i.e. he should be right skewed before deletion.  Similar argument holds for a ripple to be carried over to a parent from his right sub tree.

Thus if after K ripples we reach the root, the height of the other sub tree of the root =  h +2 + 2*K.
This value is nothing but the Height of the entire tree.

Thus H(ROOT) =  h +2 + 2*K.

 K = (H(ROOT) - (h+2)) / 2. This is the biggest value that can be assumed by "K" starting for a sub tree of height "h+2". The least value of h+2 is 2.

Thus max value of K is, K = (H(ROOT) -2) / 2 = (Height/2 -1).

PROBABILITY Puzzle

Given: A function "F" which generates "1" and "0" with probability "p" and "1-p" respectively.

Problem: Construct a function "E" using "F" (and "F" only.) such that it generates "1" and "0" with equal probability.

Solution: Return "F" and complement of "F" on alternate invocations. That would do ! More generally the function "E" should generate "F" and complement of "F" on alternate intervals of "M" invocations where "M" can be any positive integer. The former solution is a case where M=1.

Justification: Consider an interval "M" in which "E" has returned "F"'s output without any change. Thus "E" would have generated M*p number of "1" and M*(1-p) number of "0". In the next consecutive interval "M", "E" will generate M*(1-p) number of "1" and M*p number of "0". Thus over the interval 2*M, the function "E" has generated M number of "0" and M number of "1" which is nothing but equal probability.

TWO MATHEMATICIANS PROBLEM

Problem Statement

Two mathematicians are placed in two rooms and one is given the sum of two distinct numbers between 2 and 99 (2 and 99 excluded) and the other is given the product of same two numbers. They both come out of the room and the following conversation takes place.

Mathematician with product: "I don't know the two numbers".

Mathematician with sum: "I know, you won't know the two numbers".

Mathematician with product: "Now, I know the numbers".

Mathematician with Sum: "Now, I too know the numbers".

The question is what are the numbers and how did they find it out?

SOLUTION

Since PRODUCT mathematician is unable to find the individual numbers, the PRODUCT is not expressible as Product of two prime numbers.

Since SUM mathematician tells that he knows for sure that the PRODUCT mathematician would not have found the numbers, the SUM is not expressible as SUM of two PRIME NUMBERS. It the SUM is expressible so, then the SUM mathematician cannot make such a statement with 100% surety. He can only make a GUESS.

Digress

All EVEN numbers can be expressed as "Sum of 2 Prime numbers". This is a conjecture (I guess it has neither been proved nor disproved nearly for the past 400 years. You may want to try it out. If this surmise is proved someday then one can give one another proof that prime numbers are infinite.). The above surmise works fine for all numbers that are less than 196. So we can conveniently use the surmise for solving the problem. However it is not being used here to solve the problem for some reasons that will follow.

End of Digress

Now we are in search of 2 numbers such that:

Special Cases

• There is a special case we need to handle in this problem. We had seen that if the PRODUCT can be expressed as PRODUCT of two prime numbers then it cannot be further factorized. Consider this factor pair: {4 * Prime Number} - The only other factor pair such a product can have is {2 * (2* Prime Number)}. However in our problem statement "2" is not included in the set of eligible numbers. Thus if the PRODUCT mathematician is given a product which can be expressed as {4 * Prime Number} then he can immediately find the individual numbers. From the SUM mathematician's perspective his SUM should not be expressible as {SUM of TWO prime numbers} OR {SUM of a PRIME NUMBER and 4}. This fact should be considered to get the unique solution for this problem.

·        There is also another special case that needs to be addressed. Consider the PRODUCT of a prime number P, with its 2nd multiple 2*P. The factor pair {P, 2*P} can be further simplified into only one another factor-pair {2, P*P}. Since “2” is not an eligible number, the second factor-pair should be dropped. Thus the SUM mathematician cannot get a number that can be expressed as 3*P (P + 2*P) where P is a prime number. If such a SUM is given to the SUM mathematician, he can never make a statement that the PRODUCT mathematician would not have found the number pairs.

Answer (Not yet certified by anyone.)

The answer is {13,16}. This is the only pair that satisfies the condition. I wrote a program to find out the numbers. One of my transitive friends from Anna University has solved it without using a computer. (By cornering out numbers and by employing some good tactics).  (If A is friend of B and B is friend of C then A and C are transitive friends). The solution given by him follows.

Hariharan’s Tactics:

Courtesy: S.Hariharan, Anna University from Chennai

Note: This method was construed when the given set of numbers starts from 2 and the sum of the two numbers is less than 100. It can be tailored or extrapolated for other versions.  

S.Hariharan from Anna University used the following line of thought to narrow down the search for the numbers. From the PRODUCT mathematician’s perspective, out of the entire factor pairs only one factor pair’s SUM must be ODD and all others must be EVEN. Let us call the unique factor pairs as O and E (derived from Odd and Even). O has to be PRIME because if it is not prime then O can be expressed as some X * Y (where both X and Y are ODD.). Thus the PRODUCT can also be expressed as X * (Y*E) as well as Y * (X*E). Both Y*E and X*E are Even. This inhibits the PRODUCT mathematician from finding out the individual pairs. So O is PRIME. Now consider “E”.  If E is expressible as PRODUCT of an Odd and an Even then – Let us say

E = O1 * E1. Thus the PRODUCT can be expressed as O1 * (E1 * E). Thus the product has another pair O1 and E2 that is ODD and EVEN. This scenario is avoided only if O1 == O and E1*E == E i.e {E1 = 1}. This means that E cannot be expressed as the product of an ODD and an EVEN. Thus E has to be a POWER of 2.

Constraint