Below are the 20 most recent journal entries recorded in captaino's LiveJournal:

[ << Previous 20 ]

Friday, May 9th, 2008
1:52 am	Puzzle o' the Day 158! Here's a fun quickie! It isn't *quite* as easy as it may seem at first glance, but neither is it too terribly difficult. There are four major cities in Kreplachistan; they occupy the corners of a square with side 100 miles. The Kreplachistani elders wish to connect the cities with railroads; being cheap, however, they wish to lay as few miles of track as possible. What should their track network look like? How many miles of track must be laid? (9 Comments |Comment on this)
Thursday, May 8th, 2008
4:24 am	Puzzle o' the Day 157! Here's a classic poker puzzle. It's not too hard. All you need is logic and the rudiments of the rules of poker. Alice and Bob are playing a peculiar form of draw poker. Alice picks any five cards she wants from the deck. Bob then picks any five cards he wishes from the cards that remain. If she wishes, Alice may then discard any or all of her cards, and pick their replacements from the remainder of the deck. If he wishes, Bob may then discard any or all of his cards, and pick their replacements from the remainder of the deck (this does *not* include Alice's discard pile). They then compare their final hands, and see whose ranks higher. Since Alice gets the advantage of going first, Bob wins if their hands tie. With optimal strategy, who wins? What is that optimal strategy? (3 Comments |Comment on this)
Tuesday, May 6th, 2008
1:36 am	Puzzle o' the Day 156! Here's another terrific combinatorics puzzle. As usual, the only things required are arithmetic and reasoning abilities. A peace conference between Kreplachistan and Latkevakia features a circular table for the n diplomats attending. The appropriate set of n name-cards are fixed at equally-spaced positions around the table. a. (Easy). Let n be odd. Show there's a way for the diplomats to sit such that, no matter how the table is rotated, exactly one diplomat will be seated in the correct position. This is not true if n is even. Let's prove it via the following two sub-puzzles: b. (Easy). Let n be even. Suppose the diplomats sit such that nobody is in the correct position. Show there's a way to rotate the table such that at least two are seated in the correct position. One-word hint in white: Pigeonhole! c. (A fair bit harder). n is still even. Suppose the diplomats sit such that exactly one diplomat is in the correct position. Show there's a way to rotate the table such that at least two are seated in the correct position. Hint in white: For diplomat d, let f(d) be the distance clockwise around the table between his current seat and his name-card. What is the sum of the f(d)'s? What must it be divisible by? Are these contradictory? (3 Comments |Comment on this)
12:41 am	The John Williams Challenge Using only your brain, hum the main themes of "Star Wars", "Raiders of the Lost Ark", "Superman", and "E.T.", in order. It's hard. I think my favorite is the "Raiders" theme; every time I hear it, I'm transported back to when I saw the movie for the first time (age 9, I think). I remember cheering along with the Jamaican(?) crew of the ship when Indy swims over to the German submarine. All this is a roundabout way of saying the following: Please, "Indiana Jones and the Kingdom of the Crystal Skull", please, please don't suck. (4 Comments |Comment on this)
Monday, May 5th, 2008
5:34 pm	Scrabble tournament report Site: The "Original" (nee "Mel's") in downtown Berkeley Date: 05/04/08 Pre-tournament rating: 1799 (A2). Prior to this tournament, I had done little studying the last few weeks (where by "little", of course, we mean "no"); I had missed some easy bingoes on ISC recently (including FAINTEST(!)); and both captainparanoid and evwhore had beaten me in clunky games the night before, after we'd gone to see "Iron Man" (an entertaining piece of froth, btw, highlighted by some snappy line readings). The omens, in other words, were not auspicious. ( So of course I go 6-0 ) (4 Comments |Comment on this)
Saturday, May 3rd, 2008
5:27 pm	A musico-mathematical question for y'all This isn't puzzly* enough to be a PotD, but I thought I'd throw it out there anyway. 2^19 = 524288 is pretty close to 3^12 = 531441. Why is this important in music theory? (4 Comments |Comment on this)
Friday, May 2nd, 2008
11:57 pm	Test your perfect pitch This is rather a neat site. (1 Comment |Comment on this)
Thursday, May 1st, 2008
5:36 am	Puzzle o' the Day 155! We've had too many puzzles go unanswered recently. Here's an easy one. Really, I promise. You shuffle a deck of cards. Then, starting at the top, you reveal them one at a time. a. (Easy) What position (1 through 52) are you most likely to find the first black ace? b. (Easy) In general, given n between 1 and 52, what's the probability that you find the first black ace in position n? c. (Easy) What position (1 through 52) are you most likely to find the second black ace? (6 Comments |Comment on this)
Wednesday, April 30th, 2008
4:40 am	Puzzle o' the Day 154! Alice and Bob are playing Ultra-Super-Advanced Dungeons & Dragons (Alice and Bob are geeks). The only randomizer they have, however, is a weighted coin; while it comes up tails occasionally, it seems to be biased towards heads by an unknown amount. USAD&D includes "saving throws" that should be successful 1/pi = 0.318... of the time. Devise a procedure using the weighted coin that resolves saving throws correctly. Hint (in white): First devise a procedure using the weighted coin that will resolve 50-50 propositions correctly. Don't think too hard. (7 Comments |Comment on this)
Monday, April 28th, 2008
5:58 am	Puzzle o' the Day 153! Here's a terrific combinatorics puzzle. As usual, all that's needed on your part is some cleverness. Say you command 10 soldiers, all of whose heights are different. One day, you call them to attention, and they stand in a row. a. Show that, no matter how they line up, there will be a subsequence of four soldiers (not necessarily consecutive) such that the four soldiers will be ordered by height (either shortest to tallest, or tallest to shortest). E.g.: In the ordering 6482T19375, the subsequence 64-2-1 works. You *could* do this by exhaustion (examining all 10! = 3628800 orderings), but I suggest finding a cleverer approach. One-word hint (in white): Pigeonhole! Bigger hint (also in white): For soldier x, let a(x) be the length of the longest ascending chain that begins with that soldier and proceeds to the right; let d(x) be the length of the longest descending chain that begins with that soldier and proceeds to the right. Even bigger hint (also in white): Can two different soldiers have the same values for a and d? Now see hint one again. b. Easy-if-you've-gotten-this-far followup puzzle: Generalize your result for a row of n soldiers. c. Also pretty easy: Find an ordering of nine soldiers in which there is *no* monotonic subsequence of length four. Generalize this one too. (3 Comments |Comment on this)
Friday, April 25th, 2008
5:39 am	Puzzle o' the Day 152! We've had some tough ones lately. This one's somewhat easier. Also, it's fun (and easy) to experiment with. Good luck! Alice types the same sentence over and over. The sentence is less than one line long (including the standard two spaces after the period). She's using a fixed-width font. If a word (which includes any punctuation attached to its end) won't fit on what remains of a line, she simply hits return and begins the next line with that word. If the last character of a line is occupied by the last letter of a word, the next line does *not* start with a space -- each line begins with a word. She continues in this fashion until she comes to the end of the page. When she's done, will there be a completely white column (that is, a column consisting solely of spaces) on the page? Prove that there always will be, or come up with a counterexample. (5 Comments |Comment on this)
Thursday, April 24th, 2008
6:23 am	Puzzle o' the Day 151! Today: the Magic Hexagon! I'm surprised this one isn't better-known. This one's easy to explain: fill in the nineteen hexagons below with the numbers 1 through 19 (using each number exactly once) so that each of the fifteen rows (six of length three, six of length four, and three of length five) add up to 38. .................. ........__........ .....__/..\__..... ..__/..\__/..\__.. ./..\__/..\__/..\. .\__/..\__/..\__/. ./..\__/..\__/..\. .\__/..\__/..\__/. ./..\__/..\__/..\. .\__/..\__/..\__/. ....\__/..\__/.... .......\__/....... .................. (Amusing, possibly apocryphal anecdote: supposedly, one of the originators of this puzzle found the solution (which is unique, up to rotations and reflections), lost it, then took over *thirty years* to find it again. Hopefully it won't take you as long.) Hint to the central number in white: The central number is 5. By the way, if you haven't tried Puzzle o' the Day 150!, you really should. It's awesome. Hints have been added. (Comment on this)
Tuesday, April 22nd, 2008
8:40 am	Puzzle o' the Day 150! *1*5*0*!* I like to save especially good puzzles for round-numbered PotD's, and this is no exception -- it's the best puzzle I've seen in the past two years. I first saw it on hgfalling's blog, but it's been racing around math departments for awhile now. Apologies to those who've already seen it. Without further ado: The puzzle: There is a prison with 100 prisoners in it; each of them has a different name. There is a room in the prison with 100 numbered boxes in it; the prison guards write each prisoner's name on a slip of paper and put one slip in each box (in any order they like). One by one, each prisoner is led into the room. He can open up to 50 boxes. If he finds his name, he is sequestered in a different room, the box room is magically restored to its original condition, and the procedure begins again with the next prisoner. If *any* prisoner fails to find his name, *all* 100 are executed. The prisoners are allowed to plan before the procedure begins (but, of course, due to sequestration and magical restoration, cannot communicate once it starts). What strategy should they adopt in order to maximize the probability that they survive? What is that probability? (N.B.: there is no strategy that will guarantee the survival of all prisoners -- heck, since the *first* prisoner will only find his name half the time, the survival probability will be at most 50%. Most likely a fair bit less, you might think. Can you do better than the "random" strategy, which yields a (1/2)^100 chance of survival? Of course you can! You can do much, much better. How?) Hint in white: You can save the prisoners over 30% of the time! Seems unbelievable, but it's true. Now you have something to shoot for. Another hint in white: While the prisoners cannot communicate once the procedure has started, that doesn't mean their choices of which boxes to open have to be entirely pre-planned. (Why?) (20 Comments |Comment on this)
Wednesday, April 16th, 2008
3:01 pm	Ah, the irony PBS has been re-airing the 15-year old series "Jeeves and Wooster", starring Hugh Laurie as upper-class British twit Bertie Wooster, and Stephen Fry as his ultra-competent "gentleman's gentleman" Jeeves. It's an amusing series (seeing how it's derived from Wodehouse, it would be hard to be otherwise), but that's not why I'm writing about it. Some of the later episodes are set in America, but I'm fairly certain that most of the actors cast as Americans are British. Their American accents are *awful*. Distractingly awful. And in their midst, in full British twit mode, is Laurie, who's famous for doing a near-perfect American accent in his role as House. (For those of you who can detect Laurie's British accent when he's playing House, yeah, I can too. But I've had practice with my British-born father. He's lived in the US for 45 years, and, though it's possible to figure out his origins from his speech, you have to know what to listen for.) (4 Comments |Comment on this)
2:40 pm	Yeah, I'm a gullible idiot I kept thinking about that asteroid story as I fell asleep last night, wondering how a gazillion-ton asteroid could have its course changed even slightly by a satellite. Turns out the story was a complete fabrication. To steal my favorite Bill Simmons line: "The lesson, as always: I'm an idiot." (1 Comment |Comment on this)
12:59 pm	Today's candidate for the most frightening thing in the universe "My Beautiful Mommy"; didn't the Onion already do a parody of this?! (Comment on this)
Tuesday, April 15th, 2008
11:24 pm	Somebody sign this kid to a contract! This article fills me with several emotions: I'm impressed with the kid's accomplishment, worried that NASA missed it, and somewhat frightened at the 100-fold increase in the probability of a 2036 impact. (By the way, this would *not* be an extinction event; Apophis just ain't big enough. It would be a real bad day though.) (1 Comment |Comment on this)
11:10 am	Puzzle o' the Day 149! On our maps, we require countries whose borders share an edge (not merely a point) to be different colors. You've probably heard that any map on a plane (or a sphere) can be colored with four colors. That one's kinda hard to prove. But how about the torus? Map coloring is surprisingly simple there. Recall that we can consider a torus to be a square with the top edge glued to the bottom edge, and the left edge glued to the right edge. 1a. Split the torus into seven regions, each of which shares an edge with all six of the other regions. This shows that a map on a torus may require seven colors. 1b. Take your answer to 1a, and draw its "dual" -- that is, place a new point in each of your map's old regions, and connect two new points if the old regions shared an edge. Now erase your old points and edges. Now look again at the torus triangulation puzzle, PotD 146 . . . 2. Show that no map on the torus requires more than seven colors. If this weren't true, there would be an exception with a minimum number of regions; show that this leads to a contradiction. You'll need the fact that, on a torus, any graph satisfies V - E + F = 0. Further hints available on request. (3 Comments |Comment on this)
Monday, April 14th, 2008
12:44 pm	Puzzle o' the Day 148! It's Monday, so here's an easy one for y'all. Natasha wants to multiply, say, 73 by 137 (two numbers chosen entirely at random). She starts with 73, and repeatedly multiplies by 1/2 (discarding any remainder), until she reaches 1; she then doubles 137 the same number of times she went through the halving procedure, thereby creating the following table: 73...137 36...274 18...548 .9..1096 .4..2192 .2..4384 .1..8768 Now she adds the numbers in the right column that are opposite an odd number in the left column, obtaining: 137 + 1096 + 8768 = 10001. And yep, 73 times 137 = 10001 (yeah, *entirely* at random). Explain why this process works. (1 Comment |Comment on this)
Friday, April 11th, 2008
12:43 am	Puzzle o' the Day 147! Galois Theory is perhaps my favorite sub-branch of math; it's jaw-droppingly elegant, and several beautiful results fall out naturally. Here's a puzzle which will introduce you to the subject. Don't worry -- most of it is accessible to anyone who knows what a polynomial is. An algebraic number is a number x which is the root of a polynomial equation with rational coefficients. For example, x = sqrt(2) is an algebraic number, since it satisfies x^2 - 2 = 0. a. (Easy). Show that 1/sqrt(2) is also an algebraic number. b. (Easy). Show that, in general, if x is an algebraic number, so too is 1/x. c. (Still pretty easy). Show that sqrt(2) + sqrt(3) is an algebraic number, by finding a polynomial with rational coefficients for which it is a root. d. (Somewhat harder, but you can do it!). Show that if x and y are algebraic numbers, so too is x + y. This one requires a smidgen of linear algebra. Hint: don't try to construct the polynomial which has x + y as a root -- just show that it must exist. By the way, the results of b. and d. suffice to show that the algebraic numbers form a field. (By the way, no one's solved PotD 146 -- the "triangulate the torus" puzzle -- though people are getting closer. Believe it or not, the answer is important in combinatorics and graph theory.) (3 Comments |Comment on this)