My brother, who works in urban planning, called and told me I should read the article “X And The City” in the current issue of Smithsonian Magazine.
I did, and was quite disappointed. Here are my thoughts:
It’s the season for the “March Madness” college basketball tournament, and it’s also the season when people place bets on exactly what the outcome will be – not the exact scores, if I understand correctly, but which teams will win each game. If you didn’t already know, MM is a single-elimination contest among 64 different excellent varsity college basketball teams; one loss and your team is out. If your team wins every single game it plays (six games), your team is the national champion.
Inspired by seeing an office pool and a recent book on how some gamblers ‘fix’ sporting events all over the world in order to win more money, I got to wondering how difficult it would be for someone like me who knows almost nothing about college basketball to predict the exact outcome of the tournament. Not just which team will takes the ultimate trophy, but which team will lose and which team will win, in all of the many individual matchups? (Forget predicting point spreads — you need a lot of inside knowledge to get that right, and that’s precisely the sort of thing that gamblers pay referees and players to cheat on.)
My question is simpler: exactly how many combinations and permutations will there be of who will be the winners of each and every single game of any year’s March Madness?
Thinking that tackling the actual problem would initially be too difficult, I decided to try a simpler question. What if there are only two teams? Obviously, only 2 outcomes: either team A wins, or team B wins, end of story.
How about if there are four teams? (Note: for there to be no “byes” and for this to be single-elimination, this column only considers cases where there are 2^n teams: 2, 4, 8, 16, 32, 64, and so on.) The answer was not obvious, so I drew a little diagram of all possible cases, which I roughly reproduce with MSPaint, here:
I called the teams A, B, C, and D. As you can see, there are exactly two ways that team A can win, two ways that team B can win, two ways for team C to be victorious, and two ways for team D to win – a grand total of 8 possible outcomes.
Another way of thinking of this is NOT to list and count all of the possible outcomes, but to figure out a way of counting WITHOUT counting.
I looked at the same situation and realized that there were two outcomes possible for each and every game, and you can multiply the number of possibilities at each node (location where two branches meet) branch by the number of possibilities at each other branch to get the same result, as you see here:
If there are eight teams, there are seven nodes, as you can see here:
Which works out to 2 x 2 x 2 x 2 x 2 x 2 x 2 outcomes, or 2^7. Notice that 7, the exponent, is one less than 8, the number of teams, just as 3 (the exponent in the previous case) was one less than 4, the number of teams. Does this pattern continue?
Yes, it does! I took my previous drawing and extended it to 16 teams, mostly by copying and pasting, which doubled the number of nodes, then I added one more at the very bottom. So this gave me 7 x 2 + 1, or 15 different nodes, or 2^15 different possible outcomes, and, as before, 15 is one less than 16.
Consequently, continuing the same pattern, if there were only 32 teams in March Madness, then there would be 2^31 different possible outcomes. In the current, real-world March Madness, there are 64 teams, so there must be 2^63 possible ways that the entire tournament could come out. (Which, parenthetically, is the number of grains of rice on the very last square of the mythical rice-doubling-award that was legendarily asked by the inventor of the game of chess…)
Is that a large number? Heck, yes! In fact, the numbers get very quickly very huge.
2^1 = 2
2^3 = 8
2^7 = 128 (over a hundred)
2^15 = 32,768 (over thirty thousand)
2^31 = 2,147,483,648 (over two billion)
2^63 = about 9,223,372,036,854,780,000 (my computer can’t exactly count that high, but it’s over 9 quintillion!)
If you were counting the seconds since the Big Bang, which apparently occurred over 14 Billion years ago, you would be nowhere near that result. You would in fact need roughly twenty lifetimes of the entire universe to count that number of seconds…
March Madness indeed. And, knowing as little as I do about which teams are better or worse, I would be indeed mad to try to bet on the outcome. What about you?
Since my days as in HS and undergrad, computers have gone from something that was extremely rare but not impossible, all the way up to complete ubiquity in the US and much of the rest of the world (I don’t know exactly how far, but they have now reached tiny villages with no electricity or running water in Benin, west Africa, according to my niece who did a stint in the Peace Corps there: she tells me that lots of village and town folks had cell phones, which are, essentially, small, special-purpose computers. The relative cheapness of computers means that computational tasks that were only done by experts with access to rare computers, some years ago, can be done instantly and easily with Excel or an ordinary scientific or graphing calculator, which is on your smartphone anyway. (A safe bet that you, my reader, have one.)
I was one of the early folks with access to some sort of computer. In 1965, being a scholarship kid at a good New England boarding school, we had access to some early mainframe computer located at Dartmouth College (in NH like my school). We accessed the main computer via WATS lines (a fore-runner of the 800 phone system) and an honest-to-goodness modem that held the handset of the telephone in a cradle. We used some operating system referred to as “time-sharing” which meant that nobody at any of the 10 or 50 or 100 remote or local consoles noticed the presence on the computer of anybody else, which meant that we didn’t have to punch IBM cards and carefully arranged in trays and submit them to a computer operator — and then to await our turn in the queue in “batch mode” – the exact opposite of time sharing.
At that HS, we had a teletype printer that printed everything on a long roll of paper. We loved the thing and even imitated its type font. I was scornful of those kids who wrote simulations of baseball or football games, thinking that wasn’t serious. Boy, was I wrong! The games my schoolmates were writing in our spare time at the computer lab, after sports and classes and before bedtime, fit in our schedule around the time needed for completing our other homework assignments, were incredibly crude by our standards today, of course (the computer would describe the flow of the game in a few words and then ask you if you wanted to throw a fastball, a curve, or a sinker or a knuckleball, and then the computer would work out a pseudo-random number and make a decision as to what happens next (grounder to first, double play, pop fly, safe hit, double, home run, etc). But the genre of computer games has obviously earned its makers and promoters a TON of money over the years and have attracted the very, very best programmers and computer artists of all types. So don’t take everything I say as the gospel truth. Nor the words of anybody else, even your very own self.
(/brag & reminiscence ON/ I won a third place contest when I wrote a program that would do tons and tons of calculations and then print out, on the same roll of teletype paper, a very crude graph of absolutely any equation the user wanted, at any scale that might be desired, using an algorithm that I devised as a modifrication of some spaghetti code I had seen somebody else write. I mean even equations that were as complicated as
/brag & reminiscence OFF/)
I remember my brother and lots of sociology or psychology students having to make computer runs in various semi=specialized statistics packages that calculated all sorts of stuff about all sorts of data. (Usually the computer’s output was that you had made some sort of syntax or usage error and you needed to fix the error and try again later, whenever that might be.) I remember collecting IBM punch cards and computer printouts from the recycling bins at the University of Maryland so I could use them for scratch paper and flash cards in my classroom, back in the late 1970s and early 1980s. I also remember having to go to UM or UMUC or GWU or GtnU or CUA or AU or UDC in order to do various programming assignments in various languages . I, personally, only punched a handful of Fortran cards, treating it as more of a historical curiosity that i was glad I never had to use, similar to the way that folks look at slide rules today.
But there is a difference: I understood exactly how every part of the punch card mechanisms and its electronic alter-egos worked together. I could write the Fortran code (not well, but I took part of a course and taught myself from books, before going on to learn many other computer programming languages. However, I bet that most folks, even those who have just finished a year or semester of working with logarithms, could not explain how or why a slide rule worked.
Let me name a few of the computer languages I have learned, more or less in order, and in no particular order as to how well I learned them:
BASIC (in lots and lots of different variations), COBOL, FORTRAN, Logo (lots of varieties), Pascal, C-64 and Apple 2 assembly and machine language, IDL, Python. Then I said that was enough.
I also learned how to use probably a dozen different types of typewriters and later word processors, and also was quite serious about calligraphy for several decades. Old Underwood standard manual typewriters were quite different from portable or electric typewriters.
Naturally, I also used lots of different types of computational aids, Let’s try listing them:
I am sure that I am not the only person who thinks that it is not necessary to upgrade all electronic stuff all he time. Sure, the newest versions generally crash less often than the old ones, run faster, and have lots of new features, hut it’s rather expensive to keep having to buy new stuff. It especially doesn’t pay to be an early adopter, especially if you choose wrongly and you end up owning devices that are abandoned by the market and all of your hard-won detailed operating knowledge becomes useless.
Wait. That happens with everything these days!
Including cars. Here’s a little story:
The Subaru Forester my wife and I own was starting to cost a serious amount of money to repair after 10 years and 100,000 miles. We got an estimate from our most dependable mechanic that needed repairs to the window, trim, and transmission would be close to three grand on top of several grand in other repairs over the past year. Plus it would still remain noisy and not have good gas mileage, and the head gasket might be leaking, too.
When a car’s blue book value is not very much greater than the estimated repair bill, my solution is to start looking around for another car.
Not to fix it myself any more. These big jobs were never in my capacity to fix, even back when working on a car was pretty easy. In the old days (1920s through the mid-1980s) it was kind of essential for a guy to understand how to fix stuff on the car, and it often wasn’t too complicated — just really dirty and greasy. (The vast majority of women wouldn’t bother, as you probably remember, which gave rise to lots of jokes.) But today, the situation is different: almost nobody has the equipment, time, and necessary training to work on their own car. If you look under the hood, there isn’t any room left, and it’s extremely complicated to boot. Just to diagnose many problems you need a special-purpose computer.
I remember around 1980 that sometimes you could just disassemble an inoperable part such as a starter motor, clean it out really well, put it back together again, perhaps replace a washer or a nut, then reinstall it, and it would work quite well for some years. Plus, in some older Big 3 cars, one or two smallish people could easily bend over and fit in the engine compartment with the hood closed. So almost everything was easy to reach and take off and re-install.
But today, with modern cars, and going back to at least electronic ignition, a/c, and serious emission controls, all the way up to futuristic cars like the one we just bought (a prius v, level 3), you can’t do any of that.
Yeah, we bought a Prius V, which looks like it’s almost in a Matrix body, and we came to this conclusion based on some simple but useful consumer math. Our old car, the one that just reached 100 thousand miles, was great for many purposes. Perfect when it snows (except we had NONE this winter), fits my very large home-made telescopes and camping gear for remote dark-sky locations, and can hold many other things as well. It worked well up to 100 thosand miles, but then it started falling apart as I described. Our daughter had an old Subaru Forester like we did, and it also fell apart, but after more miles. (anything involving headgaskets is quite expensive!) BUT it had a big downside or two.
The overall gas mileage was around 20 mpg, which I think sucks. (Nearly every time we filled the tank over the years we would estimate what the mileagte (i.e. mpg rating) was. Some times it was a little bit below 20 mpg, sometimes a bit more. 20mpgt as an overall average is close enough and easy to work with. es, there are plenty of bigger cars that guzzle more fuel, but a Forester isn’t all that big. AWD is nice, but it really uses a lot of gas. I was envious of those who drove hybrids, but wasn’t sure they made sense for me, financially and so on.
Plus, Subarus are really noisy. You can’t stop the air from making wooshing sounds hecause of the way they made the windows, at least afrter the fist year or so. Plus, there ae lots o little rattly things all over the underside of the car – my mechanic’s approach was to take them off, one by one.
Now, Feb/March 2012, it began to make sense to buy a Prius, and let me explain why.
At 20 miles per gallon, 100,000 miles consumed roughly 5,000 gallons of fuel. It looks like gasoline is inching up to a long-term average of about $4 per gallon, which is what it used to cost in Europe about 10 years ago. So, using $4/gallon as a rough guide, that five thousand gallons costs $20,000. If I bought another forester, it would probably cost that much to fuel it in the next 10 years, all other things being equal.
However, the larger Prius V is supposed to get 41 to 45 mpg according to the famous EPA estimate. I used 40 mpg to be conservative on this for various reasons. If we drove a Prius 100,000 miles in 10 years and it gets 40 mpg, then it will use 2,500 gallons of gas. And at the same price of $4/gallon, that gas would only clost $10,000, which is half as much.
I don’t know about you, but to me, ten thousand dollars is a lot of money. It made me want to take a look. If I can save ten grand on a new type of car that can do the same thing but better than my old type of car, then that calculated $10K savings on fuel makes a big difference. It meant that the roughly $10K difference in price between a Forester and a Prius V could be essentially discounted.
Why not buy a used car? When we were young and broke (beginning teachers back in the 1970s and 1980s didn’t earn squat) my wife and I had a series of used cars, sometimes gifts from relatives (as we did for our own kids later on) and sometimes from private sellers or dealers. Some of the cars were great, some were absolutely horrible. So horrible that we laugh out loud because retelling the stories is so deliciously funny in a weird sort of way. (You could see the road through the floor! There were wasps in the upholstery! No dipstick, jack, no bald tires, trunk full of leaves!) But it’s really a huge hassle to sell your old car through classifieds or auto magazines or craigslist or whatever, and then to get a new one.
So a new car, traded in, a hybrid Prius V it is.
It’s like driving a computer. (Perhaps you’ve seen this before; I’ve driven in one a few times, but I find this a revelation.) The gas gauge almost never seems to move (exaggeration!). If I want it to, I can have the car tell me at every instant which way the power is flowing, including from the wheels through the electric motor back to the battery when I’m braking. The car’s display often claims that I’m getting over 100 mpg for a 5 minute stretch, especially when I’m coasting downhill or coming to a stop at a light or intersection. I don’t have to use the key in either the ignition nor the door, and I can tell my iphone to call my wife or anybody else. It claims its calculated the mileage at 40.3 mpg overall, but I can’t yet tell if that’s accurate, because I’m still at a half a tank of gas, so I can’t yet do the little elapsed miles divided by gallons purchased estimate to see what my real mpg is since when we bought it. We will see in a week or so.
Math is, truly, everywhere, and is part of our lives.
We all use it; better to use it well, without too much effort, than to use it poorly or only with great effort. I think we could do a much better job in school of showing how useful it really is. By that, I don’t necessarily mean we should teach formal algebra courses in 5th grade. I mean what I wrote, show kids lots of ways that they really do need to use math in many ways that are not in the old-fashioned curriculum more or less put in place in 1893 or thereabouts.
And since computers are, literally, all around us, let us use them in wise and intelligent ways that save us a huge amount of effort, to answer questions that mean a lot to us. Yes, you show kids how to do peprform standard algorithms or certain variations thereof. But you also show them how to use calculators and spreadsheets and other graphic or mathematical electronic tools as well.
A web page with very fun explorations that show what real mathematicians do:
(Hint: long division, balancing checkbooks, and adding fractions aren’t such a big part. I suspect that if we taught some of this stuff in class, kids would see that, in fact, math has some fun aspects — it’s not all drudgery. There is a lot of “gee-whiz” stuff that is accessible to the average layperson or young’un.