My Son: 2,047
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:
1: 11
2: 55
3: 165
4: 330
5: 462
6: 462
7: 330
8: 165
9: 55
10: 11
11: 1
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.
“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.”
I was going to say that teachers like to show tricks like this to help you get the answer faster, but they don’t explain the logic of why it works.
I don’t consider that to be teaching.
Learning the tools generally follows from needing to use them. I became very skilled at Excel by learning the pieces I needed. On the other hand, my skill flowed from the ability to apply pieces of precedent software (e.g. MS DOS hot keys). Having learned the tools puts Bob’s son far ahead of classmates who will have to learn tools while they learn the substance. In addition, learning the substance underlying the tools will return innumerable “aha” moments as he progresses…as it clearly did in Bob’s post.
Well, learning the tools ahead of your peers is certainly a good thing, but learning the substance ahead of your peers is even better. Learning the substance before learning the tools is often quite valuable, for multiple reasons. For one thing, you’re less likely to make mistakes, because you know why you’re doing what you’re doing. And for another thing, it makes things the subject more interesting, so you’re more engaged in learning the tools, as opposed to just treating it as a dumb thing you have to memorize as a means to an end. Let me quote from a comment I wrote on Gene’s blog a while back:
gene-callahan.blogspot.com/2015/07/why-are-books-of-mathematics-bad-at.html
“Gene, I agree 100% with your complaint about linear algebra. I’m one of those kids who learned linear algebra in high school, and when I got to the part about similarity and diagonalization, I kept thinking to myself “Why would anyone ever diagonalize a matrix, or care whether two matrices are similar or not?”
Then in college I took honors linear algebra, where we studied theorem after theorem all of the form “If M is a matrix representation of a linear transformation T, and T has such-and-such property, then M has such and such property.” Finally I raised my hand and asked “We’ve come across so many theorems that allow you to deduce the properties of a matrix if you know it’s a matrix representation of some linear transformation. But that means that if two matrices represent the same linear transformation (with respect to different bases), then we automatically know they have so many properties in common. So what’s the relationship between two matrices that represent the same linear transformation?” My professor responded “We call such matrices ‘similar'”. That was the first time I really understood similarity.
This comment was written partially to support your point, and partially just to share another “secret” of linear algebra!”
Let me give you another example. I first learnt calculus (in 6th grade) the way it was invented, through infinitesimals. When you learn it like that, as opposed to using limits, everything makes so much more sense; you understand what dy/dx means, you understand why the chain rule, the product rule, and the quotient rule work. And it’s especially helpful in integral calculus. For one thing, the fundamental theorem of calculus becomes obvious: the integral of f(t) dt from x to x+ dx / dx is equal to f(x). And the process of integration makes much more sense. Most people when they’re learning calculus treat integration as a dark art, where you memorize a bunch of “strategies” to try to do the integral. If you’ve ever seen a student flail around trying to do a trig substitution, you’ll know what I mean. But if you think in terms of infinitesimals, you’ll know exactly when to apply a trig substitution and which one to apply, because you know what integration by substitution actually means. And it becomes indispensable once you move to vector calculus. (Don’t believe the people who say you can’t understand partial derivatives through ratios of infinitesimals; you can.)
So knowing why I’m doing what I’m doing gave me a humongous advantage over my peers.
Let me illustrate what I’m talking about. I invite anyone who’s taken calculus to attempt the following:
PROBLEM: Find the integral of 1/x dx using integration by parts, letting u = 1/x and dv = dx
I predict that anyone who just blindly learnt calculus techniques as part of, say, an engineering program, will be utterly confused by what they get. They may well say something like “Math doesn’t make sense anymore.” I’ve actually given this problem to friends and even teachers and gotten exactly such reactions. But if you have your head screwed on correctly, you should understand what’s going on. That’s the benefit of knowing the substance behind the tools.
(Note: if anyone is attempting this, don’t expect to get an actual answer. But what you will get will likely shock you unless you’re understanding of calculus is built on a solid foundation.)
Keshav, I very much agree with you. In a different world (e.g. history and literature) teachers were moving in the direction of teaching grade school and high school students how to critique and interpret subjects while not requiring memorization and studying of the subject matter. The end result is that the tools go unused with nothing to practice on.
In Bob’s case it is exciting to see the easy way in which his son was able to integrate his learning with practical real-life inquiry.
Congrats on raising what appears to be a good son, Murphy. Maybe he can one day teach us Austrians how to do math at the Mises Institute (haha!).
The Khan Academy should go down in history as a precedent setting shift in education.
I am not as clever with math as your son, Murphy, but as a software/computer geek, I couldn’t help but notice/point out, that this principle of choosing, in this case the formula utilizes 2^10, is the same mathematical structure used in binary and computer science.
If you had a 10 bit (address bit) microprocessor (which would be rather old, as CPUs and address buses today are mostly 64 bit), then the most RAM, or random access memory, that such a CPU can utilize would be 2^10 = 1,024 bits. The base 2 is used because computers use binary language of 0 and 1. There are 1,024 possible combinations of bits that a 10-bit (address) CPU can read and write.
Adding more memory to a computer with that CPU won’t actually work in making your computer use that extra memory, because the CPU cannot code any more combination with only 10 bits and using only 0s and 1s. So manufacturers reached a memory bottleneck, encentivizing them to creating CPUs with larger address buses.
The classic 1981 IBM PC, with the 8086 CPU, had an 18 bit address bus, which translates to 1152 KB max memory.
A 32 bit address bus will allow a maximum 2^32 = 4,294,967,296 locations, or 4 GiB. A 64 bit address bus would in theory have 2^64 = 18 GiB. The actual would probably be lower due to certain factors that are not really relevant here.
Thanks MF. I totally see why it’s 2^n for binary code, but it still is not obvious to me why it’s 2^n for the power set. After he and I went through it, I remembered learning that in the past, but it must not have stuck with me (probably because I never saw why it worked).
You actually showed the reasoning in your post. Each fighter is in the fight or not. That’s 2 possibilities for each fighter, so 2^11 combinations. Then -1 because we don’t care about the case of no fighters.
With the power set stuff, you go through each element and its either in a subset or not. That’s 2 possibilities for each element, so 2^n possible subsets can be created.
Incidentally, this is the same reasoning you would use to prove that your way and your kid’s way are equivalent. That is,
n choose 0 + n choose 1 + …. + n choose n = 2^n.
I don’t remember being explicitly taught this equation. I remember ‘discovering’ it wile doing a discrete math problem where I went the choosing route, like you. I was so stoked I tried to prove it algebraically. I succeeded (I think), but it was a bit of a mess and I later found the easier proof using the reasoning above. The relationship has sort of stuck with me since.
Admittedly I’m one of the people that while reading your post was thinking – duh – 2^11-1.
Are you sure that your kid wasn’t just using his fingers to keep track of how many times he’s doubled in his head? Like he immediately thought of the Kahn video and then started doubling? Doubling is a foundational skill schools try to teach early on (I’m talking like 1st and 2nd grade).
@guest,
😉
“I totally see why it’s 2^n for binary code, but it still is not obvious to me why it’s 2^n for the power set.” Bob, just represent “in or out” as 1 or 0.
You and me both.
Wow, Keshav (and guest)! I’m being serious, thank you very much. That is obvious now that you’ve said it, but it never clicked for me before.
Bob, I’m happy to have helped you. And now if possible, I’d like to push your understanding one step further.
You now understand why the set of all binary sequences of length n has the same cardinality as the power set of the set {1,2,3,…,n}, because any subsets of that set can represented as a sequence of “ins” and “outs”, which can be represented as 1’s and 0’s. Well, the same principle applies when you go to infinity. That is to say, the set of all infinite binary sequences has the same cardinality as the power set of N. That’s because you can represent any subset of N as a sequence of in’s and out’s, like the set of prime numbers is (out, in, in, out, in, out, in, out, out, out, in, …) which you can write as a sequence of 1’s and 0’s like (0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, …) in this case.
And the cardinality of the set of real numbers between 0 ands 1 is the same as the cardinality of the set of infinite binary sequences. Why is that? Because if you put decimal point before any infinite binary sequence, you instantly get a base-2 representation of a real number between 0 and 1. For instance, the base 2 number 0.01010101… Is equal to 1/3. You can represent every real number between 0 and 1 like that, just as you can represent real numbers using decimals.
So now we reach the grand conclusion that the power set of N has the same cardinality as the set of real numbers between 0 and 1! That is why people say the cardinality of the set of real numbers is equal to 2^Aleph_0, where Aleph_0 is the cardinality of N. They are using the notation of 2 to the power of something to make an analogy to the finite case.
Spooky coincidence, Peter Schiff was talking about his kid getting A in his exams, just today.
Is there some sort of Austrian command center and briefing room?
Wow, clever boy you are having!
If you don’t like someone just show him binary 4 with your hand!
😉
And if you reallly really don’t like someone then the number is 132.
zing!
“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. ”
Doesn’t that exclude the possibility to have all fingers in? I mean if I only have 1 finger, then it is 2^1 options which is 2.
Obviously for the fighting thought experiment you need to calculate minus 1 since not fighting is not an option of course.
Skylien,
I didn’t watch the Khan video so I don’t know how they explained it in words, but it must not be including the empty set.
So in general, the power set has 2^n elements, if you include the full set and empty set as elements of the power set.
With the Punch Out problem we weren’t including the case where you fight 0 opponents, so you subtract 1.
And, I guess the Khan video said you have to be sticking out at least 1 finger.
Thus, if you only have 1 finger, then there is only 1 combo, i.e. 2^1 – 1 = 1.
Let’s not focus on the kid knowing the formula for the size of the power set. The clever bit is recognizing that this IS the power set. If you focus on the number of m size matches, 1,2 ,3 … etc you solve it like you did with your phone. If you get the aha you solve it like your kid did — the clever way.
Yeah, the fact that an 11 year-old could recognize the powerset connection is impressive. I knew the cardinality of a power set at age 11 (I even knew about transfinite arithmetic – I’m a lifelong nerd). But I don’t think at that age I would have been able to recognize that it’s a power set.
By the way, you’re comment gets me thinking, is there a simple way to prove using the combinations formula that the cardinality of a powerset is 2^n. Of course it’s trivially easy to just prove the cardinality of power set directly, but I’m wondering if there’s some sigma notation identity involving factorials that would give you the result from the combinations formula.
If you list every singleton, then every pair, then every triplet, etc up the the full set you have enumerated all the subsets once each. Hence the sums are equal. (For finite sets!)
Yeah, that’s obvious, but I’m just wondering whether it’s also possible to prove it using the combinations formula and sigma notation.
Wow! Justifiably proud papa.
whaaaattttt?
I recall mathematical series from Jr. high, this is sigma of 11 combination r where r ranges from 2 to 11. I’m glad i had good math teachers and i can recall it after more than 20 years even though i studied in a school from very small rural toen in India.
Bob, did you not realize that the problem boiled down to finding the cardinality of a power set, or did you just not remember the expression for the cardinality of a power set? Because as soon as I read the problem statement, the answer immediately came to me. But I’m not going to say “Who the heck doesn’t know…”, because the average person on the street has never even heard “cardinality” or “power set”.
It is deeply impressive that he could see the connection between what he already knew and the question at hand. The similarity in the two problems is non-obvious, in my opinion, and it would have taken me awhile to realize the connection myself, even though I would have come up with the numerical solution the way Dr. Murphy did quite quickly, and I have studied advanced set theory. That is one kid thinking outside the box!
Bob, I highly recommend that you get your son the book “The Number Devil”. It’s a book written for kids that introduces a lot of advanced concepts in math, including Pascal’s triangle, triangular numbers, the Fibbonaci series, the notion of axioms and theorems, the Sierpinksi triangle etc. My uncle, who’s a mathematician, got me the book in 4th grade, and it made me fall in love with the subject.
Another good book, which I read in 5th grade, is “The Fourth Dimension” by Rudy Rucker. It’s about visualizing the fourth dimension, the concept of Flatland, Plato’s cave, etc.
Getting off the topic of your son for a moment… I was poking around with that Kahn Acadaemy and there’s some pretty cool things on there.
https://www.khanacademy.org/computing/computer-programming/programming/intro-to-programming/a/learning-programming-on-khan-academy
They have done a good job! I really had not seen a resource like that, which is probably not a whole lot of use to an old dog like myself, but might have been very exciting to me a few years ago (OK, perhaps a lot of years ago, but that’s beside the point). It’s astounding that we have right now the regular government school system (let’s not mince words) turning into junk… while at the same time we have online education resources that are better than have every existed before. Seriously, nothing like this has ever existed in history.
I’m curious about the Kahn Acadaemy though… is it going to stay free forever? I mean I know they promise that, but people promise a lot of things, what sort of guarantee are we looking at?
Yeah, on the one hand I’m praising them (because they are doing excellent work) but with the other hand I’m stabbing in the back, but that’s the way of the world… a trust problem. Let’s just say that with age comes wisdom and with wisdom comes an inclination to scan through a lot of fine print.
How does this change the picture for home schoolers?
The whole MOOC (massive open on-line classes) universe is expanding rapidly. I have dabbled in classes from MIT and Coursera – at no charge – and have not been disappointed.
I’m also impressed that your eleven-year-old son is sufficiently knowledgeable about Punch-Out!! to run this gedankenexperiment. He even referred to Mike Tyson and not Mr. Dream, so it must be the NES original he’s familiar with. That’s awesome.
Also: I was terrible at Punch-Out!! when I was eleven. Actually, I’m still terrible at Punch-Out!!. The fact that your son thinks it should be way, way harder… I dunno, Bob. That might impress me even more than the math bit.
Congrats Dr. Murphy, You have every right to be proud.
That’s really cool, Bob. Your son must be a bright boy!
For the benefit of my daughter, I’m curious as to how he got turned-on to Khan Academy videos. Did he just decide to start watching them in his spare time, or do you try to point him to such things when he wants to know the answers to questions?
I wanna roll with the gangstas …
That is very impressive for a 11 year old !
BTW, this is a special case of the binomial theorem which would be known to a nerdy 17 year old (as you must have been a couple of decades ago :))
(a + b)^n = nC0a^n + nC1a^(n − 1)b + nC2a^(n − 2)b^2 + nC3a^(n − 3)b^3 + … + nCnb^n
Just put a and b = 1 and you get the desired equality..
2^n = nC0 + nC1 + nC2…… nCn
Wow, mind blown! It never occurred to me that those two things have a connection.
I’m now thinking, what other cool identities can one deduce from the binomial theorem?
Yogi, this is impressive for an 11 yr old. But think of why. In a world where school and state are separate, this would likely be the norm.
That’s utterly ridiculous; the average private school student wouldn’t be able to do this either. Also, although I went to public school, I’m basically self-taught in mathematics. I learnt calculus in the 6th grade, and I learned transfinite set theory at a very early age. I can conceive of no possible educational system, public or private, where it could ever become the norm to do what I did. And yet I do not think I would have realized the connection to the power set at age 11.
So although you might believe that the abolition of public education is a good thing, I’m quite confident that it would not have the effect you’re suggesting.
“I’m basically self-taught in mathematics. I learnt calculus in the 6th grade, and I learned transfinite set theory at a very early age. I can conceive of no possible educational system, public or private, where it could ever become the norm to do what I did.”
It’s a sacrifice. It takes hard work.
It’s a way of life.
(Aside: I’ll just throw a bunch of cool parties and charge you your teaching skills to attend.)