Name the members! What are the odds of getting at least one right? (an actually interesting math problem for stan Twitter)

This game has circulated K-Pop stan Twitter:

I’ve never actually attempted it myself, as I know that 99.999999% of the time I will screw this up. Badly. However, I’ve seen some pretty amusing results and heard some pretty funny stories about it.

Sometimes, people would play this game by getting a list of member names first to match them to their faces. This ostensibly increases their odds of getting everyone’s names right from practically zero to merely something undetectable by 10-digit calculators, and perhaps gives them something of a fighting chance of getting at least one. Anyway, let’s try this variant of this game, as described in a puzzle I posed to my followers:

with larger groups, the probability of getting at least one name correctly

[for example, a small group like mamamoo (4 members) vs. a large group like nct (21 members)]

— 🐼 GFRIEND LOCKDOWN | 1 year with 드림캐쳐 | #시연_v1 🐺 (@damivariable) September 1, 2019

It was pretty close, but a plurality said that the odds of getting at least one correct get better as the number of members gets larger. Let’s see how correct this is.

(Before we proceed, of course I’m making the following assumptions: we play fairly, i.e. we assign distinct names to every member.)

A Preliminary Approach

Let’s start by looking at small cases.

Say you have only one member. This isn’t particularly interesting, because there’s literally no way you can mess this up. This case also pretty much never pops up, so we can safely ignore it.

Now suppose we’re talking two members. Still not particularly interesting–there are only two possibilities. Either you get them both right, or you get them both wrong. So the odds are now 50%.

If we stop here, then our conclusion is that the odds are worse the more members you have.

Let’s move on to three members, the first actually “interesting” case here.

For convenience, let’s say that the members are 1, 2, and 3. Then we can think of each assignment of “names” as an arrangement of the three numbers: the first number is the “name” we assign to Member 1, the second number is the name assigned to Member 2, and the third member is the name assigned to Member 3. A number in the correct place is a member correctly named. Basically, getting them all right would be the arrangement 1 2 3.

There aren’t too many possible arrangements. In fact, there are exactly 6, and it’s not hard to list them all (red numbers denote numbers in their places):

1 2 3 ✔️
1 3 2 ✔️
2 1 3 ✔️
2 3 1
3 1 2
3 2 1 ✔️

Thus, the odds of getting at least one member are $\dfrac{4}{6} \approx 67\%$ .

In a similar vein, we can attack the case of four members. The list is a bit longer, but still manageable:

1 2 3 4 ✔️ 2 1 3 4 ✔️ 3 1 2 4 ✔️ 4 1 2 3
1 2 4 3 ✔️ 2 1 4 3 3 1 4 2 4 1 3 2 ✔️
1 3 2 4 ✔️ 2 3 1 4 ✔️ 3 2 1 4 ✔️ 4 2 1 3 ✔️
1 3 4 2 ✔️ 2 3 4 1 3 2 4 1 ✔️ 4 2 3 1 ✔️
1 4 2 3 ✔️ 2 4 1 3 3 4 1 2 4 3 1 2
1 4 3 2 ✔️ 2 4 3 1 ✔️ 3 4 2 1 4 3 2 1

This gives us odds of $\dfrac{15}{24} \approx 63\%$ .

Listing all arrangements isn’t exactly the best way to study this though. The reason is that the number of arrangements grows extremely rapidly as the number of members does. For five members, we have 120 arrangements; for seven members, we have 5,040 arrangements; for the 21-member NCT, there are more than 51 quintillion arrangements (51,090,942,171,709,440,000 to be exact)!

We thus need to attack this more systematically. In the succeeding sections, we will cover some basic counting concepts, then apply them to this problem.

Factorials

Again and again, we will be considering products of the form $n \times (n - 1) \times \dots \times 3 \times 2 \times 1$ where $n$ is a positive integer. We denote this product by $n!$ . Before you break your roommate’s ear yelling out numbers, know that this is actually read as “n factorial.” For example, $3! = 3 \times 2 \times 1 = 6$ ; $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ , and $21! = 51,090,942,171,709,440,000$ . As a matter of convention, it is useful to define $0! = 1$ . We will see why in a bit.

In fact, the number of possibilities for $n$ members is exactly $n!$ . To see why this is so, let’s look at the case for three members. For member 1, there are exactly three possible names you can give them. Then for member 2, since one of the names has been assigned to member 1, there are exactly two more names. Finally, for member 3, there is exactly one name remaining.

Thus the total number of possibilities we have for three members is $3 \times 2 \times 1 = 3! = 6$ . More generally, if you have $n$ members, then there are $n$ possible names for the first member, $n - 1$ possible names for the second member, and so on and so forth until you have to assign the last name to the last member, and the total number of possibilities is $n \times (n - 1) \times \dots \times 1$ which is exactly how we defined $n!$ .

Permutations and Combinations

