20 people in a circle

[Schunck]

Please help with an explained solution to the following:

20 people sits in a circle. They are told to look at another person. What is the probability that two random people look at each other?

 

[Deleted member 4993]

Please help with an explained solution to the following:

20 people sits in a circle. They are told to look at another person. What is the probability that two random people look at each other?

Please show us what you have tried and exactly where you are stuck.

Please follow the rules of posting in this forum, as enunciated at:

READ BEFORE POSTING​

Please share your work/thoughts about this problem.

 

[Schunck]

I was thinking something like:

There is 19^20 ways they can look at each other.
18^20 are 2 people who are not looking at each other. Giving 19^20-18^20 looks at each other from a total of 19^20=0,66.

 

[Dr.Peterson]

I was thinking something like:

There is 19^20 ways they can look at each other.
18^20 are 2 people who are not looking at each other. Giving 19^20-18^20 looks at each other from a total of 19^20=0,66.

Nice idea, but I'm not quite convinced of the 18^20. Can you explain that in detail?

I tried it on a smaller case (3 people) and it didn't seem to work, though that could be a special case; with 4 people, I didn't try listing all the possibilities, but it seems that introduces more ways for your idea, as I understand it, to fail.

Can you tell us a little about the problem? Is it your own idea (in which case it might not be solvable), or from a class, so that some method you've learned should work (in which case, what have you learned?), or from a contest, so that it may take a big trick?

 

[JeffM]

If person 1 looks right at person 2, what must person 2 do so that persons 1 and 2 are not looking at each other? So what must person 3 do? How does that propagate?

How about if person 1 looks left? What must person 20 do so that 1 and 20 are not looking at each other? How does that propagate?

So what is the probability that nobody is looking anyone else in the eye?

 

[Schunck]

Well another way to look at it could be:

Everyone looks at another and there is a 1/19 chance that the other looks back.
Therefore also 18/19 so that it does not happen.
In order for no one to look at each other, the probability must therefore be (18/19) ^ 20, or approx. 34%
Therefore also 66% percent for just two looking at each other?

 

[Dr.Peterson]

This is still not convincing. And in this field, it's very easy to be almost convincing, but wrong.

Here's the extra issue I see: You can have a set of people who form a loop (e.g. 1 -> 2 -> 3 -> 1) that doesn't include everyone, Then #4 can be looking at anyone, rather than having one he can't look at. (And whoever he chose reverts to having one he can't look at.)

What answer do you get for 3 people, or for 4? Try counting those directly, and see if your answer agrees.

 

[LCKurtz]

Interesting thread. I'm not sure everyone is interpreting the question the same way. Is it this:

If two people are picked at random, what is the probability they are looking at each other?

or

What is the probability that there are two people that are looking at each other?

I favor the first interpretation of the OP and I think the answer is 1/19. Could be wrong though.

 

[Cubist]

Is it this:

If two people are picked at random, what is the probability they are looking at each other?

or

What is the probability that there are two people that are looking at each other?

...and if the latter, then which of the following applies:

What is the probability that there are exactly two people (and no more) looking at each other?

or

What is the probability that at least two people (one, two, three, or more pairs) are looking at each other?

 

[Steven G]

...and if the latter, then which of the following applies:

What is the probability that there are exactly two people (and no more) looking at each other?

or

What is the probability that at least two people (one, two, three, or more pairs) are looking at each other?

My thoughts exactly--are exactly two people looking at one another?

 

[Dr.Peterson]

...and if the latter, then which of the following applies:

What is the probability that there are exactly two people (and no more) looking at each other?

or

What is the probability that at least two people (one, two, three, or more pairs) are looking at each other?

I took the OP in #3 to be taking it as "at least one pair", which is how I take it as well. "One randomly chosen pair" seems too easy.

But I'll allow anyone to convince me of an answer to either of these two interpretations ...

 

[Schunck]

I took the OP in #3 to be taking it as "at least one pair", which is how I take it as well. "One randomly chosen pair" seems too easy.

But I'll allow anyone to convince me of an answer to either of these two interpretations ...

I read it as at least one pair.

I tried with 3 people and drew all the possibilities (2 * 2 * 2 = 8), and then counted the favorable outcomes (2 * 2 + 2 * 1 + 2 * 0 = 6), and then calculated 6/8 = 75% as the expression can be reduced by dividing by 2, ie it becomes 2 + 1 + 0/2 * 2 = 3/4 = 75%, all major expressions can be reduced down. I also tried with 4 people.

