ISI INTERVIEW PREP

[Mr. Nobody]

CONTENTS DELETED

The author has deleted this message.

[Amit Goyal]

Ok Ram. Answer this question:
True or False.
When the highest of n numbers is less than or equal to x then the second highest of those n numbers is also less than or equal to x.

[Mr. Nobody]

CONTENTS DELETED

The author has deleted this message.

[n.saish]

Consider a square of side length 4 units. Place 17 points randomly inside this square.
Show that no matter where you place these 17 points, you can always find at least two points whose distance is less than or equal to sqrt(2) units.

Well am getting only 13 points can be placed at a distance less than or equal to root 2 units....

[neha]

okay,, so your solution basically implies that there may be a case when all xi are less than x (which i completely missed out) and plus there are n cases when second highest is less than x.. Thanks a ton sir

[anurag]

@n.saish -  wt ws ur approach to dis? did u actly find all dese coordinates?

[Saish]

No, I did something like induction.
Basically how I thought is that we have to find how far away we can place n points from each other within the space of the square and then see the minimum distance amongst them...
First take 2 points and put them on the diagonal of the square... then put 3rd and 4th on the perpendicular bisector (PB) farthest away from the first two points. Now the four points would lie on the edges of the square...
The 5th would lie on the intersection of the PB's of the line connecting points 1,3 and 3,2. This would be the centre of the square.
similarly keep drawing PB's 6,7,8,9 points would lie on the centre of the sides of the square. Again draw PB's from the shortest distance you will see where 10, 11, 12, 13 would be placed.... If you calculate the minimum distance at this point it would be root 2.... I don't know if this way of thinking is correct...
I must me missing something cause as you can see placing another four points gives 17....
I thought of coordinates, but I thought the method would be too tedious

[anurag]

@n.saish - see ur answer depicts a very specific case. n u r able to find 13 sch pts dn automaticly it proves atleast 2 pts ka criteria..bt i dnt think dis is d right approach..
amit sir,pls help

[deepak]

This is how I thought about the problem.
Number of points that can be placed such that minimum distance of any 2 points is 2^.5 = (Area of the binding square)/(Area of a circle of diameter (2)^.5)
The binding square, I take to have side = 4(which is the given square) + 2 * (2^.5)/2 . The second term I get because, assuming a circle to be centered at one of the vertices, the binding square will have to envelope this. Since I need to extend on both directions by the radius, I get the above term.
If I compute the area of the square as (4+2^.5) ^2 and the area of each circle as pi *(1/2^.5)^2, I get n = 13.2.
Since you can place maximum 13 points such that each pair is atleast (2)^.5 apart, there is no way we can place 17 points such that they have a pairwise distance greater than root2.
Does this look sensible at all?

[deepak]

Apologies, in the above, I must mention one can place 13 points such that pairwise distances is > root(2). So Saish's inductive reasoning does look right.

[Rain Man]

Hi Deepak..

Can you elaborate on the concept you have just used . what do you mean when you say a binding square and how do you approach this problem

thx

[n.saish]

@deepak: Yes your method does look right... But with ref. to your statement "I must mention one can place 13 points such that pairwise distances is > root(2)", some of the 13 points can be placed at a distance > than root 2, but the minimum of the distances b/w 2 points would be root 2. What I mean is the points on the sides can be placed at a distance of 2 from each other, but some of the points inside cannot be placed at a distance > than root2. Just try to actually draw circles around the points, the way you have mentioned to see why this happens...
Therefore it would be misleading to think that because the answer is 13.2, all 13 points can be placed at a distance > than root 2.

[deepak]

@Saish Yes what you say is correct.

[deepak]

@Rain Man You can imagine the problem as placing n circles inside a square with a side of 4 such that their centres are atleast root(2) distance apart. The 'outermost' circles will be the ones having their centres coinciding with the vertices of the square. Since the centres of the circles are root(2) apart, the radius of each circle I take as 1/(root(2). So, to make sure my 'binding' square contains all circles, including the outer circles, I must extend the given square upwards, downwards, left and right by the length of the radius. ie, effectively, I'm increasing the side by root(2). And then I compute the ratio of areas to get the number of such circles.

[Preet]

Hi,

First of all i want thank Vasudha, Deepak,Ram, Anurag and others for being so proactive on this thread. You guys deserve the best in your life as you all are sharing knowledge just like Amit sir does :-)

Now, i have a doubt in the solution vasudha presented in the SWAP-RETAIN problem. Let me take this case where Player A gets the no-5 and the player B gets no-6.
Would player A not think tht his chances of improving his payoffs is 95/99 since there are 95 numbers greater than his own no? Similarly, player B has a probability of 94/99 to improve his payoffs.
Would both of them rather not be tempted to swap?

Vasudha wrote

Umm i didn't attempt this one bcoz i was not sure. But what i thot was this: say i'm 1 of the players. the expected value of the other player's number is 50. so i wud swap if my no. is less than 50. but then i know that the other guy wud also swap only when he's got less than 50. if he has less than 50 the expected value of his no is 25. so now i shud swap if i get less than 25. but then he wud be doing the same :) so i shud swap if i get a no less than 12.5..this will continue and i wud never swap :|

[deepak]

Ok let me try restating the problem so that it conforms to an already known paradox with a resolution, called the 2 envelope problem.

The 2 envelope problem is as follows : 2 envelopes contain a certain amount of money each, one higher than the other. A person picks up an envelope at random and sees how much money it has. He can either choose to take this and walk away, or leave this envelope, take the other one (without inspecting it's content) and begone with it.

Now let me try to reduce our current problem to the 2 envelope problem :
Since 2 people each draw a number, one of them must have the higher number. Also, if I am person 1, the number I choose can be taken to represent the amount of money in the open envelope. The number my opponent chose will be the amount of money in the other closed envelope. One of these must be higher than the other and thus it reduces to the 2 envelope problem.

Now to see why they won't swap, do jog on to wikipedia and read this article :) -
Two Envelope problem
Definitely worth a read!

[deepak]

I think I missed a key difference between the 2 problems. In the envelope problem there is no bounds on how high the amount can be but in ours, there is a limit of 100. This deserves more thought!

[Preet]

@Anurag/all- Will we or not divide by 3! and 2!?

I had read tht if we have to selected all of then objects of which there are r of one type and s  of another type then the total number of ways this can be done is

(n!)/(r!)(s!)

anurag wrote

In a pack of cards there are 52 cards: cards of 13 denominations belonging to each of 4 suits (clubs, diamonds, hearts and spades). 5 cards
are drawn from a pack of 52 cards. What is the probability of getting
3 cards of one denomination and 2 cards of another denomination?

ans. wil it be ( 4C3 * 4C2 / 52C5) * 13 * 12
 * multiplication , C combination

[deepak]

That holds if we are talking about 3 identical objects, like 3 red balls whcih can't be distinguished. Here, each card is unique, only, they are grouped. So 4C2 actually denotes, of the 4 cards of the same denomination, for eg. the Ace of clubs spades diamonds and hearts, we want to select 2 aces which are unique in their individual respect.

[anurag]

no we will not cz wt u r talkng abt is permutations of chosing r dn dividing by respectv r! ,bt in my answr hv already used combinations..