Monday puzzle: a really tough interview question

Many of my Monday puzzles have been technical interview brain teasers.

Sebastian emails me an interview question that is a really difficult math problem.

Hi Presh,

This is a question I once got asked in an internship interview. The interviewer told me it was a hard problem, that would take at least 20 minutes, but I still couldn’t solve it or come up with a decent formula under the stressful setting. Here it is:

You have a box with 30 shoe laces (or strings) in it. You can only see the ends of the strings sticking out, so you see 60 string ends total. Now you start tying them together until all ends are tied to another.

How many ways can you tie the shoe laces together?

What is the expected number of loops?

For instance there could be at least 1 big loop consisting of all the 30 strings but at most 30 individual loops when each end is tied to the end of the same string.

[Update 9-30]: I apologize for the confusion in wording. My solution below assumes left and right shoelaces are distinguishable. Arguably, left and right shoelaces should be treated as indistinguishable, and the question is about “how many structures” can be made. The comments below address both cases.

Can you figure it out?

I really enjoyed this question and I have spent over two hours working on it myself.

Definitely give this one a try before reading my hints and thoughts below.

Hint: work on lower cases

With math problems and interview brain teasers, there are often problem solving techniques that can help you get to the right answer.

My first thought was that working out the answer for 30 shoelaces would be hard. I would instead tackle smaller cases like considering 2 or 3 shoelaces and seeing if there is a pattern.

How many ways can you tie 2 shoelaces together?

I drew a figure like this and I counted the number of ways.

I noticed the leftmost shoelace end could connect to at most 3 spots: it could tie to the end of its own shoelace, or it could tie to one of the other two ends on the other shoelace.

After that, there would be just two ends remaining, making just 1 way to connect the loops.

This means there are exactly 3 x 1 = 3 ways to connect the ends when there are 2 shoelaces.

What about 3 shoelaces?

I tackled this case by drawing out the following diagram.

For the leftmost end, there are 5 different shoelace ends that it could connect to: either it could connect to the other end of its own shoelace, or it could connect to the four ends of the other shoelaces.

Once that end is tied, we have to consider how many ways the remaining 4 shoe lace ends could be tied. But in fact we have solved this problem already! This is exactly the number of ways 2 shoelaces could be tied together, which we found was 3 x 1 = 3.

Thus, the total number of ways for 3 shoelaces is 5 x 3 = 15.

Answer: How many ways can you tie the shoe laces together?

We can deduce a general pattern from these cases.

If there are n shoelaces, then there are 2n shoelace ends.

The first shoelace end can be connect to any of the other (2n – 1) ends.

Tying one end to another removes 2 ends. Thus, the next shoelace end can be connected to any of the remaining (2n – 3) shoelace ends, the one after that to the remaining (2n – 5) ends, and so on.

The general formula for n shoelaces is they can be tied together in:

Ways to tie n shoelaces = 1 x 3 x 5 … x (2n – 1)

In other words, we have a product of the odd numbers up to (2n – 1)

For 30 shoelaces, this is going to be a gigantic number. I will let WolframAlpha compute this one:

Question: What is the number of expected loops?

I have worked on this part of the question for a couple hours, and admittedly I have not come up with a solution.

I have worked out some smaller cases and formulas, however, and I am hoping someone can figure it out as you guys are so smart at solving puzzles.

In general, I would guess the expected number would be something like 4 or maybe 5.

Why so low?

The reason is there are a lot more ways to tie all the shoelaces into one loop.

For instance, consider 2 shoelaces. There is just 1 way to make the ends form two loops: you have to tie each to its own shoelace. But there are 2 ways you can form one big loop (if the shoelace ends are labeled Aa and Bb, then you can form the loops ABba or AbBa).

Above we showed there are 3 equally likely ways the 2 shoelaces can be tied. Thus, we can calculated the expected number of loops by:

loop size * number of ways / (total number of ways) = (2*1 + 1*2) / 3 = 4/3 = 1.3333

