Rom/Column Inversion

You are given a matrix m*n (need not be square) of positive/negative integers. The only operations permitted are you invert the signs of an entire row or an entire column. And that is counted as one step. The goal is the to reach the maximum sum possible (of all elements) of the matrix with such a series of operations. 

Q. Does the process converge. If yes, then what is the complexity ?

Clue: When would you do such an operation ? And when you do that what happens to the total sum? What is the max sum which can be reached. 

Bit length

How many bits are required to represent a given number N in binary notation ? Can you come up with a formula for the same. For example F(N) for N = 7 is 3, since 111 is the binary representation for 7. F(N) for N=8 is 4.



Spoiler: F(N) = lg (N) + 1

How does the formula change when representing N in decimal notation.

Locker

Imagine you are at a school that still has student lockers. There are 1000 lockers, all shut and unlocked, and 1000 students.

Here's the problem:

1. Suppose the first student goes along the row and opens every locker.
2. The second student then goes along and shuts every other locker beginning with number 2.
3. The third student changes the state of every third locker beginning with number 3. (If the locker is open the student shuts it, and if the locker is closed the student opens it.)
4. The fourth student changes the state of every fourth locker beginning with number 4. Imagine that this continues until the thousand students have followed the pattern with the thousand lockers. At the end, which lockers will be open and which will be closed? Why?

Try the problem for n=10,20 and observe the results.

Hint / Spoiler : http://www.math.msu.edu/~nathsinc/java/Lockers/

A related problem to prove the solution to the one above

How many perfect square factors does the number 46,656 have?

Horses on Induction

Theorem. All horses are the same color.

Proof. Induct on the number of horses. Base case: 1 horse. Clearly with just 1 horse, all horses have the same color.

Now, for the inductive step: let's show that if it is true for any group of N horses, that all have the same color, then it is true for any group of N+1 horses.

Well, given any set of N+1 horses, if you exclude the last horse, you get a set of N horses. By the inductive step these N horses all have the same color. But by excluding the first horse in the pack of N+1 horses, you can conclude that the last N horses also have the same color. Therefore all N+1 horses have the same color. QED.

Q. Where is the flaw in the induction argument ?

Clue: Double - check the induction argument at a specific case, P(2) => P(3). Strong induction ?

More questions:

Is there anything else besides the above mentioned problem in the induction argument ?

Ant Problem

The noted gourmet Pangolini Aardvark is preparing a late night snack of "Ant au Chocolat" and "Ant au Fromage". This requires the use of a five foot pole. One end of the pole is over a bucket of melted chocolate and the other is over a bucket of melted cheese.

Pangolini sprinkles some ants onto the pole. They immediately start scampering along the pole in random directions. If two ants run into each other then they both instantaneously reverse their directions and are now moving away from each other. An ant can change direction many times. Eventually, all of the ants will fall off one or other end of the pole. If each ant travels at a speed of one inch per second, what is the maximum time until all ants have fallen off?

Suppose now that n ants are placed on a circle of five foot circumference and randomly choose their direction of travel and again reverse direction when they bump into each other. One of the ants is named Alice. What is the probability that Alice is back where she started, one minute after the ants start their scampering.

Back to the pole. Alice starts in the middle of the pole. There are n other ants placed randomly on the pole and they start scampering in random directions. Alice has a cold. When an ant with a cold bumps into another ant, the uninfected ant catches a cold too. What is the expected number of ants who catch cold before they all fall off the pole?

Clue:

This one is vague but very much relevant - What happens in an elastic collision of identical balls ?

level order tree traversal

How would you print out the data in a binary tree, level by level, starting at the top?

Clue:

How about using a Queue. Relate to Dijkstra's SP algorithm.

typrewriter Gib

On April 1st a typist found the hammers of the typewriter resoldered in an arbitrary order, so typing a text resulted in gibberish. The typist decided to type a document in its entirety using this typewriter. Afterwards, if the result does not represent the original text, he will type the result, and so on. Prove that the clear text will emerge sooner or later. How many iterations are enough to guarantee that the clear text will appear, if the typewriter has, say, 46 keys? N keys?

Clue:

Why does it say April 1 ? Is the question poser trying to trick you in deep stuff ? May be. But you can take it to a suitable point and then leave to the crazy math guys.

To take it to the suitable pt:

Decompose a number into such constituents such that the LCM of the constituents is maximized। Think prime! Pray Riemann !

Find the previous alphabet.

khanji has a LOT of characters in their alphabet and are using a way of compressing it so that the most common characters are 1 byte and the less common are 2 bytes. If it's a '1 byte' character, it starts with a 0, If it's a 2 byte character, it starts with a 1. If you're at a particular character (at the beginning), how do you find where the previous character begins?

Now this is an interesting question.
Let the currect char be c (irrelevant), and the first bit of every previous byte be denoted by 1s, 2s....etc.

Some hints:
1. If 1s = 1, then previous char is 2 byte long.
2. If 1s = 2s = 0 then ??
3. If 1s = 0 then all (2...n)s = 1 then the problem is undecidable until you hit
a 0, in which case the answer is ??

DP - max subset of dominating pts.

A DP one.

Q. Consider that you have n 2D pts. Find the largest set of pts such that when sorted (by either axis) produce the same sequence.
Okay, the exact wordings of the original problem -
A circus is designing an act consisting of a tower of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower?

My thoughts -
Sort the pts by say x axis co-ordinates. Then the problem reduces to finding the longest increasing subsequence ( or longest decreasing subsequence Note: we hae to consider both ) in y axis co-ordinates. this is a std DP problem.

More questions :
1. Will it produce the same answer when first sorted in y axis co-ordinates. Or we have to do the both and then take the one of max-length ?

2. How would you generalize the problem to pts coming from dimension d > 2. Need to think over that.

An aside :
See if you could relate some parts of the above problem to the following problem.
Given any sequence of mn+1 real numbers, some subsequence of (m + 1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.

Rational Pirates (really ??)

k, somebody sent me this question and a quick googling gave me this wikipedia link to the question itself. The question

There are five rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them.

The Pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E.

The Pirate world's rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates should then vote on whether to accept this distribution; the proposer is able to vote, and has the casting vode in the event of a tie. If the proposed allocation is approved by vote, it happens. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again.

Pirates base their decisions on three factors. First of all, each pirate wants to survive. Secondly, each pirate wants to maximize the amount of gold coins he receives. Thirdly, each pirate would prefer to throw another overboard, if all other results would otherwise be equal.

Wiki link - http://en.wikipedia.org/wiki/Pirate_game

Assuming the reader has read just the question, let me proceed further by strengthening it. What strategy should A employ that he doesn't get thrown overboard ?
Clue: Why not try this with a smaller number of people and then increase to see if it proves to be any helpful.
If n = 2, (say D and E ) are there. Then D obviously splits it as 100:0. So E will always attempt to never reach this situation where only 2 people are left out.
Consider n = 3. C knows that E would not want to in a situation with n = 2, so he would vote for me with any bare min payoff. So he would splits it as 99:0:1.
Now consider n = 4. B clearly knows that D would not want n = 3 situation and by same reasoning would split it as 99:0:1:0 ( note : In this case the casting vote would rule as C and E will vote against the proposition ).

Do you see a pattern readers. Plz note the flipping payoffs. And this is how A would split 98:0:1:0:1.

Easily generalizable. Solved.

Better still, they should all be given swords to finish it off, say, in more pirately manner.