A permutation of $k$ distinct objects out of $n$ distinct ones is an ordered selection of $k$ objects out of $n$ , where $k \le n$ . We denote by $P(n, k)$ the number of permutations of $k$ objects out of $n$ . For example, suppose we want $P(n, n)$ . That is, we choose all $n$ objects, and order them. Basically, we are just counting the number of ways to arrange $n$ objects. Thus, from the above, $P(n, n) = n!$ .

For another example, we want $P(3, 2)$ . We have exactly six such permutations: 1 2, 1 3, 2 1, 2 3, 3 1, and 3 2. There is another way to arrive at that answer without listing everything down. First, we count the number of possible choices for our first number. There are three. Then, for each choice of the first number the number of choices for the second number is two, and so we have $3 \times 2 = 6$ permutations, as desired.

More generally, suppose we want permutations of $k$ objects out of $n$ . For the first object, there are $n$ possibilities. For the second, since we already chose one object, there are $n - 1$ possibilities left. For the third, as we have chosen two objects, there are $n - 2$ possibilities. And so on and so forth. Until we get to the $k$ th object, where, since we have chosen $k - 1$ objects, we have $n - (k - 1) = n - k + 1$ possibilities. Thus,

$P(n, k) = n \times (n - 1) \times (n - 2) \times \dots \times (n - k + 1)$ .

In fact, we can rewrite this formula in terms of factorials. This is the product of all numbers from $n$ to $n - k + 1$ . However, we can think of this as the product of all numbers from $n$ to $1$ , but we remove everything from $n - k$ to $1$ . Thus, we have

$\displaystyle P(n, k) = \frac{n!}{(n-k)!}.$

(This is why we use $0! = 1$ .)

Combinations are like permutations, except that this time, order does not matter. We denote the number of combinations of $k$ objects out of $n$ by $C(n,k)$ .

For example, if we want $\displaystyle C(3,2)$ , we want to choose two out of 1, 2, 3. We choose 1 and 2, 1 and 3, or 2 and 3. (Note that choosing 2 and 1 is the same as choosing 1 and 2.) Thus $\displaystyle C(3,2) = 3$ .

Let’s find a more general pattern given $n$ and $k$ . From the above, counting the number of permutations of $k$ objects out of $n$ , we have $\displaystyle P(n, k) = \frac{n!}{(n-k)!}$ . However, for each combination of $k$ objects, we have $k!$ different arrangements, and thus there are $k!$ different permutations corresponding to any such combination. Thus, we have

$\begin{aligned}[t] C(n,k) &= \frac{P(n,k)}{k!} \\ &= \frac{1}{k!} \times \frac{n!}{(n-k)!} \\ &= \frac{n!}{k! \times (n-k)!} \end{aligned}$

The Principle of Inclusion And Exclusion

Suppose we want to count the number of items in a bunch of sets. Say we have two fandoms, A and B, and we want to count how many people are in at least one of the two fandoms. First, we count the number in A, then we count the number in B. Then we add them. Unfortunately, this approach gives us too many, because some people are in both fandoms and get counted twice. To compensate, we subtract the number of people in both fandoms. Now everyone is counted exactly once, and we are happy.

Let’s try this for the case of three fandoms. Let’s add C as a third fandom. So if we naively add the number of those in A, those in B, and those in C, we’ve counted the number of people in A and B, B and C, or C and A twice, and in fact we’ve counted the number of people in all three fandoms thrice! To compensate, we subtract the number of people in A and B, B and C, and C and A.

However, when we do this, we subtract the number of people in all three fandoms thrice. Since we added them thrice earlier, they are no longer accounted for. To finish off, we have to add this number back.

In general, if we want to count the total number of distinct elements of a union of sets, we first count the number in one of the sets, then we subtract the number in two of the sets, then add back the number in three of the sets, and so(w)on and so forth.

This formula is called the principle of inclusion and exclusion.

Let’s now try and apply this to our original problem. For the case of four members, we counted exactly 15 arrangements with at least one correctly placed number. Let’s see if we can get this number without listing everything.

First, we count the number of arrangements with one correctly placed number. If 1 is placed correctly, then we can place 2, 3, 4 wherever we want. This gives us $3! = 6$ arrangements where 1 is placed correctly. Similarly, we have 6 arrangements where 2 is placed correctly, 6 arrangements where 3 is placed correctly, and 6 arrangements where 4 is placed correctly.

Of course, if we naively add these together, we get $6 \times 4 = 24$ arrangements with at least one correctly placed number, which doesn’t make any sense at all.

The problem is that we’ve counted some arrangements more than once. For example, when we counted the arrangements with 1 placed correctly, we also counted some arrangements where 2 was placed correctly as well; these arrangements then got double-counted when we counted the number of arrangements with two placed correctly.

To compensate, we count the number of arrangements with two correctly placed numbers. For example, if we place 1 and 2 correctly, we have to place 3 and 4, and there are exactly $2! = 2$ ways to do this. Similar count for 1 and 3, 1 and 4, 2 and 3, 2 and 4, 3 and 4. Thus we subtract $2 \times 6 = 12$ from our answer.

