From: Dodsonzoo@aol.com Date: Thu, 25 Feb 1999 23:20:18 EST To: rusin@math.niu.edu Subject: Hi! Was looking over your web page - impressive!!!! You don't know me from Adam but you may be able to help. Taking a college course on elementary math teaching and stuck on my home project. Have you ever heard of the game "Hot Fat Tune?" There are nine cards with words to be cut out: ROPE FAT TUNE PAIN CUP SONG SALE BUS HOT This is a game for two players Take turns to remove any one of the nine cards - they are placed up The first player to hold three cards which contain the same letter is the winner. There is one right move that will guarantee a win every time. Well - after 5 days - I give up!!!!!!!! Don't suppose you have any suggestions? Thanks for any help you can give. My name is Sue ============================================================================== From: Dave Rusin Date: Thu, 25 Feb 1999 23:12:22 -0600 (CST) To: Dodsonzoo@aol.com Subject: Re: Hi! Well, there are only 9!=360thousand sequences of ways to order the 9 cards. You could easily run them all through a machine to see who wins each time. Look up "alpha-beta pruning" in a computer science text to find out how to deduce a strategy from this complete game tree. I'm glad you found the site of interest. Watch for further changes later this year. I intend to move to the much snappier URL "www.mathmap.com/welcome.html" dave ============================================================================== From: Dave Rusin Date: Fri, 26 Feb 1999 00:19:45 -0600 (CST) To: Dodsonzoo@aol.com Subject: Re: Hi! Actually I think there is no winning move (although I didn't prove it). Is it possible your instructor meant to include SOAP too? dave ============================================================================== From: Dodsonzoo@aol.com Date: Fri, 26 Feb 1999 08:53:49 EST To: rusin@math.niu.edu Subject: Re: Hi! A truly smart man would not just blurt out the answer. Will check out alpha- beta pruning! Thank you for your help! I will watch for your new site! Sue ============================================================================== [I think I had by this time found it _was_ possible to win, and suggested locating the most important word as the opening move -- importance measured by the preponderance of "important" letters.] ============================================================================== From: Dodsonzoo@aol.com Date: Fri, 26 Feb 1999 15:53:29 EST To: Rusin@math.niu.edu Subject: Hello again Hi Dave! Ok - researched alpha-beta pruning. Could I have another hint please? Still not sure where I am going with it. Thanks. Sue ============================================================================== [My response lost] ============================================================================== From: Dodsonzoo@aol.com Date: Fri, 26 Feb 1999 18:55:17 EST To: rusin@math.niu.edu Subject: ?? Okay - thanks again! Going to start writing this tree down. Curious though - you said it was not too big to check by machine? Don't know exactly what you mean. ============================================================================== [Suggested a recursive program I had used with Maple and outlined the proc's. test1: given hands (A,B) assign a value of +1 if A can win, -1 if B has won, otherwise give it value equal to max(test2(A union {c}, B)). test2: given hands (A,B) assign a value of +1 if A has won, -1 if B can win, otherwise give it value equal to min(test1(A, B union {c})). Here the first player wants hands with positive value, the second wants negative value.] ============================================================================== From: Dodsonzoo@aol.com Date: Fri, 26 Feb 1999 19:55:23 EST To: rusin@math.niu.edu Subject: Re: ?? I give up! You have been very patient and I appreciate it. I am going to be an elementary teacher - not a computer programmer! Tell me one elementary child out there who is going to figure this out - then again, 4 years from now, who knows!!!! I followed your tree theory. Tune is the most important word. When Tune is played first, there is an easy win when followed by Bus, Cup, Fat, and Hot. That was as far as I could go. No 4-letter words (and I can think of a few left out) would produce an automatic win if Tune was played. At this point, I would not be offended if you wanted to tell me the answer - because I am going crazy here!!!! Thanks Sue ============================================================================== From: Dave Rusin Date: Sat, 27 Feb 1999 00:24:20 -0600 (CST) To: Dodsonzoo@aol.com Subject: Re: ?? Yes, begin with TUNE, and you can play to a sure win. You'll have to excuse me, I don't have the original problem here at hand, so I'll have to reproduce this from memory. There are 9 words, using a total of 16 letters. We observe that the letters {TUNESOAP} show up in 3 words each, and the other letters show up in only one word each. In particular, you can only win by holding three T's, three U's, ..., or three P's -- you might as well ignore the other letters. SONG could just as well be SON or SONZ or SONQ. Now that you have the letters ranked, look at the words. TUNE is made of four useful letters. SONG has only three, as do three other words which I can't recall but they involved PAN, POE, and SAE. The other four words involved only two good letters; they were essentially US, UP, TO, TA. So I see three grades of words. Now look at the letters _again_! TUNE uses only the letters {T,U,N,E}, of course. The words in the second tier each use exactly two of those letters and one of {S,O,P,A}. The remaining words use just one of each set. So we segregate the eight letters into these two classes. OK! So we have organized our data a little. The nine cards are effectively C1 N E U T C2 N S O C3 E O P C4 N P A C5 E S A C6 U S C7 T O C8 U P C9 T A I hope you can see some regularity in the table here. Everything I've done so far is just to organize the data to take advantage of symmetry in a maximal way. Someone was rather clever to create a problem with this much symmetry; this is what enables us to do the problem by hand rather than have to search blindly for all the options, although really there's no reason that one can't set up a game tree as I described earlier and let a machine do the grunt work -- 9! sequences is trivial for today's machines. OK, so we simply look for the smartest way to choose cards from the set {C1, C2, C3, C4, C5, C6, C7, C8, C9}. The goal is to be the first to collect a set which contains one of the winning subsets. You win by holding 3 N's, ..., 3 A's -- that is, by holding one of these eight subsets: S1: {C1, C2, C4} S2: {C1, C3, C5} S3: {C1, C6, C8} S4: {C1, C7, C9} S5: {C2, C5, C6} S6: {C2, C3, C7} S7: {C3, C4, C8} S8: {C4, C5, C9} The first player chooses card C1, and responds to the second player's opening move as follows: Game Player P2's move Response by player P1 G1 C2 C9 G2 C3 C6 G3 C4 C7 G4 C5 C8 G5 C6 C4 G6 C7 C5 G7 C8 C2 G8 C9 C3 I had to get the response to player P2's first move "take card C2" by some experimentation. The solution I found is not unique (I think). Below, I'll outline what happens next in game G1. Any of the next three games G2, G3, G4 on the table are then obtained by relying on the symmetry (I hope you see the pattern). I then tried to get a response to "take card 6" (game G5) in a similar way; you'll see that below, too -- it's pretty similar to game G1. Then again I rely on symmetry to tell me how to respond to the remaining games. I don't want to sound like a broken record here, but in principle you can handle any opening move by player P2 by examining a game tree, but the remarkable symmetry among card groups {C2, C3, C4, C5} and {C6, C7, C8, C9} allows me to do this by hand in just a couple of cases and rest assured that any other case will be nearly identical by rotating through the two four-card groups cyclically. Think mod 4 or something as you read the table if it helps. OK, so let's see how the game goes if the card selections are, in order, C1-C2-C9 as in game G1 in that last table. Player P2 has to respond by choosing card C7; otherwise, Player P1 will select it on the next turn, and have C1-C9-C7, a winning hand (S4). If player P2 messes up, player P1 chooses card C7 next and wins. If player P2 does play "right", then a winning move by player P1 would be to choose card C5. For then, player P2 is stuck. S/he must choose card C3 next, for if not, then player P1 can choose it on the next turn, having cards C1-C9-C5-C3, which contains set S2 and so is a win for player P1. But even if player P2 does play "right" again, and chooses card C3 to forestall _this_ defeat, player P1 can select card C4 and have hand C1-C9-C5-C4 which now contains set S8 and so is again a win for player P1. So even if player P2 is optimally clever, player P1 has forced the game sequence to be C1-C2-C9-C7-C5-C3-C4, that is, the players hold cards {C1, C9, C5, C4} and {C2, C7, C3} respectively. You should really work through this paragraph on scap paper right next to the table of winning hands S1 through S8. Just to verify the symmetry here, let's run though game G2. I just shift cyclically through card sets {C2,C3,C4,C5} and {C6,C7,C8,C9} from the previous paragraph. Player P1 chooses card C1, P2 chooses card C3, P1 chooses card C6 to begin game G3. Player P2 has to respond with card C8 to prevent P1's win with C1-C6-C8. Player P1 then should choose card C2. For then P2 must select card C4 to prevent player P1 from having C1-C6-C2-C4 which wins. But even if player P2 plays right, player P1 responds by choosing card C5, and so has hand C1-C6-C2-C5, which wins. Games G3 and G4 will be similar. Perhaps you can see what happens in a sort of a general way: player P2's first move blocks out two of the last four wins for P1, but player P1 takes the next move in such a way that P2's forced response (trying to block a win from among S1 S2 S3 S4) does not reduce the set of winning hands still available for P1 from among the last four wins (S5, S6, S7, S8). So player P1 can choose a third card which is a setup: P1 is primed for one win from among S1, S2, S3, S4 (which P2 has to block) and also for one win from among S5, S6, S7, S8. Now I'll show that games G5-G8 will operate on a similar principle. As before I only really had to analyze G5 in some detail; G6 G7 G8 will follow essentially identically by permuting cards {C2, C3, C4, C5} and {C6, C7, C8, C9} cyclically. Ready? P1 chooses card C1; P2 chooses card C5; P1 responds with card C4. Player P2 must then respond with card C2 to prevent winning hand S1. Player P1 can choose card C8; Player P2 must then respond with card C6 to prevent winning hand S3, but the player P1 can select card C3 and win with hand S7. This time I'll leave it to you to investigate the last three cases. For example, in game G6 we expect the game to run C1-C6-C5-C3-C9-C7-C4. So no matter which opening move player P2 chooses, player P1 more or less forces the games to run along the sequences shown for the eight games G1, ..., G8. If P2 follows the script, P1 wins after 7 cards have been played. If P2 ever messes up, P1 can win on the very next move. Exercises for further contemplation: 1. If player P1 fails to open with move C1 can P2 then force a win? 2. What if we add a card which reads "SOAP"? I rather enjoyed this game analysis. As you can see from the paragraph describing game G2, it isn't all that hard of a game to analyze but not immediately trivial either. But what's really nice about it, to a mathematician, is the amount of symmetry in the overall game. There is a branch of mathematics called Game Theory, which is really more a question of optimization and economics, but which includes a small branch called combinatorial game theory, in which one does this kind of analysis. I mentioned the alpha-beta pruning of game trees in a previous letter; this is a common technique studied in computer science (recursive programs). Exactly what kind of mathematics is useful for the analysis of a particular combinatorial game varies from game to game. In this case we have a sort of combinatorial geometry; we're looking for "minimal spanning sets" containing "cliques" in a graph, perhaps. There may be some more general structure into which this game would fall; I'm not an expert in combinatorics. For more information, see e.g. Game theory: http://www.math.niu.edu/~rusin/known-math/index/90-XX.html Combinatorics: http://www.math.niu.edu/~rusin/known-math/index/05-XX.html Computer Science: http://www.math.niu.edu/~rusin/known-math/index/68-XX.html You've been a good sport to work on the problem on your own. I hope this analysis is helpful without taking all the fun away. Of course I assume that if this is for a graded class that you will fess up to having had some assistance. Good luck with your game playing! dave ============================================================================== Sample set: TUNE PAIN COPE SAVE SNOW TALK FORT BUSH JUMP ============================================================================== From: Dodsonzoo@aol.com Date: Sat, 27 Feb 1999 10:26:56 EST To: rusin@math.niu.edu Subject: Re: ?? Going to study your explanation and give it a try - thanks!!!!! Of course at this point I am going for the "effort" points. I do think I should get credit for soliciting someone else's help! I hope you don't mind If I submit some of your letters with it - let me know if that is a problem. Bet you will get a lot of "hits" to your website. Have to tell you something I noticed last night. Stopped working on the "hot fat tune" game and did my book work. Had a very hard time with one problem and when I finally did get it - noticed it reminded me of this game I was trying to solve. This was the problem: You had to use the numbers 1-9 to fill in all the squares. Started by listing each number and what other numbers added up to that number. Some numbers only had two possibilities, some three and some four, etc. Was able to solve this - mainly by trial and error - but I couldnt help thinking it was along the same line as the hot fat tune game. Anyway, so you don't think I am totally worthless, there are many parts to this math assignment project. The game I showed you was just one of the worksheets I couldnt figure out. Was able to do the "frogs leaping over other frogs" and how to figure out with "n" amount of frogs. Had to figured out the "nim" game - did that too! So - thank you - thank you for your help! Will try this later. Sue