Finally I came up with:
(19+18+17+16…..+0)/(19*19). Giving 190/361=52,63% ...................... added REQUIRED parentheses in the denominator.

??

 

[Dr.Peterson]

I tried with 3 people and drew all the possibilities (2 * 2 * 2 = 8), and then counted the favorable outcomes (2 * 2 + 2 * 1 + 2 * 0 = 6), and then calculated 6/8 = 75% as the expression can be reduced by dividing by 2, ie it becomes 2 + 1 + 0/2 * 2 = 3/4 = 75%, all major expressions can be reduced down. I also tried with 4 people.

Finally I came up with:
(19+18+17+16…..+0)/(19*19). Giving 190/361=52,63% ...................... added REQUIRED parentheses in the denominator.

Can you justify your formula for n=20, other than by analogy? What did you get when you took n=4? (My impression is that n=3 is a special case, and n=4 introduces new considerations as I suggested in #7.

I'm expecting someone here to try a simulation.

 

[Cubist]

I'm expecting someone here to try a simulation.

Dr.Peterson seems to know me Here are the first few results before computation time becomes excessive. I hope this helps to find an exact answer. If not, then I could write a Monte-Carlo simulation to obtain an approximate answer for the 20 people case.

Num  count/ways       simplified           as approx decimal
 2    1/1                 1                 1.0000
 3    6/8                 3/4               0.7500
 4    51/81               17/27             0.6296
 5    580/1024            145/256           0.5664
 6    8265/15625          1653/3125         0.5290
 7    141246/279936       7847/15552        0.5046
 8    2810437/5764801     401491/823543     0.4875
 9    63748728/134217728  7968591/16777216  0.4750

Spoiler: show code

from fractions import Fraction

numPeople=4 # Setting to 20 would take too long

ways=0
eye2eyeCount=0

p=[1]
for j in range(numPeople-1):
    p.append(0)

done=0
while done==0:
    e=0
    for j in range(numPeople):
        if j == p[ p[j] ]:
            e = 1
            break
    if e==1: eye2eyeCount += 1
    # print(p,e)
    
    ways += 1
    
    # increment p
    for j in range(20):
        p[j] += 1
        if p[j] == j: p[j] += 1
        if p[j] < numPeople:
            break
        else:
            if j==numPeople-1:
                done=1
                break
            p[j] = 0
            if j==0: p[j] = 1
    
print(eye2eyeCount,"/",ways)
print(Fraction(eye2eyeCount, ways))

 

[Schunck]

Dr.Peterson seems to know me Here are the first few results before computation time becomes excessive. I hope this helps to find an exact answer. If not, then I could write a Monte-Carlo simulation to obtain an approximate answer for the 20 people case.

Num  count/ways       simplified           as approx decimal
 2    1/1                 1                 1.0000
 3    6/8                 3/4               0.7500
 4    51/81               17/27             0.6296
 5    580/1024            145/256           0.5664
 6    8265/15625          1653/3125         0.5290
 7    141246/279936       7847/15552        0.5046
 8    2810437/5764801     401491/823543     0.4875
 9    63748728/134217728  7968591/16777216  0.4750

Spoiler: show code

from fractions import Fraction

numPeople=4 # Setting to 20 would take too long

ways=0
eye2eyeCount=0

p=[1]
for j in range(numPeople-1):
    p.append(0)

done=0
while done==0:
    e=0
    for j in range(numPeople):
        if j == p[ p[j] ]:
            e = 1
            break
    if e==1: eye2eyeCount += 1
    # print(p,e)
 
    ways += 1
 
    # increment p
    for j in range(20):
        p[j] += 1
        if p[j] == j: p[j] += 1
        if p[j] < numPeople:
            break
        else:
            if j==numPeople-1:
                done=1
                break
            p[j] = 0
            if j==0: p[j] = 1
 
print(eye2eyeCount,"/",ways)
print(Fraction(eye2eyeCount, ways))

Please do so

 

[LCKurtz]

I may be missing something here but here's my thinking. You have n people. Pick any one of them, "him". He will be looking at one of the others. Now, thinking about her, if she is not to look at him or herself, she has n-2 choices. So the probability she is not looking at him is [math]\frac{n-2}{n-1}[/math] since she has n-1 choices possible. The same is true for each of the n-1 others that might have been looking at him. Since there are n-1 others besides him, the probability that none of them are looking at him is [math]\left( \frac{n-2}{n-1}\right)^{(n-1)}[/math]. So the probability someone is returning his gaze is [math]1-\left( \frac{n-2}{n-1}\right)^{(n-1)}[/math].
I have posted some Maple output for this below. Since my numbers don't quite agree with @Cubist, I'm a little uncertain here...

 

[Cubist]

here's my thinking...

...that's a great idea/ way of thinking about it!

I haven't looked into the difference between our results in detail yet. But I'm not too sure about the step of raising to the power of (n-1) when there are n people. Hopefully I'll get more time soon! Below is a copy of the possible combinations for 4 people (from an adapted version of my code above), hopefully it will help us to spot any problems in the number of ways that a pair can be looking at each other

1000  1      3210  2      2001  1      1311  1      3002         2312 
2000  1      1310         3001         2311  1      1202         3312 
3000  1      2310         1201         3311  1      2202  1      1032  2
1200         3310  1      2201  1      1031  1      3202         2032  1
2200  1      1030  1      3201         2031         1302         3032  1
3200  1      2030         1301  1      3031         2302  1      1232  1
1300         3030  1      2301  2      1231         3302         2232  1
2300  1      1230         3301  1      2231         1012  1      3232  1
3300  1      2230         1011  1      3231         2012         1332  1
1010  1      3230  1      2011         1331  1      3012         2332  1
2010         1330         3011         2331  1      1212  1      3332  1
3010  1      2330         1211  1      3331  1      2212  1
1210  1      3330  1      2211  1      1002  1      3212  1
2210  1      1001  1      3211  1      2002  1      1312

The 4 digits represent { who is person #0 looking at, who is person #1 looking at, ..} and the single digit to the right (if there is one) says how many pairs are looking at each other. (If this is 2, then it only counts as 1 toward the sum)

NB: Your expression gives 1-( (4-2) / (4-1) )^(4-1) = 19/27
My code gives 51 / 81 = 17/27

 

[LCKurtz]

I have to admit that, after looking at this again in the light of day, I'm not sure I believe my own argument. I will look at it some more.

 

[Cubist]

Here's a formula, that matches up with my code's output, for a table of n people:-

[math] P(n)= \frac{s}{(n-1)^n}[/math]where
[math] s=\sum_{p=1}^{\left\lfloor{n/2}\right\rfloor} (-1)^{p-1} \times \frac{\left(2p\right)!}{p! \cdot 2^p}\times \binom{n}{2p}\times \left(n-1\right)^{\left(n-2p\right)}[/math]
P(20) = 16028016368907840953165425 / 37589973457545958193355601
≈ 0.42639073387508110361

--

The number of ways to have "p" pairs looking at each other (while the remaining peoples' gaze is unknown) is:-

[math]\frac{\left(2p\right)!}{p! \cdot 2^p}\times \binom{n}{2p}\times \left(n-1\right)^{\left(n-2p\right)}[/math]
Breaking it down:-

• [imath]\frac{\left(2p\right)!}{p! \cdot 2^p}[/imath] The number of ways that 2*p people can be paired. (To explain this consider p=4, this is equivalent to the permutations of "AABBCCDD" divided by the permutations of "ABCD")
• [imath]\binom{n}{2p}[/imath] Ways of choosing 2*p people (to pair) from n
• [imath]\left(n-1\right)^{\left(n-2p\right)}[/imath] Ways that the unpaired people can look

When p=1 and n>3 an over count occurs because the remaining people could also be looking at each other. Therefore subtract the results for p=2 (which removes this over count). But then we need to add back in p=3, etc. Therefore the final expression for "s" uses inclusion-exclusion. This hopefully explains "s", which is the numerator of P(n).

The denominator for P(n) is obtained by realising that here are n people and every one of them can look at any of (n-1) people therefore [imath](n-1)^n[/imath] ways.

 

[Cubist]

Here's a formula

And here's a graph for different number of people...



NOTES: It should really be drawn with discrete points, but a line it's easier to see how it flattens out. Note that the probability goes below 0.4 since P(1000)≈0.3940768.