Serving the Quantitative Finance Community

 
User avatar
vema
Topic Author
Posts: 0
Joined: December 25th, 2006, 9:54 pm

Interview Question

June 1st, 2007, 2:37 pm

A set of six people are chosen at random and the claim is that we can select threepeople who know everyone else in the group or they do not know anyone in the group. True or False ?
Last edited by vema on May 31st, 2007, 10:00 pm, edited 1 time in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Interview Question

June 1st, 2007, 3:22 pm

Are you sure you stated this correctly? There's a brain teaser that asks "In any collection of six people either do three of them mutually know each other or do three of them mutually not know each other?" The answer, which is based on Ramsey theory, is yes. I assume that when you say "know everyone else in the group", that you mean the subgroup of three not the entire group of six.
 
User avatar
Advaita
Posts: 0
Joined: April 20th, 2005, 1:54 pm

Interview Question

June 1st, 2007, 4:02 pm

Given 6 points, but excluding any triangles --I divide the various ways of connecting these points by identifying the "largest polygon" of connections1. Line 2. 4-sided3. 5-sided4. 6-sidedLine: at most 2 are connected. We can easily select 3.5-sided: Visualise a "planar pentagon" and a floating sixth point in space. Note that there cannot be any diagonals within the pentagon (otherwise they would form a triangle). There will be only 2 lines from alternate points on the pentagon to the floating sixth point.Choose the floating point and two on the pentagon.6-sided: The most general 6-sided figure is a hexagon with 3 diagonals. We select alternate points.4-sided: Visualise a planar square with 2 floating points in space. There are two ways to connect the floating points. Chose 2 alternate points on the square and connect to one point. Then chose these or the other set of diagonal points to connect to the other floating point.Chose floating points accordingly.No Other possibilities: There cannot be isolated polygons as we have only 6 points (3 per triangle, ggives two triangles at most.)
Last edited by Advaita on May 31st, 2007, 10:00 pm, edited 1 time in total.
 
User avatar
MCarreira
Posts: 64
Joined: January 1st, 1970, 12:00 am

Interview Question

June 1st, 2007, 4:54 pm

As Traden4Alpha pointed out:Theorem_on_friends_and_strangers
 
User avatar
SW3Quant
Posts: 0
Joined: October 6th, 2006, 9:49 pm

Interview Question

June 2nd, 2007, 9:13 pm

I was asked a (simple) question the other day when practising for a junior quant job interview , and im not sure that i gave the correct answer: I pose it to the forum:"you are dealt 13 cards randomly from a pack of 52. What is the prob that your hand contains exactly two aces?"My answer was:P(X=r) = C(n,r) * (p^r) * ((1-p)^(n-r)) however as the number of cards is small, the prob will change as they are dealt....Solutions??
 
User avatar
MCarreira
Posts: 64
Joined: January 1st, 1970, 12:00 am

Interview Question

June 2nd, 2007, 10:30 pm

While we wait for the probabilists, 500000 simulations yield:0 aces: 152005/5000001 ace : 219583/5000002 aces: 106865/5000003 aces: 20248/5000004 aces: 1299/500000
 
User avatar
koffieboer
Posts: 0
Joined: May 20th, 2007, 11:44 am

Interview Question

June 3rd, 2007, 7:39 am

(2-from-4) (11-from-48) / (13-from-52)(2! * 2!) / 4!(11! * 37!) / 48!(13! * 39!) / 52!===> 0,213493397
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Interview Question

June 3rd, 2007, 10:37 am

QuoteOriginally posted by: MCarreiraAs Traden4Alpha pointed out:Theorem_on_friends_and_strangersRamsey Theory is interesting to quants because it defines the unavoidable emergence of order in sufficiently large collections of things. For example, the friends and strangers scenario can actually be recast into a statement about the structure of correlation matrix. Thus, a 6-instrument correlation matrix MUST contain 3 instruments that are all mutually positively correlated or all mutually negatively correlated.Ramsey Theory is one tool for thinking about patterns that are unavoidable and thus helps one avoid being fooled by randomness.
 
User avatar
MCarreira
Posts: 64
Joined: January 1st, 1970, 12:00 am

Interview Question

June 3rd, 2007, 7:25 pm

QuoteOriginally posted by: Traden4AlphaRamsey Theory is one tool for thinking about patterns that are unavoidable and thus helps one avoid being fooled by randomness.Which other tools do you suggest ?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Interview Question

June 4th, 2007, 1:38 am

QuoteOriginally posted by: MCarreiraQuoteOriginally posted by: Traden4AlphaRamsey Theory is one tool for thinking about patterns that are unavoidable and thus helps one avoid being fooled by randomness.Which other tools do you suggest ?First, I was thinking mainly of all the tools in statistics, probability, and combinatorics that let one model the statistical inevitability of "pattern" in random sequences or the inevitability of barrier crossings (e.g., gamblers ruin). Second, I suppose logic and the scientific method would be the tool for thinking about biased sampling problems (e.g., survivor bias) or other problems associated with misinterpreting market data. Third, are the cognitive science studies that empirically show the predilection of the human brain to find non-existent patterns.What's interesting about Ramsey Theory is that it contains no assumptions about the system having probabilistic vs. deterministic behavior. Instead, it concerns statements that hold true for all states of the system whether realized or not. Ramsey theory can't be fooled by randomness because it is independent of randomness.And now that you ask the question, I'm sure there are other tools that speak to the certainties embedded in seemingly randomness. I'd imagine that percolation theory and graph theory could be interesting. Perhaps the most interesting tools are those from nonlinear systems dynamics because they invert the fallacy. The second definition of "fooled by randomness" would be one in which we declare the system to be random when it is not. Chaotic systems appear random and unpredictable, when they are, in fact, deterministic and controllable.
 
User avatar
pk14
Posts: 0
Joined: February 15th, 2006, 12:43 am

Interview Question

June 4th, 2007, 5:21 am

Suppose it is false. Then,a. There are no 3 persons who dont know each other implies:For a fixed person A, the persons A doesnt know (call these persons group 1) know each other.b. There are no 3 persons who know each other implies:For a fixed person A, the persons A knows (call these persons group 2) don't know each other.Except for A, there are 5 persons, hence one of group 1 and group 2 has more than three persons. This gives a contradiction.