I have similarly worked out the case of 3 shoelaces. I will omit the details, but I manually counted the number of ways to make different loop sizes. There are 8 ways to end up with 1 big loop, 6 ways to end up with 2 loops, and just 1 way to end up with 3 loops. Thus, the expected number of loops is:

loop size * number of ways / (total number of ways) = (3*1 + 2*6 + 1*8) / 15 = 23/15 = 1.5333

What about 30 shoelaces? So far I have not been able to generalize this formula or figure out a nice way to count it. I am guessing there is some kind of recursion formula.

If you figure it out, please share in the comments or at least give us a hint–we’ll be extremely grateful.



Share this post:

| More

Previous post:

Next post:



  • http://mathsetc1618.blogspot.com Gareth

    Hi there

    Maybe the question was a little ambiguous, but surely you should be counting unique ways of joining the shoe laces?

    so if we have 2 shoelaces, with ends A,B for shoelace 1 and C,D for shoelace 2, joining A and C is the same as joining A and D – both ways you’re left with a single loop. In a way, the loop ADCB is not the same as ACDB….but I would have assumed that it is and gone from there, stating there are only 2 ways of joining two shoelaces.

    I think this means that there are 5 ways of joining 3 shoelaces together, but I haven’t checked it properly yet.

  • Mark Engelberg

    Here’s what I’ve come up with so far.

    Let’s start by focusing on how many ways there are to make 1 loop out of n shoelaces. Let’s call this function L(n). This has a pretty easy pattern to it:

    L(1) = 1
    L(2) = 2
    L(3) = 2*4
    L(4) = 2*4*6
    L(5) = 2*4*6*8
    L(6) = 2*4*6*8*10

    You can see this by thinking about how the first lace end has 2n-2 choices to avoid making a loop, the second lace end has 2n-4 choices and so on.

    Notice that L(n) * Ways to tie n shoelaces = (2n-1)!

    Anyway, let’s say you want to figure out the number of ways to make 2 loops out of 4 numbers. First, we write down all the ways to sum to 4 with 2 summands.
    1+3
    2+2
    3+1
    [Think of this as ways to break it up into groups of shoelaces that need to be tied together as one loop]
    So then, we transform the above information into an equation as follows:
    L(1)*L(3) + L(2)*L(2) + L(3)*L(1) = 20

    Similarly, number of ways to make 3 loops out of 4 shoelaces is:
    L(1)*L(1)*L(2) + L(1)*L(2)*L(1) + L(2)*L(1)*L(1)=6

    Number of ways to make 4 loops out of 4 shoelaces is:
    L(1)*L(1)*L(1)*L(1) = 1 (just as we expect)

    In summary:
    L is a very straightforward function to calculate.
    Once you have L, assuming you have a program to generate all the possible ways to sum to a given number with a fixed number of summands (a fairly straightforward, recursive program to write), it is an easy task to write a program to compute the expectation.

    This formulation is intimately connected to the notion of a “partition” of a number (ways to create sums that add up to a given number). Partitions are very resistant to coming up with direct formulas, so I’d be inclined to think there isn’t a much more direct way to compute the expectation. If there is a more elegant, closed formula, I’d love to see it.

  • Mark Engelberg

    Hmmm, just found a flaw in my analysis.
    The partitions:
    1+1+2
    1+2+1
    2+1+1
    don’t tell the whole story, because it’s possible to group, say, lace 1 and 4 together in one loop as the group of 2, which isn’t really reflected here. I’ll have to think about how this modifies the formula, and post again.

  • Mark Engelberg

    OK, so we have to be more precise in our counting of partitions. We need to really enumerate all the ways to partition a set of n items into various configurations of subsets, but the idea I proposed basically works. Once you have counted such configurations, we use the L function to count how many ways to make a single loop out of each subset.

    Let’s recompute the 4 shoelace version more carefully.

    4 shoelaces, 1 loop = L(4) = 48

    4 shoelaces, 2 loops:
    There are 4 partitions of a set of 4 items of the form 3 + 1 and 3 partitions of the form 2 + 2.
    So, the answer is 4*L(3)*L(1) + 3*L(2)*L(2) = 44

    4 shoelaces, 3 loops:
    There are 6 partitions of the form 2+1+1, so the answer is 6*L(2)*L(1)*L(1) = 12

    4 shoelaces, 4 loops:
    There is 1 partition of the form 1+1+1+1, so the answer is 1*L(1)*L(1)*L(1)*L(1)=1.

    Note that 48+44+12+1 = 105, which is the total number of configurations for 4 shoelaces (7*5*3*1). So at least this passes a basic sanity check (I should have done that check on my previous explanation before posting!)

    As before, we have an “algorithm” for computing the result, but still not a direct formula.

    It seems that this is very closely related to Bell numbers and Stirling numbers of the second kind.
    But as far as I know, none of those formulas have anything to say about the number of ways to make rather specific configurations of partitions.

  • Mark Engelberg

    OK, did a little more research into Bell numbers, and it seems that “Bell’s complete polynomial” allows you to do computations that require the exact counts for a specific partition.

    http://en.wikipedia.org/wiki/Bell_polynomials#Complete_Bell_polynomials

    So if my reading of Bell’s complete polynomial is correct, then my above examples can be rewritten as:
    4 shoelaces, 1 loop:
    B_4,1(L(1),L(2),L(3),L(4))
    4 shoelaces, 2 loops:
    B_4,2(L(1),L(2),L(3),L(4))
    4 shoelaces, 3 loops:
    B_4,3(L(1),L(2),L(3),L(4))
    4 shoelaces, 4 loops:
    B_4,4(L(1),L(2),L(3),L(4))

    This has a nice pattern, so we can write the numerator for the expectation for n shoelaces as:

    summation where i runs from 1 to n of
    i*B_n,i(L(1),L(2),…,L(n))

    [I'm still using L to mean the function I defined in my first comment]

    The denominator, of course, is the total number of ways of tying the shoelaces, which you’ve already addressed.

    It appears that Mathematica has this complete Bell polynomial function as BellY, so it should be relatively quick to test out the above formula and make sure it works.

  • Mark Engelberg

    I went ahead and entered it into Sage, to do the calculation.

    http://www.sagenb.org/home/pub/3230/

    Sage’s built-in Bell polynomial function just generates a symbolic expression, so I rewrote it to take a list of numbers, so I could pass it the list of Ls.

    Again, to review:
    W(n) is the number of ways to tie n shoelaces
    L(n) is the number of ways to make 1 loop out of n shoelaces.
    The basic strategy to compute expectation is to partition the n laces into all the possible subsets, and multiply the product of the Ls.
    So, for example, one possible partition for 5 laces is:
    {{Shoelace1, Shoelace3, Shoelace4}, {Shoelace2, Shoelace5}}
    So we need to multiply the ways to make one loop out of Shoelace1,Shoelace3,Shoelace4 (i.e., L(3)) by the ways to make a loop out of Shoelace2 and Shoelace5 (i.e., L(2)). So this particular partition contributes a L(3)*L(2) count to the number of ways of we can get two total loops (which will eventually be multiplied by 2 to get the expectation).
    Methodically doing this computation for all possible partitions is exactly what Bell’s polynomial expresses.

    By my computation, the answer for 30 shoelaces is approximately 2.682.

  • john

    I agree that this is a tough problem. I read the problem as Presh did, not the way Gareth did.

    Gareth’s method for counting ways of tying laces is useless for solving the second question as can be seen with 2 laces. No matter which end you pick first, there is only one of 3 remaining that belongs to the same lace, and picking that one is the only way to end up with 2 loops. So the probability of 2 loops is 1/3 and that of one loop is 2/3. Gareth’s “unique ways” are not equally probable.

    I also see no reason to consider the ends of a single lace to be interchangeable but not the laces. If you consider laces distinct but not ends, 3 laces indeed gives 5 ways to tie, and 4 laces gives 15. With neither ends nor laces distinct, 3 laces gives 3 ways, and 4 laces gives 5 ways.

    But getting back to the question that gives the denominator for the second question, Presh’s answer for n laces is right. His answer can be written more elegantly as (2n)!/(n!2^n) where “^” means “to the power of”. n! and 2^n each have n terms, and if you put each 2 with a term from n! you get all the even terms in (2n)!

    While I find that more elegant, it offers no insight (as far as I can tell) for solving the problem. However, there is another way of writing it that does offer some insight.

    It can also be written as (2n-2+1)(2n-4+1)(2n-6+1)… For the first tie, there are 2n-2 ways that do not close a loop and one way that does. Every time you pick an end to tie, there is only one end that is not already tied which is connected to it. That means that each time you tie 2 ends together, there is 1 way to complete a loop and 2(n-t) ways not to complete a loop (t is the number of times you have already tied 2 ends together).

    So, here is my solution, which is admitedly quite cumbersom (I haven’t come up with any simplification, but someone else might). The denominator can be written as the product of all the terms of the form Ai+1 where Ai=2(n-i) and i goes from 1 to n. Since for i=n Ai+1=0+1=1, the last term in the product can be removed leaving n-1 terms.

    Now comes the tedious part. If you keep the last term, there are n terms, all of which have a 1 in them (n “1″‘s). when you multiply it out, there will be 1 term with all the 1′s multiplied together giving 1 which is the number of ways to get n loops. So the first term in the numerator for the expectation will be 1xn.

    There will be n terms with n-1 “1″‘s, and adding them together is the sum of the Ai (=n(n-1))which is the number of ways of having n-1 loops. making the second term n(n-1)^2.

    The next term for n-2 loops is n-2 times the sum of all the terms with n-2 “1″‘s which is all the terms that are a product of 2 Ai’s (so the sum over i’s from 1 to n of the sum over j’s from i to n of AiAj – the sums can be to n-1 as An=0)

    The ith term will be for n-i+1 loops and will be n-i+1 times the sum of all the terms with n-i+1 “1″‘s (or the sum of all the products of i-1 Ai’s).

    The n-1st term is the number of ways of getting 1 loop. The only “1″ that can be kept is the one in the term An+1 as all others would be multiplied by An=0. So the number of ways to get 1 loop is (n-1)!2^(n-1).

    There are no ways of getting 0 loops, but that is really irrelevant as the value is also 0.

    You can verify that this works for n=1,2,3,4 or as high as you want to go.

    It looks like there might well be a simplification, however, it would still be quite cumbersom. If there is one that I can find, and if and when I get around to it (and if someone hasn’t beaten me to it), I’ll add another comment.

    Not sure I made this readable enough. Hope someone can make sense of it.

  • Robb Effinger

    I agree with Gareth on Question One – I also solved it counting the unique ways to tie shoelaces together. This led to 395 ways to tie together 30 laces, with the function {f(1)=1; f(2)=2; f(3)=3; f(n)=f(n-1)+(floor(n/2)-1)*2 }

    I solved question two a different way then Mark did, but I agree with his answer. Basically, there’s one way to tie one lace together, so f(n)=1. With two laces, you have 1/3 chance of tying it to itself, forming two loops, and 2/3 chance of tying it to the other lace, forming 1 loop (for a 4/3 Expected Value). Or, more generally, you have a 1/3 chance of tying it to itself, meaning that the problem is the same as the previous case, but with one more loop – (f(2) = (1/3) * (f(1) + 1) + …) and a 2/3rds chance of tying it to the other lace, and so you can treat the two laces as one lace, and then it’s the exact same problem as the previous case (f(2) = … + (2/3) * f(1) ). Or even more generally,

    f(n) = (f(n-1) + 1)/(n*2-1)
    + (f(n-1) * (n*2 -2))/(n*2 -1)

  • Lucas

    Warning : this post is long, and can seem quite technical (even if I try to be as detailled as possible).
    n denotes the number of lace.
    For the expected number of loops, it is indeed quite hard, as the law of the number of loops is really complicated.
    But as we only want the expectation, and not the law, a nice trick can simplify the computation. All we need to compute is the expectation of what I will call “the contribution of a lace”, which is 1/the length of the loop this lace belongs to.
    The interest of that is that the number of loops is the sum over all the laces of the contribution of the lace (for each loop of length 1 we will get l times 1/l, thus 1 by loop), and that the expectation of the sum is the sum of the expectation. And as all the laces are identical, the expected value of the contribution is the same for every lace, and thus the expected number of loops is n times the expected contribution of a given lace.

    To compute the expectation contribution, we need to know the probability that a given lace is in a loop of length l. Let’s design by e1 and e2 the extremity of this lace. Let’s try for small value :
    -the lace is in a loop of length 1, if e1 is tied to e2, i.e. with probability 1/(2n-1).
    -the lace is in a loop of length 2 if 1)e1 is not tied to e2 2) and if the other extremity of the lace tied to e1 is tied to e2, thus the probability is 2n/(2n-1)*1/(2n-3).
    And so on.
    Thus the (ugly formula) should be that the expectation of the contribution should be the sum of :
    1/l*(the product of (l-1) even terms decreasing from 2n)/ (the product of l odd terms decreasing from 2n-1).

    And I really don’t see any simplification…

  • Dave

    Here’s my solution to the second problem:

    With one lace, you will always have one loop. L1=1.

    With two laces, when you tie the first knot one of two things happen: 1/3 chance you tie the lace to itself and have added 1 loop and are back to the case of one lace; 2/3 chance you tie the lace to another lace and have added 0 loops and are back to the case of one lace. So L2 = (1/3)*(L1+1) + (2/3)*L1 = L1 + 1/3 = 1 + 1/3

    Similarly, with three laces, by tying the first knot: 1/5 chance to add 1 loop and have two laces left over; 4/5 chance to add 0 loops and have two laces left over. L3 = (1/5)*(L2+1) + (4/5)*L2 = L2 + 1/5 = 1 + 1/3 + 1/5

    For the general case: L(n)= 1 + 1/3 + 1/5 + … + 1/(2n-1). For L(30), Excel gives me about 2.682, the same as Mark above.

    ps Longtime lurker, love the blog Presh.

  • Mark Engelberg

    I’m starting to think we’re all attacking the wrong problem. It just seems rather implausible to me that this problem would be presented, as stated, in an interview. So perhaps some detail in the wording of the problem got lost in translation?

    I’ve been trying to reverse-engineer the problem, brainstorming about whether there might be a slight variation of the problem that would be more amenable to generating an elegant formula.

    I’m reminded of a problem from my kids’ math book that starts off with the following scenario:
    Drape three shoelaces across your palm and close your palm. You’ve got three ends sticking out of the left side of your fist, and three ends sticking out of the right side. It is no longer obvious which end connects to which. Another person takes one end from the left side and ties it randomly to an end from the right side, and so on. Then you open your fist and count how many loops you made.

    I have a feeling the problem was meant to be an extension of something like this to 30 shoelaces. This problem is much easier to solve. It is fairly straightforward to see that this problem would be analogous to finding the expected number of cycles in a randomly chosen permutation of 30 elements.

    When you compute that (and I’ll leave these calculations out so that readers have some fun figuring it out for themselves) things cancel nicely and you end up with something fairly elegant like:
    summation of i from 1 to 30 of i/(i-1)!
    [Not totally sure, I did it in my head, but I think that's right.]

    So what do you think? Is it possible the wording of the problem is incorrect and something like this is what was meant?

  • Mark Engelberg

    @Lucas: I tried cranking through a few examples of your formula, and am getting very different answers using your formula than what Presh and I came up with for 2 and 3 shoelaces. Maybe I’m not understanding your formula correctly. Could you please crank through a couple concrete examples to demonstrate?

  • john

    1st, a correction. What I called t isn’t the number of completed ties, but that number +1.

    Looks like Mark’s answer is the most practical if you know Bell’s polynomial.

    However, I prefer Lucas’s answer. There is however one small mistake. The probability of tying the first end without making a loop is (2n-2)/(2n-1) (2n/(2n-1) is greater than 1 and cannot be a probability).

    The approach is clever, and the corrected answer can easily be verified for low numbers (n=2 and n=3 give the same answers as what Presh got).

    Since the final expectation is n times the expectation of the contribution, the final expectation would be:
    n(1/(2n-1)+sum over l from 2 to n of 1/l*(the product of (l-1) even terms decreasing from 2n-2)/(the product of l odd terms decreasing from 2n-1)).

    I seperated off the l=1 case as “the product of 0 terms” seems confusing. It doesn’t seem obvious to me that the answer would be 1.

    For n=30, I estimate that Lucas’ method would take about 10^3 operations, while my aproach would take on the order of 10^10 operation. His method would also require a simpler program. So, this method is much more practical than mine, and, like mine, requires no essoteric knowledge.

  • john

    Mark’s easier problem may well be what was intended.

    Using Lucas’ aproach, the answer is fairly straight-forward. Again you multiply the expectation of the contribution by n, but now that expectation is the sum over l of 1/l(((n-1)!/(n-l)!)/(n!/(n-l)!)) which simplifies to the sum over l of 1/l(1/n). The 1/n can factor out and is multiplied by n, leaving simply the sum over l of 1/l.

    This gives 1, 1.5, 11/6 and 25/12 for the expectations with 1, 2, 3 and 4 laces respectively. These are fairly easily verified to be correct.

    PS @Mark: if you’ve looked at this again, I’m sure you’ve already noticed, but the sum of i/(i-1) isn’t possible as the first term blows up (is infinite). And if the “!” is a factorial rather than an exclamation point, you correctly get 1 for n=1, but you get 3 for n=2. That’s not possible as the maximum number of loops is 2. Maybe you were supposed to end up with (i-1)!/i! as that is the same as 1/i.

    If you have already revisited your answer, I apologize for being redundant.

  • Leipaella

    From Marks link (http://www.sagenb.org/home/pub/3230/) its sure looks like this problem has a limit at e.

  • Leipaella

    Or not. :D

  • http://thehologram.blogspot.com Sailesh Ganesh

    Let E_n be the expected number of loops for n strings. Then,

    E_n = 1/(2n-1)*(E_n-1 + 1) + (2n-2)/(2n-1)*E_n-1

    To see why, consider the following cases:

    Case 1: Pick the end of any string, say, end 1 of string 1. There are 2n-1 other ends that it can loop with. There is a 1/(2n-1) chance that it loops with end 2 of string 1, creating one loop on its own. There are n-1 strings left, and the expected number of loops from these is E_n-1, giving a total of E_n-1 + 1 loops.

    Case 2: There is a (2n-2)/(2n-1) chance that end 1 of string 1 loops with a different string, say, end 1 of string 2. Now, we can consider the combination of string 1 and string 2 as a single string, and we have n-1 strings after the first loop. The expected number of loops from these is again E_n-1.

    Took me about 20 min just for this question.

  • Scott

    @Sailesh:

    Your formula reduces to:

    E_n = 1/(2n-1) + E_n-1

    And, if we acknowledge that E_1 = 1, it reproduces Presh’s outputs for n=2 & n=3.

    E_30 = 2.682376847

  • Scott

    It also lookes like this recursive function can be represented by the series:

    E_n = sum (i=1 to n) [1/(2i-1)]

    Which, at least visually, seems to have some relationship or similarity to harmonic numbers and/or natural logs.

  • http://thehologram.blogspot.com Sailesh Ganesh

    @Scott:

    It is like a harmonic number, but with half the terms taken out. The sum does not converge, though the expected number of loops is never very high. Even for a billion strings, the expected number of loops is only slightly larger than 9.

  • Eyal

    When tying the shoelaces, you’re making a permutation. Imagine all the laces are numbered 1 to 30. Each knot is connecting one lace to another (or the same lace). You could list them like this:

    1 -> 4
    2 -> 3
    3 -> 1
    4 -> 2
    5 -> 5

    This is identical to the first notation here: http://en.wikipedia.org/wiki/Permutation#Notation

    The Stirling Numbers of the First Kind S1(k,j) are the number of ways to make j loops given k elements. So the answer to the second problem for 5 strings is:

    5*Abs(StirlingS1(5,5))+4*Abs(StirlingS1(5,4))+3*Abs(StirlingS1(5,3))+2*Abs(StirlingS1(5,2))+1*Abs(StirlingS1(5,1))+0*Abs(StirlingS1(5,0))

    divided by 5! .

    Putting the the former into Wolframalpha and then dividing by 120, the answer for 5 laces is:

    274/120 = 2.82…

    Wolfram Alpha can’t swallow all 30 terms in one pass so I had to chop it up. My final result was 3.9949… This was quite different from other answers. I’d like to try a small case, like 3 laces, count the results by hand, and see which technique is correct.

  • Mark Engelberg

    @Eyal:
    The flaw in your analysis is that you don’t have an equal chance of picking each permutation. For example, in the 3 lace version, shoelace 1 has twice the probability of connecting to lace 2 and 3 than it does of connecting to itself.

    See my “alternative formulation” for a version of the problem that does correspond to picking a permutation at random.

  • Chris Kuklewicz

    Let me take the laces/strings to be indistinguishable. A way of
    looking at the possibilities is counting the lengths of the loops. For 4 laces you could have five ways to have loops of total length 4:

    4
    3 + 1
    2 + 2
    2 + 1 + 1
    1 + 1 + 1 + 1

    I am just looking, like Mark, at partitions, but unordered. There are recurrence relations for computing this, but as wikipedia explains “In January 2011, it was announced that Ono and Jan Hendrik Bruinier, of the Technische Universität Darmstadt, had developed a finite, algebraic formula determining the value of p(n) for any positive integer n.”

    The probabilities of number of loops is trickier, as you care about the probability of each of the five ways above but only consider the number of terms instead of the values. Combinatorics would get you there. But the recursive recurrence relation definition above looks like a better method.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    By the way, there is some great discussion of this article over at reddit.

    http://www.reddit.com/r/math/comments/kw7pm/a_really_tough_technical_interview_question_about/

    Here is an amazingly elegant answer to the number of expected loops:

    “What about this: You have 60 ends and you start tying laces, two at a time. Each time you tie a knot, you either make a loop or you don’t, and you take 2 ends out of the pool.
    For each iteration, you take one end (e1) and then tie it to another end (e2). That other end is either the other end of e1 or it isn’t, and you just extend the length of e1. The chance e2 is tied to the other end of e1 is 1/(n-1) where n is the number of ends in the current pool.

    The expected number of loops made after the first iteration is then 1/59. For the next iteration, it’s 1/57, and so on until you get to 1/1
    So the total number of expected loops is sum(1/59+1/57+…+1/1)=2.682.”

  • john

    That is an elegant solution Presh, but in my mind it is really just another description of the recursive answer given by Sailesh Ganesh (who seems to me to be the person who got the job/aced the interview – and I think congratulations are in order). The heart of this solution is simply that for n laces the first tie contributes 1/(2n-1) to the expectation, and n-1 laces remain.

    Your description expicitly (the recursive relation does so as well, but less expicitly) points out that each term is the contribution of a tie which is an interesting point to make. If Lucas had tried to find the contribution of each tie rather than of each lace, he would probably have aced the interview as well.

    But adding the contributions of each lace was still far better than the brute force “partition” method the rest of us were trying.

    I suspect that the sole purpose of the first question was to lead one to a “partition” approach. So those who are too suggestible will lose.

    The advantage of the recursive description, is that it naturally leads to adding up instead of down. So on your way to finding the answer for n, you will have found the answer for all i less than n.





Previous post:

Next post:

Other posts you may enjoy reading:

Random Posts

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress