Ramaiah entrance test question [Solution]

The problem was to show that  the sequence of numbers

$$49, 4489, 444889, \dots $$

where each number is formed by inserting 48 in the middle of the previous number:

$$49 \to 4\underline{48}9 \to 44\underline{48}89 \to \dots$$

has only perfect squares!

Solution

---

Any number is of the form $n$ 4s followed by $n-1$ 8s followed by 9.

This can be rewritten as the sum of

$4444\dots44$ (a $2n$ digit number) 

$44\dots4$  (an $n$ digit number)

1

This is basically

$$\frac{4(10^{2n}-1)}{9} + \frac{4(10^{n}-1)}{9}  + 1 $$

$$= \left(\frac{2\times10^n + 1}{3}\right)^2$$

Integer part of $(1 + \sqrt{2})^n$

Give an algorithm to compute the integer part of

$$(1+ \sqrt{2})^n $$

in number of operations which is polynomial in $\log n$.

Note: I had a mistake earlier by using time, instead of number of operations. Even though we use only polynomial in $\log n$ integer operations, the running time will be $\Omega(n)$, as we are dealing with $\theta(n)$ bit integers.

[Solution]

A question from Ramaiah entrance test

Ramaiah's classes were (are) popular coaching classes for IIT JEE exam preparation in Hyderabad. They themselves had an entrance exam!

These Ramaiah entrance tests contained some very nice problems.

This was a question I first saw on a Ramaiah entrance test when my brother appeared for it (1990). The question is actually much older than that, probably the 1800s.

Anyway, here goes:

Consider the sequence of numbers

$$49, 4489, 444889, \dots $$

Each number is formed by inserting 48 in the middle of the previous number.

$$49 \to 4\underline{48}9 \to 44\underline{48}89 \to \dots$$

Show that all these numbers are perfect squares!

[Solution]

Another textbook hand.

This hand is based on one that occurred in a pairs game at a recent Sectional in Everett, WA.

Assume you are playing teams, though.

You are South and reach 6H, and get a club lead.

IMPS None	North ♠ AQT432 ♥ 72 ♦ A2 ♣ KQ2
	South ♠ 5 ♥ AKJT986 ♦ 43 ♣ A43

How will you play?


Suggested line (added April 16 2015)

---

If trumps are 2-2, you will have an easy 12 tricks.

If you have a trump loser, then you need to do something about the diamond loser.

Spades are a potential source of that trick.

Since you might need entries to dummy, you win trick one in hand.

If spades are 4-2, you need 3 entries in the non-spade suits to setup and cash the extra spade tricks (the SA is an entry for a ruff).

If spades are 5-1, you need 4 non-spade entries. Not sure what to do about a 6-0 spade break.

So the suggested line is:

Win CA in hand. Play spade to A and ruff a spade in hand with one of J,T,9,8. Preserve the 6!

If spades are 4-2, you can now just play trumps from the top.

If spades are 5-1, and LHO hasn't ruffed, you now play the HJ from hand! The opponents cannot duck this (if trumps are 3-1) and now the H7 is the extra entry you need to dummy!

Generate a random heap [Solution]

The puzzle was here.

Solution

---

I will be brief.

For O(n) random number calls, the idea is to grow the heap top down.

n has to be the topmost element. Now n-1 could be any of its two children. Pick a spot for that, randomly.

Now there are 3 new spots available for n-2. Pick one of those three randomly.

This leads to 4 new spots for n-3 and so on.

At the end, you have a random heap.

For an O(1) random number calls algorithm, try proving that there are exactly n! (i.e. factorial of n) heaps, and provide a way to encode/decode a heap given a random number from 1 to n!.

Integration problem [Solution]

The puzzle was to compute

$$ \int \frac{1+x^2}{(1-x^2)\sqrt{1+x^4}} dx$$

Solution

---

As usual, a clever substitution needs to be sought.

In this case, you divide the numerator and denominator by $x^2$ and then make the substitution $t = x - \frac{1}{x}$.

This results in

$$ -\int \frac{dt}{t\sqrt{t^2+1}}$$

which is a standard integral.

Rabbit plays A diamond

[Like the previous Rabbit stories, this is based on the Menagerie characters. This was also posted on bridgewinners.]

---

Karapet was hoping he would cut the Rabbit, but as usual, the Rabbit with his darn luck got paired with the Hog.

"Again? Anyway, how bad can it be? At least it is Secretary Bird and not Papa. It can't be worse than yesterday when...".

Karapet's thoughts were interrupted by the Hog loudly ordering some jam sandwiches.

The Rabbit was the dealer and dealt himself ♠AK ♥KQT9876 ♦A32 ♣A.

He opened 1♥, Secretary Bird, who was on his left passed. Hog surprised everyone by passing, and Karapet doubled.

Just then the waiter arrived with the sandwiches and the Hog offered him some. Saying "No thanks", the Rabbit passed (the sandwich no bid, if I may).

The Bird bid 2♣ , Hog passed (again!), and Karapet bid 2♦.

The Rabbit now thought, "With my diamond honour over Karapet's, my hand has improved. I was going to invite, but I think I should bid game now". His nose quivering with excitement, the Rabbit bid 4♥ with shaking hands.

The Bird, Hog and Karapet passed. The Rabbit passed out of habit. "No double this time Rabbit", chuckled Hog.

The Bird led the ♦T.

The Hog placed the dummy down awkwardly, as he took the Rabbit's cards for a look see. "Wonderfully bid Rabbit. Now you just have to make it", said Hog, while scraping the last globs of jam on the plate with his finger.

These were the cards

Rubber None	Hog ♠ 5432 ♥ 32 ♦ 5432 ♣ 432
	Rabbit ♠ AK ♥ KQT9876 ♦ A76 ♣ A

W	N	E	S
			1H
P	P	X	P*
2C	P	2D	4H
P	P	P

Rabbit immediately called for a low ♦ and Karapet overtook the ♦T with the ♦K.

Now the Rabbit began to think. "What was it? Count your losers? Lose two diamonds and the ♥A. Maybe I should duck the diamond? Or was the rule to win it?".

Then inspiration struck him, "Aces are meant to take Kings!". The decision was easy. He needed to win it and then drive out the ♥A.

So he reached for the ♦A and plunked it on the table. To his dismay, he noticed a card lying beneath the ♦A. He was surprised to see that it was the ♥T.

"What? How? I sorted my cards. Wait there is something on back of ♦A. It is some ja...".

"You never could tell the difference between a heart and a diamond", interrupted the Hog.

"It is a played card. Since you won the trick, you need to lead that to the next trick. Those are our rules", said the Bird.

"What? No. It is not my fault. It is those damn sandwi...".

"In fact I would not be surprised if you didn't notice that you had a club in with your diamonds too", interrupted the Hog again.

Inspite of the Rabbit's protests, he was forced to play the ♥T to the next trick.

These were the four hands

Rubber None	Hog ♠ 5432 ♥ 32 ♦ 5432 ♣ 432
Bird ♠ T98 ♥ J54 ♦ T ♣ JT8765		Karapet ♠ QJ76 ♥ A ♦ KQJ98 ♣ KQ9
	Rabbit ♠ AK ♥ KQT9876 ♦ A76 ♣ A

W	N	E	S
			1H
P	P	X	P*
2C	P	2D	4H
P	P	P

The Bird quickly played the ♥J to get the cheap trick that he had directed himself to.

Poor Karapet had to overtake with his bare Ace. He could cash two more diamonds, but even Rabbit could take the rest.

"Just my luck, as usual. Rabbit had to have a heart in with the ♦, and you had to play the ♥J. If you play low, I can win and promote your Jack for the setting trick!"

"Jam sandwiches, anyone? I am ordering more", said the Hog, licking his fingers.

[You guessed it. It was the Hog who had stuck the cards together with jam, and the Rabbit had in fact sorted his cards correctly.]

Generate a random heap.

Very recently I posted a puzzle on generating a random binary tree.

This time, the puzzle is to generate a uniformly random binary heap.

Specifically, generate a heap implemented as a binary tree of $n$ nodes, where each node takes exactly one of the values in $\{1,2, \dots, n\}$, and satisfies the max-heap property: each node value is larger than the values of its children (number of children could be zero, one or two).

The tree does not have to be full/almost complete (so a linked list of $n$ nodes is a valid heap for our purposes).

