So I was at a Waffle House with my son (age 11) and he was telling me about his idea for a new game, based on the Nintendo Mike Tyson’s Punch Out!
First, you’d go through and fight each of the 11 opponents (from the original game) one at a time, ending with Tyson. But then, you’d go through and fight all the opponents two at a time, starting with the weakest combo (i.e. Glass Joe and von Kaiser) and ending with the strongest (Super Macho Man and Tyson).
Then, you’d go through and fight the 11 opponents 3 at a time, in all possible combinations.
And so on, up until you had a single match where you had to box all 11 opponents simultaneously.
I told my son that was really interesting, but then to make it educational I said, “So how many total matches would you fight, in your new game?”
My son looked down at his hands and appeared to be counting with his fingers. After maybe 10 or 20 seconds, he says, “One thousand and such-and-such.” But then he quickly changed it, “No, 2,047. Yeah, 2,047.”
So I thought he wasn’t even close, because I had been thinking through some of the individual components of the total number, and thought they would be big numbers. And in any event, I was quite sure that him looking at his fingers for 10 or 20 seconds wouldn’t get the answer to such a question.
I took out my phone and we did it through brute force. If you’re taking the opponents 1 at a time, obviously you go through 11 matches. If you take them 2 at a time, there are 11×10 different permutations (there are 11 possible guys in the first “slot,” and then 10 possible remaining guys for the second “slot”), but since you don’t care about the order, you divide by 2. For example, two of the permutations are “Piston Honda, Bald Bull” and “Bald Bull, Piston Honda,” but you only count that as one combination. So, you divide 11×10 by 2.
With 3 possible opponents, you do 11x10x9, but then divide by 3x2x1 different ways of arranging them.
With 4 opponents, it’s 11x10x9x8 divided by 4x3x2x1. And so on.
So here are the subtotals that I calculated, where the first number is the number of opponents per match:
Just to make sure you get the pattern, consider the 2nd last one, where you’re fighting 10 opponents at once. Well, what’s “special” about each match is the one guy who’s not in the ring with you. Since there are 11 total opponents, that means there are 11 different matches where you fight 10 guys at a time.
Then with 11 opponents in the ring with you, there’s only one match, because there’s only one way to fight all the guys at once.
As I was calculating the 7th or 8th subtotal, my son asked, “Do you want me to explain my trick?” (Or maybe he said “technique,” I can’t remember.) I said, “Hold on, let’s make sure you got the right answer first.”
So I totaled them all up and…the answer was 2,047.
At this point I was astonished (although I had started to think he might be right when I saw that the subtotals put it in the right ballpark). How the heck did he do that?
He explained that he had seen a Khan Academy video showing that if you wanted to figure out how many total ways to organize your hands, where the only options were to stick a finger out or in, then the answer was 2^10 minus 1, in other words 1,024-1 = 1,023.
So then my son realized that if each finger were an opponent, then he could represent whether the guy was in the match or not by having the finger point out or be curled up. So, if there had been 10 opponents, then the total number of possible matches would be 1,023.
But there were 11 opponents. So my son knew the answer was 2^11 – 1. Now normally, it would have taken him a bit to figure out 2^11 in his head. But he remembered 2^10 was 1,024 from the Khan video, so all he had to do was double it to 2,048, then subtract one to get the answer of 2,047.
In conclusion, in case you got lost in the details: My son correctly computed the answer in at most 20 seconds using his fingers, while it took me a good 10 minutes with a calculator and memo pad. (I actually made some mistakes a few times, which I knew because, e.g., sometimes I’d get a decimal, and then sometimes I would deviate from the nice pattern you see above. It’s almost a philosophical issue to think about that I “knew” when I had mistyped on my phone calculator, even though I didn’t prove to myself why that pattern should exist until afterward.) Furthermore, he didn’t just get lucky; he was relying on a principle he had learned in a different context which he tweaked for this problem.
P.S. I am quite certain someone is going to feel the need to say, “Who the heck doesn’t know that you do (2^n)-1 for problems like this?” Uh, most people.