This leaves us with an undercount now, though, for similar reasons. The arrangements where three numbers were placed correctly were subtracted too many times, so now we have to add them back in. We have exactly one arrangement where 1, 2, and 3 are placed correctly. Similarly, we have one arrangement where 1, 2, and 4 are placed correctly; one where 1, 3, and 4 are placed correctly; one where 2, 3, and 4 are placed correctly. We thus add $4$ to our answer.

And again, to compensate for the overcounting, we have to subtract the arrangement where all four are placed correctly, namely 1 2 3 4. Thus, finally we subtract $1$ , and our answer is $24 - 12 + 4 - 1 = 15$ , as we wanted.

Let’s tackle this generally. Suppose you want to count the number of arrangements of $n$ numbers with at least $k$ of them placed correctly. First, we choose which $k$ of them to place correctly. There are $C(n,k)$ ways to do this. Then, for the remaining $n - k$ objects, there are $(n - k)!$ ways to arrange them. Hence, there are $\displaystyle C(n,k)\times(n-k)!$ such arrangements.

Thus, by applying the same reasoning as in the preceding example, the number of arrangements of $n$ numbers with at least one number placed correctly, which we shall denote by $A(n)$ , is given by the formula

$\begin{aligned}[t] A(n) &= \displaystyle C(n,1)\times(n-1)! - C(n,2)\times(n-2)! + C(n,3)\times(n-3)! - \dots + (-1)^{n-1} \times C(n,n) \times (n-n)! \\ &= \frac{n!}{1!\times(n-1)!}(n-1)! - \frac{n!}{2!\times(n-2)!}(n-2)! + \frac{n!}{3!\times(n-3)!}\times(n-3)! - \dots + (-1)^{n-1}\times\frac{n!}{n!\times 0!}\times 0! \\ &= n! \times \left(1 - \frac{1}{2!} + \frac{1}{3!} - \dots + \frac{(-1)^{n-1}}{n!} \right) \end{aligned}$

and so, if we define by $P(n)$ the probability of getting at least one out of $n$ members right (let’s not confuse this with $P(n,k)$ ), we have

$\begin{aligned}[t] P(n) &= \frac{A(n)}{n!} \\ &= 1 - \frac{1}{2!} + \frac{1}{3!} - \dots + \frac{(-1)^{n-1}}{n!}. \end{aligned}$

With the above formula, let’s study the behavior of the values of $P(n)$ .

$\begin{array}{c|c} n & P(n) \\ \hline 1 & 1.000000 \\ 2 & 0.500000 \\ 3 & 0.666667 \\ 4 & 0.625000 \\ 5 & 0.633333 \\ 6 & 0.631944 \\ 7 & 0.632143 \\ 8 & 0.632118 \\ 9 & 0.632121 \\ 10 & 0.632121 \end{array}$

You can see that the values go up and down. However, they quickly get close to about 0.632121. In fact, we are sure they won’t get too far from that after some point. Note that the difference between consecutive values of $n$ is $\dfrac{1}{n!}$ . Since $n!$ gets large rapidly, $\dfrac{1}{n!}$ gets very small rapidly. Moreover, aside from the changes getting very small rapidly, they also take turns going in opposite directions, so any “attempts” to break away from this limiting value are immediately undone by the next change.

This reasoning can made just a bit more rigorous to conclude that indeed the answer is that the probability, in fact, stays roughly the same as $n$ gets large.

An Infinite Series

We can do even better than 0.63, in fact, if we want a name for this value. Euler’s number, denoted in many calculators as $e$ with approximate value $e \approx 2.71828$ , is a magical and mysterious thing, and if I were to try and explain all of its awesome properties, I would never finish this article. Anyway, one of the cool things about it is that for any number $x$ , the sum

$\displaystyle 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots$

gets closer and closer to the exponential $e^x$ the more terms we add.

If we let $x = -1$ , this means that

$\displaystyle 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots$

gets closer and closer to $e^{-1} = \dfrac{1}{e} \approx 0.37$ .

Hence, from simple manipulation, we see that

$\displaystyle \frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \dots$

gets closer and closer to $1 - \dfrac{1}{e} \approx 0.63$ the more terms we add. But in fact the sums of the first $n$ terms here are exactly our values of $P(n)$ .

Exercise: The Case $n = 7$

e0097535b9082b6bd787e3d4a7955c5c92a32c4fc538e5d381aa6eef491b86bc.jpg

These girls’ stage names are JiU, SuA, Siyeon, Handong, Yoohyeon, Dami, and Gahyeon.

Based on the formula above, what are the odds you will get at least one of them right?
Do try and identify these members.
Bonus: try to identify them in the clip below.

Name the members! What are the odds of getting at least one right? (an actually interesting math problem for stan Twitter)

Published by xdoublestar

Leave a Reply Cancel reply

Share this:

Like this:

Published by xdoublestar

Leave a Reply Cancel reply