The left and right children are distinct, so the heap with 3 at the top, and left child 1, right child 2, is different from the heap with 3 at the top, left child 2 and right child 1.

Assume you have a random number oracle which gives you a random number in the range $\{1,2, \dots, K\}$, with probability $\frac{1}{K}$, $K$ is input and could be as large as you want it to be.

A) Give an algorithm that makes $O(n)$ calls to the random number generator.

B) Give an algorithm that makes $O(1)$ calls.

[Solution]

Integration problem

Computing tricky integrals was something which folks preparing for IIT JEE used to do.

Here is one such.

$$ \int \frac{1+x^2}{(1-x^2)\sqrt{1+x^4}} dx$$

[Solution]

Generate a random binary tree [Solution]

The puzzle was to generate a random binary tree on n nodes, each structurally distinct tree being equally likely, given a uniform random number generator which can generate a number from 1,2,...,K with probability 1/K, given input of K.

The easier version was to use O(n) calls to the random number generator.

The harder version was to use O(1) calls to the random number generator.

Solution

---

A structurally unique tree can be encoded by its preorder traversal, which includes the null nodes, and that encoding is reversible.

Using a '1' for a node, and '0' for a null node, we get a string of n 1s and n+1 0s.

For example, just a single node tree encodes are 100. (1 for root, and 0, 0 for the left and right null children), while a tree with a root and its right child encodes as 10100.

An important property of this encoding: Every proper prefix of the encoding has at least as many 1s as 0s, and any string with n 1s and n+1 0s that has that prefix property, is the encoding of a tree.

Now if you look at the reverse of the encoding (e.g: 001 for a single node tree), it is nothing but a semi-balanced string which we encountered in an earlier blog post!

Now we can generate a tree as follows:

Generate a random string of n+1 0s and n 1s. Find the unique semi-balanced string which is a circular shift of that string.  Reverse it. Decode to get the tree which gives that preorder.

Thus the problem boils down to picking n numbers out of 2n+1 numbers (the positions of the 1s).

If we use reservoir sampling, this will take O(n) random number calls.

We can also encode the sets to a number from 1 to $\binom{2n+1}{n}$, pick a random number using _one_ random number call (remember it can take arbitrary integers as input), and decode. I will leave the decoding to you.

A perfect square problem [solution]

The puzzle was to find all positive integers $n$ (with proof) for which $$n^4 + n^3 + n^2 +n + 1$$ is a perfect square.

Solution

---

One liner!

For $n \gt 3$, we have that

$$ (2n^2+n)^2 \lt 4(n^4 + n^3 + n^2 +n + 1) \lt (2n^2 + n + 1)^2$$

So verify for $n=1,2,3$ and we get the answer to be $n=3$.

What is the danger?

This puzzle is for the newer players (not completely new, though).

Playing Rubber Bridge, you are South and end up in 5S. West leads the club 2 and you see:

Rubber N/S	North ♠ QJT92 ♥ A2 ♦ QJ ♣ QJ43
	South ♠ K8754 ♥ K3 ♦ A3 ♣ AK65

You play low from dummy and East follows with the club 7.

What is the danger, and how will you deal with it? How will you play?

Solution (updated March 24th 2015)

---

Looks like West has led a singleton club.

The danger is when East has the singleton Ace of trumps.

In that case, if you play trumps immediately (after winning the first trick), East will win, give partner a ruff, and West will safely play back a heart. Leaving you to rely on the diamond finesse.


You cannot prevent the club ruff if it is there, but you can remove the safe heart exit from West, by playing two rounds of hearts before touching trumps. Now if West ruffs, he will be forced to return a diamond giving you the free finesse, or a heart for a ruff-n-sluff!

Generate a random binary tree

You want to generate a random binary tree on n nodes, such that each structurally different tree has the same chance of being generated as any other.

Suppose you have access to a random number generator oracle which generates an integer in $\{1,2,\dots, K\}$ (with probability $\dfrac{1}{K}$), given $K$ as an input ($K$ could be as large as you want).

Can you give an algorithm which generates an n node binary tree using $O(n)$ calls to the random number generator?

Can you do it using $O(1)$ calls?

[Solution]

A perfect square problem

Find all positive integers $n$ (with proof), for which $$n^4 + n^3 + n^2 + n + 1$$ is a perfect square.

[Solution]