Brin and Bear It
I attended the same high school as Sergey Brin, co-founder of a verb called "Google." Sergey dropped out in 1990, the year I started at Eleanor Roosevelt High School. By all accounts, he was extremely bright. But from the little I've heard of him via direct anonymous sources (*cough* former-math-teacher *cough*), he was quite cocky about his intellect, often trying to prove teachers of various subjects (read: Math) just how wrong they were. But this is utterly forgivable, given that almost any successful self-respecting computer scientist went through such a phase during his teenage years. (If, however, you are remembered fondly by all your high school teachers and friends, chances are incredibly good that you're also a handsome business major now working at a consulting company who's wandered onto this blog by accident. But I digress.)
Who's Line Is It Anyway?
There's been quite a lot written about Sergey Brin, but hardly enough about a much lesser known Brin -- Dr. Michael Brin. In addition to being precocious Sergey's father, Dr. Brin was also my favorite professor at the University of Maryland. He taught what was easily the most enjoyable class in my college career. I would have taken more of Dr. Brin's classes if the university system allowed it, but alas a computer scientist of meager intellectual means couldn't afford the heavy IQ tolls imposed by his graduate-level math courses.
Dr. Brin is a first-rate orator who begins every class with a smoke. Well, usually he'd show up, pose a rather vexing problem, and then escape for a cigarette in the midst of the ensuing confusion. He expected an answer from the class by the time he returned. Invariably no answer was forthcoming, since that's the entire point of a vexing, smoke-break-enabling problem. (At this juncture, I know those of you in technical fields are just dying for an example of a vexing Dr. Brin problem, just so you can solve it faster than I could smoke a cigarette to prove me dumb. I'll bite and indulge. Answers at the end. And I don't smoke.)
Vexing Problem #1. You have an 8x8 grid of squares and 31 dominoes. Each square in the grid is exactly half a domino large, such that each domino placed on the grid covers two squares. How do you arrange the dominoes such that all the squares in the grid are covered except for the two squares in the outermost corners of the grid diagonal from each other? If this cannot be done, provide a proof of why not.
Vexing Problem #2. You have a solid bar of chocolate that's pre-scored by the helpful chocolate bunnies at the Hershey factory into four rows and eight columns (such that if you broke the chocolate along those lines, you'd end up with 32 pieces of chocolate). Prove the minimum number of breaks that are required to break the bar into its 32 pieces (you may not stack or otherwise cheat on how you count breaks -- a break is any one fracture along a pre-scored line on one solid piece of chocolate).
Vexing Problem #3. You are in a maze of twisty little passages, all alike. (Ho ho! You either laugh or scratch at this one, but in either case Dr. Brin would certainly not have posed this most vexing of problems.)
In addition to loving wacky problems, true enjoyment of a Dr. Brin class can only be had if you check your ego at the door. Almost half the statistics class he taught dropped out after the first session because they couldn't handle his assault and battery on their sense of self. Attending his classes was like experiencing the drill sergeant in Full Metal Jacket -- unless you braced for impact, your ego would likely leave wounded or even dead.
As for me, I was his Private Gomer Pyle, and I loved every minute of it. Dr. Brin would often hand back graded tests with a simple, "My sincere condolences." He'd openly make fun of wrong answers to his questions, which I believe he found amusing the way we find children amusing when they ask where babies come from. His spirited and equal-opportunity barrage on all students backfired only once in all my recollection:
Dr. Brin: It's time for an Odyssey of the Mind -- time for our statistics final.
[Most students understand the implications and put away their calculators. One student, let's call him "Bart," obviously didn't follow.]
Dr. Brin: Bart. You have your calculator on your desk. What -- do you ~love~ your calculator?
[A few students giggle nervously]
Bart (startled, confused, and a bit hurt): Every night.
[Dr. Brin is so caught off-guard by this genuinely clever answer, made in a spirit so congruent with how he ran his classes, that he allows Bart the unique privilege of using his calculator during the test.]
If crushed egos was the price for true learning, then I was ready for the abuse. Dr. Michael Brin's classes were always great and full of laughter (albeit at your own expense). I didn't mind being constantly reminded that my intellect was inferior. It was refreshing in an inexplicable, self-effacing way. And it was worth it to learn from one of the best.
How I (Almost) Made My First Million
One of the last conversations I remember having with Dr. Brin was one which I initiated. I was blissfully raving about this great new search site I had found, then in Alpha mode, called Google. It was done by some Stanford students! It didn't have ads! It was much better than then-market-leader AltaVista, and I wanted Dr. Brin to try it out.
He matter-of-factly replied that his son Sergey was a key member of the Google team. He also suggested that I write his son to see if there might be an employment opportunity for me.
Sergey never wrote back.
So here's to Dr. Michael Brin: May the laughter never end, may the smoking never stop. May only the humble learn at your fount of intellect, and may you always find interesting problems to puzzle and amuse.
Thiiiiiis Is Hoooow We Doooo It... (This is how we do it!)
You've stayed long enough. You've scrolled far enough. You want answers, and you want them now. And you're not going to settle for me promising them to you next week (We all know what happened last time when I suggested that. I hope you still have your day job as a programmer. If not, in the words of Dr. Brin, "My sincere condolences.").
Vexing Solution #1: You can't cover all squares but two diagonal outer corners. The proof is in the custard: Imagine the 8x8 grid was a chess board. Each domino would clearly have to cover exactly one white and one black square, no matter how you placed it on the board. Two diagonal outer corners are going to be the same color -- either both black, or both white. Given that you start with 32 uncovered black squares and 32 uncovered white squares, it's impossible to leave two squares of the same color uncovered if each domino covers one square of each color. This is called a parity problem, and is an excellent example of how many seemingly complicated problems are actually easily solved (and proven!) when you view them from the right perspective. (All three of the business majors that are reading this blog by accident should turn this principle into a trendy bestselling business book. I feel one coming. Pull my finger.)
Vexing Solution #2: I ask this one in interviews all the time. Inevitably, people start testing all sorts of conjectures. (You know the true computer scientists right away because they insist that breaking the chocolate into successive halves must be the best way. It just must!). Most interview candidates don't realize that to prove a minimum by such a method would require exhaustively testing all the possibilities, which is clearly too many (even for those of you who were just about to respond with some comment about symmetry [or how your job has gone to India and now you're browsing the web all day]). Far better to learn from Vexing Solution #1 and see this problem from a different angle. Here's the angle: no matter how you break a piece of chocolate along a pre-scored line, you always end up with the same thing -- two pieces of chocolate. Any break always adds one and only one to the total number of separate pieces of chocolate you have. So by induction, the number of breaks it takes to break one solid bar of chocolate into its 32 constituent pieces is always 31, no matter how you choose to break it. So be you Row-ist, Column-ist, Half-ist, or Whatever-Other-Compulsive-Chocolate-Breaking-Strateg-ist, know in your heart of hearts that it doesn't matter. 31. Always.