Archive-name: puzzles/archive/competition/part1 Last-modified: 17 Aug 1993 Version: 4 ==> competition/contests/games.magazine.p <== What are the best answers to various contests run by _Games_ magazine? ==> competition/contests/games.magazine.s <== Contest Date Archive Entry ---------------------- -------------- ----------------------------- Equations ? 1981 equations National Puzzle 1993 1993 npc.1993 Nots and Crosses ? 1992 nots.and.crosses Perfect Ladder July 1993 perfect.ladder Telegrams ? telegrams ==> competition/contests/national.puzzle/npc.1993.p <== What are the solutions to the Games magazine 1993 National Puzzle Contest? ==> competition/contests/national.puzzle/npc.1993.s <== 1. 6, 10, 11, and 12 are in one group, and everything else is in the other. 2. 20 3. The upper-right segment of the first 8. 4. 6 5. d (ball point pen, analog watch, mattress, pogo stick): springs 6. a (Fire Engine, strawberry, lobster, lips): red 7. h (Icicle, paint, nose, faucet): drip 8. f (piggy bank, basketball, jack o' lantern, drum): hollow 9. g (horseshoe, goal post, stethoscope, fish hook): shaped like letters 10. e (flying bat, Xmas tree ornament, framed picture, trapeze artist): hang 11. b (candle, owl, vampire, pajamas): all associated with night 12. 4, 7, 2, 10, 5, 8, 1, 9, 6, 3 13. 152954 14. LIMA PERU 15. 44 16. 160 17. A 18. Flo Lisa Amy Joyce Kim. 19. Top: AJKQ, 2nd Row: JKAQ, 3rd Row: KQAJ, 4th Row: JQAK 20. Joan Miro, Paavo Nurmi, Blaise Pascal 21. Top: 1, 8, 4 Middle: 6, 9, 3 Bottom: 2, 7, 5 22. d and g 23. Brenda: 87, Carrie: 85, Dick: 86, Harry: 84, Laura: 88, Tom: 83 24. If you number the columns 1-6 and letter the rows a-f, the first group consists of 1a, 2a, 3a, 4a, 1b, 2b, 2c, 3c, 2d. Other groups are similarly shaped, rotated around the center point of the grid. 25. 2, 6, 5 26. Top: R O M Middle: Q T A Bottom: U E D S 27. 3 X 58 = 174 = 6 X 29 28. 5 (the number of enclosed areas in the letters of each month name) 29. too hard to describe -- easier than it looked 30. 80 31. 16 32. 4 (ADBECF ADBFCE ADFCBE BFDCAE) 33. 8 (delete 3,5,7,9,12,14,17,18) 34. CONKP VALEY GSRCW TUIBI LANZS ==> competition/games/bridge.p <== Are there any programs for solving double-dummy Bridge? ==> competition/games/bridge.s <== I'll enclose my Double-Dummy solver for bridge. I like this program because it contains a wildly unstructured "goto" -- which I claim is the most readable way to write the program. Included are two test problems for the bridge-solver: a 6-card ending and a complete 13-card position. The former should be very fast; the latter about 20 minutes on Sparcstation-2. Each is *very* challenging for humans. Regards, James =============== clip; chmod +x; execute ============= #!/bin/sh cat > bridge.c << 'EOF' /* * DOUBLE_DUMMY * Copyright (c) 1990 by * James D. Allen * 19785 Stanton Ave * Castro Valley, CA * Permission granted to use for any non-commercial purpose * as long as this notice is not removed. * * This program will solve double-dummy bridge problems. * The algorithm is trivial: brute-force alpha-beta search (also known * as "backtracking"). The alpha-beta is trivial since we do not * consider overtricks or extra undertricks. * The control flow is neat; this is a rare exception where software is * more readable with a "goto". (Although I've tersified this to * the point where it is perhaps unreadable anyway :-) */ #define NUMP 4 /* The Players: N, E, S, W */ #define NORTH 0 #define IS_CONT(x) (!((x) & 1)) /* Is x on N/S team? */ #define LHO(x) (((x) + 1) % NUMP) #define RHO(x) (((x) + NUMP - 1) % NUMP) char *Playername[] = { "North", "East", "South", "West" }; #define NUMS 4 /* The Suits: S, H, D, C */ char Suitname[] = "SHDC"; char *Fullname[] = { "Spades\t", "Hearts\t", "Diamonds", "Clubs\t" }; /* * Rank indices are 2 (Ace), 3 (King), ... 14 (Deuce) * There is also a CARD Index which can be converted to from Rank and Suit. */ #define CARD(Suit, Rank) (((Suit) << 4) | (Rank)) #define SUIT(Card) ((Card) >> 4) #define RANK(Card) ((Card) & 0xf) char Rankname[] = "??AKQJT98765432"; #define INDEX(s, c) ((char *)index(s, c) - (s)) /* A "SuitSet" is used to cope with more than one card at once: */ typedef unsigned short SuitSet; #define MASK(Card) (1 << RANK(Card)) #define REMOVE(Set, Card) ((Set) &= ~(MASK(Card))) /* And a CardSet copes with one SuitSet for each suit: */ typedef struct cards { SuitSet cc[NUMS]; } CardSet; /* Everything we wish to remember about a trick: */ struct status { CardSet st_hold[NUMP]; /* The players' holdings */ CardSet st_lgl[NUMP]; /* The players' remaining legal plays */ short st_play[NUMP]; /* What the players played */ SuitSet st_trick; /* Led-suit Cards eligible to win trick */ SuitSet st_trump; /* Trump Cards eligible to win trick */ short st_leader; /* Who led to the trick */ short st_suitled; /* Which suit was led */ } Status[14]; /* Status of 13 tricks and a red zone" */ #define Hold Statp->st_hold #define Resid (Statp+1)->st_hold #define Lgl Statp->st_lgl #define Play Statp->st_play #define Trick Statp->st_trick #define Trtrick Statp->st_trump #define Leader Statp->st_leader #define Suitled Statp->st_suitled /* Pick a card from the set and return its index */ pick(set) SuitSet set; { return set & 0xff ? set & 1 ? 0 : set & 2 ? 1 : set & 4 ? 2 : set & 8 ? 3 : set & 16 ? 4 : set & 32 ? 5 : set & 64 ? 6 : 7 : pick(set >> 8) + 8; } #define highcard(set) pick(set) /* Pick happens to return the best card */ main() { register struct status *Statp = Status; /* Point to current status */ int tnum; /* trick number */ int won; /* Total tricks won by North/South */ int nc; /* cards on trick */ int ohsize; /* original size of hands */ int mask; int trump; int player; /* player */ int pwin; /* player who won trick */ int suit; /* suit to play */ int wincard; /* card which won the trick */ int need; /* Total tricks needed by North/South */ int cardx; /* Index of a card under consideration */ int success; /* Was the trick or contract won by North/South ? */ int last_t; /* Decisive trick number */ char asciicard[60]; SuitSet inplay; /* cards still in play for suit */ SuitSet pr_set; /* Temp for printing */ /* Read in the problem */ printf("Enter trump suit (0-S,1-H,2-D,3-C,4-NT): "); scanf("%d", &trump); printf("Enter how many tricks remain to be played: "); scanf("%d", &ohsize); printf("Enter how many tricks North/South need to win: "); scanf("%d", &need); printf("Enter who is on lead now (0=North,etc.): "); scanf("%d", &pwin); printf("Enter the %d cards beginning with North:\n", NUMP * ohsize); for (player = NORTH; player < NUMP; player++) { for (tnum = 0; tnum < ohsize; tnum++) { scanf("%s", asciicard); cardx = CARD(INDEX(Suitname, asciicard[1]), INDEX(Rankname, asciicard[0])); Hold[player].cc[SUIT(cardx)] |= MASK(cardx); } } /* Handle the opening lead */ printf("Enter the directed opening lead or XX if none:\n"); Lgl[pwin] = Hold[pwin]; scanf("%s", asciicard); if (asciicard[0] == 'X') { strcpy(asciicard, "anything"); } else { cardx = CARD(INDEX(Suitname, asciicard[1]), INDEX(Rankname, asciicard[0])); for (suit = 0; suit < NUMS; suit++) if (suit != SUIT(cardx)) Lgl[pwin].cc[suit] = 0; else if (!(Lgl[pwin].cc[suit] &= MASK(cardx))) { printf("He can't lead card he doesn't have\n"); exit(1); } } /* Print the problem */ for (player = NORTH; player < NUMP; player++) { printf("\n---- %s Hand ----:\n", Playername[player]); for (suit = 0; suit < NUMS; suit++) { printf("\t%s\t", Fullname[suit]); for (pr_set = Hold[player].cc[suit]; pr_set; REMOVE(pr_set, pick(pr_set))) printf("%c ", Rankname[RANK(pick(pr_set))]); printf("\n"); } } printf("\n%s%s Trumps; %s leads %s; N-S want %d tricks; E-W want %d\n", trump < NUMS ? Fullname[trump] : "", trump < NUMS ? " are" : "No", Playername[pwin], asciicard, need, ohsize + 1 - need); /* Loop to play tricks forward until the outcome is conclusive */ for (tnum = won = success = 0; success ? ++won < need : won + ohsize >= need + tnum; tnum++, Statp++, success = IS_CONT(pwin)) { for (nc = 0, player = Leader = pwin; nc < NUMP; nc++, player = LHO(player)) { /* Generate legal plays except opening lead */ if (nc || tnum) Lgl[player] = Hold[player]; /* Must follow suit unless void */ if (nc && Lgl[player].cc[Suitled]) for (suit = 0; suit < NUMS; suit++) if (suit != Suitled) Lgl[player].cc[suit] = 0; goto choose_suit; /* this goto is easily eliminated */ /* Comes back right away after choosing "suit" */ make_play: Play[player] = cardx = CARD(suit, pick(Lgl[player].cc[suit])); if (nc == 0) { Suitled = suit; Trick = Trtrick = 0; } /* Set the play into "Trick" if it is win-eligible */ if (suit == Suitled) Trick |= MASK(cardx); if (suit == trump) Trtrick |= MASK(cardx); /* Remove card played from player's holding */ Resid[player] = Hold[player]; REMOVE(Resid[player].cc[suit], cardx); } /* Finish processing the trick ... who won? */ if (Trtrick) wincard = CARD(trump, highcard(Trtrick)); else wincard = CARD(Suitled, highcard(Trick)); for (pwin = 0; Play[pwin] != wincard; pwin++) ; } /* Loop to back up and let the players try alternatives */ for (last_t = tnum--, Statp--; tnum >= 0; tnum--, Statp--) { won -= IS_CONT(pwin); pwin = Leader; for (player = RHO(Leader), nc = NUMP-1; nc >= 0; player = RHO(player), nc--) { /* What was the play? */ cardx = Play[player]; suit = SUIT(cardx); /* Retract the played card */ if (suit == Suitled) REMOVE(Trick, cardx); if (suit == trump) REMOVE(Trtrick, cardx); /* We also want to remove any redundant adjacent plays */ inplay = Hold[0].cc[suit] | Hold[1].cc[suit] | Hold[2].cc[suit] | Hold[3].cc[suit]; for (mask = MASK(cardx); mask <= 0x8000; mask <<= 1) if (Lgl[player].cc[suit] & mask) Lgl[player].cc[suit] &= ~mask; else if (inplay & mask) break; /* If the card was played by a loser, try again */ if (success ? !(IS_CONT(player)) : IS_CONT(player)) { choose_suit: /* Pick a suit if any untried plays remain */ for (suit = 0; suit < NUMS; suit++) if (Lgl[player].cc[suit]) /* This goto is really nice!! * / goto make_play; } } } /* * We're done. We know the answer. * We can't remember all the variations; fortunately the * succeeders played correctly in the last variation examined, * so we'll just print it. */ printf("Contract %s, for example:\n", success ? "made" : "defeated"); for (tnum = 0, Statp = Status; tnum < last_t; tnum++, Statp++) { printf("Trick %d:", tnum + 1); for (player = 0; player < Leader; player++) printf("\t"); for (nc = 0; nc < NUMP; nc++, player = LHO(player)) printf("\t%c of %c", Rankname[RANK(Play[player])], Suitname[SUIT(Play[player])]); printf("\n"); } return 0; } EOF cc -O -o bridge bridge.c bridge << EOF 4 6 5 2 AS JS 4S QD 8D 2C KS QS 9H 8H AD 2D AH 2H KD 9D 7D AC TS 3S 2S TH TD TC XX EOF bridge << EOF 1 13 13 3 3C 3H 2H AD KD 2D AS KS 7S 6S 5S 4S 3S 8C 7C 6C 5C 4C QH TH 8H 7H 8D 7D 6D 2S AC QC JC 9C AH KH JH 9H 6H 5H 5D 4D 3D KC TC 2C 4H QD JD TD 9D QS JS TS 9S 8S QS EOF ==> competition/games/chess/knight.control.p <== How many knights does it take to attack or control the board? ==> competition/games/chess/knight.control.s <== Fourteen knights are required to attack every square: 1 2 3 4 5 6 7 8 ___ ___ ___ ___ ___ ___ ___ ___ h | | | | | | | | | --- --- --- --- --- --- --- --- g | | | N | N | N | N | | | --- --- --- --- --- --- --- --- f | | | | | | | | | --- --- --- --- --- --- --- --- e | | N | N | | | N | N | | --- --- --- --- --- --- --- --- d | | | | | | | | | --- --- --- --- --- --- --- --- c | | N | N | N | N | N | N | | --- --- --- --- --- --- --- --- b | | | | | | | | | --- --- --- --- --- --- --- --- a | | | | | | | | | --- --- --- --- --- --- --- --- Three knights are needed to attack h1, g2, and a8; two more for b1, a2, and b3, and another two for h7, g8, and f7. The only alternative pattern is: 1 2 3 4 5 6 7 8 ___ ___ ___ ___ ___ ___ ___ ___ h | | | | | | | | | --- --- --- --- --- --- --- --- g | | | N | | | N | | | --- --- --- --- --- --- --- --- f | | | N | N | N | N | | | --- --- --- --- --- --- --- --- e | | | | | | | | | --- --- --- --- --- --- --- --- d | | | N | N | N | N | | | --- --- --- --- --- --- --- --- c | | N | N | | | N | N | | --- --- --- --- --- --- --- --- b | | | | | | | | | --- --- --- --- --- --- --- --- a | | | | | | | | | --- --- --- --- --- --- --- --- Twelve knights are needed to control (attack or occupy) the board: 1 2 3 4 5 6 7 8 ___ ___ ___ ___ ___ ___ ___ ___ a | | | | | | | | | --- --- --- --- --- --- --- --- b | | | N | | | | | | --- --- --- --- --- --- --- --- c | | | N | N | | N | N | | --- --- --- --- --- --- --- --- d | | | | | | N | | | --- --- --- --- --- --- --- --- e | | | N | | | | | | --- --- --- --- --- --- --- --- f | | N | N | | N | N | | | --- --- --- --- --- --- --- --- g | | | | | | N | | | --- --- --- --- --- --- --- --- h | | | | | | | | | --- --- --- --- --- --- --- --- Each knight can control at most one of the twelve squares a1, b1, b2, h1, g1, g2, a8, b8, b7, h8, g8, g7. This position is unique up to reflection. References Martin Gardner, _Mathematical Magic Show_. ==> competition/games/chess/knight.most.p <== What is the maximum number of knights that can be put on n x n chessboard without threatening each other? ==> competition/games/chess/knight.most.s <== n^2/2 for n even >= 4. Divide the board in parts of 2x4 squares. The squares within each part are paired as follows: ----- |A|B| ----- |C|D| ----- |B|A| ----- |D|C| ----- Clearly, not more than one square per pair can be occupied by a knight. ==> competition/games/chess/knight.tour.p <== For what size boards are knight tours possible? ==> competition/games/chess/knight.tour.s <== A tour exists for boards of size 1x1, 3x4, 3xN with N >= 7, 4xN with N >= 5, and MxN with N >= M >= 5. In other words, for all rectangles except 1xN (excluding the trivial 1x1), 2xN, 3x3, 3x5, 3x6, 4x4. With the exception of 3x8 and 4xN, any even-sized board which allows a tour will also allow a closed (reentrant) tour. On an odd-sided board, there is one more square of one color than of the other. Every time a knight moves, it moves to a square of the other color than the one it is on. Therefore, on an odd-sided board, it must end the last move but one of the complete, reentrant tour on a square of the same color as that on which it started. It is then impossible to make the last move, for that move would end on a square of the same color as it begins on. Here is a solution for the 7x7 board (which is not reentrant). ------------------------------------ | 17 | 6 | 33 | 42 | 15 | 4 | 25 | ------------------------------------ | 32 | 47 | 16 | 5 | 26 | 35 | 14 | ------------------------------------ | 7 | 18 | 43 | 34 | 41 | 24 | 3 | ------------------------------------ | 46 | 31 | 48 | 27 | 44 | 13 | 36 | ------------------------------------ | 19 | 8 | 45 | 40 | 49 | 2 | 23 | ------------------------------------ | 30 | 39 | 10 | 21 | 28 | 37 | 12 | ------------------------------------ | 9 | 20 | 29 | 38 | 11 | 22 | 1 | ------------------------------------ Here is a solution for the 5x5 board (which is not reentrant). -------------------------- | 5 | 10 | 15 | 20 | 3 | -------------------------- | 16 | 21 | 4 | 9 | 14 | -------------------------- | 11 | 6 | 25 | 2 | 19 | -------------------------- | 22 | 17 | 8 | 13 | 24 | -------------------------- | 7 | 12 | 23 | 18 | 1 | -------------------------- Here is a reentrant 2x4x4 tour: 0 11 16 3 15 4 1 22 19 26 9 24 8 23 14 27 10 5 30 17 31 12 21 2 29 18 25 6 20 7 28 13 A reentrant 4x4x4 tour can be constructed by splicing two copies. It shouldn't be much more work now to completely solve the problem of which 3D rectangular boards allow tours. Warnsdorff's rule: at each stage of the knight's tour, choose the square with the fewest remaining exits: 1 12 23 44 3 14 25 22 43 2 13 24 35 4 11 28 45 40 47 26 15 42 21 48 27 34 5 36 29 10 41 46 39 16 33 20 49 8 31 18 37 6 9 30 19 38 7 32 17 Mr. Beverley published in the Philosophical Magazine in 1848 this knight's tour that is also a magic square: 1 30 47 52 5 28 43 54 48 51 2 29 44 53 6 27 31 46 49 4 25 8 55 42 50 3 32 45 56 41 26 7 33 62 15 20 9 24 39 58 16 19 34 61 40 57 10 23 63 14 17 36 21 12 59 38 18 35 64 13 60 37 22 11 ~References: ``The Construction of Magic Knight Tours,'' by T. H. Willcocks, J. Rec. Math. 1:225-233 (1968). "Games Ancient and Oriental and How to Play Them" by Edward Falkener published by Dover in 1961 (first published 1892) "Mathematical Magic Show", Martin Gardner, ch. 14 ==> competition/games/chess/mutual.stalemate.p <== What's the minimal number of pieces in a legal mutual stalemate? ==> competition/games/chess/mutual.stalemate.s <== 6. Here are three mutual stalemate positions. Black is lower case in the diagrams. W Kh8 e6 f7 h7 B Kf8 e7 --+--+--+--+--+ | | k| | K| --+--+--+--+--+ | p| P| | P| --+--+--+--+--+ | P| | | | --+--+--+--+--+ | | | | | W Kb1 B Ka3 b2 b3 b4 a4 | | | +--+--+-- | p| p| +--+--+-- | k| p| +--+--+-- | | p| +--+--+-- | | K| +--+--+-- W Kf1 B Kh1 Bg1 f2 f3 h2 | | | | --+--+--+--+ | p| | | --+--+--+--+ | p| | p| --+--+--+--+ | K| b| k| --+--+--+--+ ==> competition/games/chess/queen.control.p <== How many queens does it take to attack or control the board? ==> competition/games/chess/queen.control.s <== Five queens are required to attack every square: 1 2 3 4 5 6 7 8 ___ ___ ___ ___ ___ ___ ___ ___ h | | | | | | | | | --- --- --- --- --- --- --- --- g | | | | Q | | | | | --- --- --- --- --- --- --- --- f | | | | Q | | | | | --- --- --- --- --- --- --- --- e | | | | Q | | | | | --- --- --- --- --- --- --- --- d | | | | Q | | | | | --- --- --- --- --- --- --- --- c | | | | | | | | | --- --- --- --- --- --- --- --- b | | | | | | | | | --- --- --- --- --- --- --- --- a | | | | Q | | | | | --- --- --- --- --- --- --- --- There are other positions with five queens. ==> competition/games/chess/queen.most.p <== How many non-mutually-attacking queens can be placed on various sized boards? ==> competition/games/chess/queen.most.s <== On an regular chess board, at most eight queens of one color can be placed so that there are no mutual attacks. Here is one configuration: ----------------- |Q| | | | | | | | ----------------- | | |Q| | | | | | ----------------- | | | | |Q| | | | ----------------- | | | | | | |Q| | ----------------- | |Q| | | | | | | ----------------- | | | | | | | |Q| ----------------- | | | | | |Q| | | ----------------- | | | |Q| | | | | ----------------- On an nxn board, if n is not divisible by 2 or 3, n^2 queens can be placed such that no two queens of the same color attack each other. The proof is via a straightforward construction. For n=1, the result is obviously true, so assume n>1 and n is not divisible by 2 or 3 (thus n>=5). Assume we are given n queens in each of these n "colors" (numbers): 0 1 2 ... n-1 The proof is by construction. The construction is easier to see then to describe, we do both. Here is what it looks like: 0 1 2 3 4 ... n-2 n-1 n-2 n-1 0 1 2 ... n-4 n-3 n-4 n-3 n-2 n-1 0 ... n-6 n-5 ...(move one row down => sub 2 (mod n); one col right => add 1 (mod n)) 2 3 4 5 6 ... 0 1 People who know how a knight moves in chess will note the repetitive knight move theme connecting queens of the same color (especially after joining opposite edges of the board). Now to describe this: place in each cell a queen whose "color" (number) is: j - 2*i + 1 (mod n), where i is the # of the row, and j is the # of the column. Then no 2 queens of the same color are in the same: row, column, or diagonal. Actually, we will prove something stronger, namely that no 2 queens of the same color are on the same row, column, or "hyperdiagonal". (The concept, if not the term, hyperdiagonal, goes back to 19th century.) There are n hyperdiagonals of negative slope (one of them being a main diagonal) and n hyperdiagonals of positive slope (one of them being the other main diagonal). Definition: for k in 0..n-1: the k-th negative hyperdiagonal consists of cells (i,j), where i-j=k (mod n) the k-th positive hyperdiagonal consists of cells (i,j), where i+j=k (mod n) Then 0-th negative hyperdiagonal is simply the NW-SE main diagonal. Then "1-th" positive hyperdiagonal is simply the SW-NE main diagonal. The other 2*(n-1) hyperdiagonals appear as 2 disconnected diagonal fragments of cells, but if you join opposite edges of an nxn board to each other, forming a sphere, these 2 fragments become linearly connected forming a great circle. Now to the proof: 1) First note that the above color assignment does indeed uniquely define the color of a queen in each of the n^2 cells. 2) no row contains 2 queens of the same color: cells (i, a) and (i, b) contain queens of the same color => a-2i-1 = b-2i-1 (mod n) => a = b (mod n) => a = b (since a,b are within 1..n) 3) no column contains 2 queens of the same color: cells (a, j) and (b, j) contain queens of the same color => j-2a-1 = j-2b-1 (mod n) => 2a = 2b (mod n) => a = b (mod n) (since n and 2 have no common factor) => a = b (since a,b are within 1..n) 4) no negative hyperdiagonal contains 2 queens of the same color: cells (a, j) and (b, k) on the same negative hyperdiagonal contain queens of the same color => a-j = b-k (mod n) AND j-2a-1 = k-2b-1 (mod n) => 2a-2j = 2b-2k (mod n) AND j-2a = k-2b (mod n) => (adding corresponding sides:) -j = -k (mod n) => j = k. And thus a = b, as well (see first equality, 5th line up) 5) no positive hyperdiagonal contains 2 queens of the same color: cells (a, j) and (b, k) on the same positive hyperdiagonal contain queens of the same color => a+j = b+k (mod n) AND j-2a-1 = k-2b-1 (mod n) => 2a+2j = 2b+2k (mod n) AND j-2a = k-2b (mod n) => (adding corresponding sides:) 3j = 3k (mod n) => j = k (mod n) (since n and 3 have no common factor) => j = k. Likewise a = b. As special cases with the 0th negative hyperdiagonal and 1st positive hyperdiagonal, no 2 queens on the same main diagonal are colored the same. Now is this condition, than n be not divisible by 2 and 3 also *necessary*? Mike Konrad mdk@sei.cmu.edu ****** . . . o . This is a solution for the 5-queen problem o . . . . at the torus. It has the 90 degree rotation symmetry. . . o . . . . . . o . o . . . According to T. Klove, The modular n-queen problem II, Discrete Math. 36 (1981) 33 it is unknown how to construct symmetric (90 rot) solutions for n = 1 or 5 (mod 12) and n has prime factors = 3 (mod 4). He solved the smallest cases 49 and 77. Try the next cases 121 and 133 or find a general solution. A further reference for modular or reflected queen problems is: Martin Gardner, Fractal Music, Hypercards and More ..., Freeman (1991) ******** For the 3-D N-queens problem the answer is four, at (1,1,2), (1,3,3), (2,3,1), and (3,2,3). You can't have more because with four, you must have at least two in at least one of the three horizontal slices of the cube. For the two-or-more-queen slice you must solve the n-queens problem for a 3x3 planar board, which allows you to place at most 2 queens, and one must be in a corner. The two queens cover all but one spot in the adjacent slice, so if the two-queen slice is the middle one we're already limited to no more than 4 queens. But if we put the 2-queen slice at the bottom or top, then the corner queen has line of sight to all corners of the opposite slice, so it can contain at most one queen, and so can the middle slice. If they sit in a 4x4x4 cube, the maximum is 7. Here is a sample. 1. 4 4 3 2. 2 3 4 3. 1 2 2 4. 2 4 2 5. 3 2 1 6. 1 1 4 7. 3 1 3 If they sit in a 5x5x5 cube, the maximum is 13. Here is a sample. 1. 4 5 4 2. 3 5 1 3. 5 4 2 4. 3 1 2 5. 2 1 4 6. 2 5 5 7. 4 1 5 8. 1 5 2 9. 5 2 1 10. 2 3 1 11. 1 3 5 12. 1 1 1 13. 5 1 3 ==> competition/games/chess/queens.p <== How many ways can eight queens be placed so that they control the board? ==> competition/games/chess/queens.s <== 92. The following program uses a backtracking algorithm to count positions: #include static int count = 0; void try(int row, int left, int right) { int poss, place; if (row == 0xFF) ++count; else { poss = ~(row|left|right) & 0xFF; while (poss != 0) { place = poss & -poss; try(row|place, (left|place)<<1, (right|place)>>1); poss &= ~place; } } } void main() { try(0,0,0); printf("There are %d solutions.\n", count); } -- Tony Lezard IS tony@mantis.co.uk OR tony%mantis.co.uk@uknet.ac.uk OR EVEN arl10@phx.cam.ac.uk if all else fails. ==> competition/games/chess/rook.paths.p <== How many non-overlapping paths can a rook take from one corner to the opposite on an MxN chess board? ==> competition/games/chess/rook.paths.s <== For a 1 x 1 chessboard, there are 1 unique paths. For a 1 x 2 chessboard, there are 1 unique paths. For a 1 x 3 chessboard, there are 1 unique paths. For a 1 x 4 chessboard, there are 1 unique paths. For a 1 x 5 chessboard, there are 1 unique paths. For a 1 x 6 chessboard, there are 1 unique paths. For a 1 x 7 chessboard, there are 1 unique paths. For a 1 x 8 chessboard, there are 1 unique paths. For a 2 x 2 chessboard, there are 2 unique paths. For a 2 x 3 chessboard, there are 4 unique paths. For a 2 x 4 chessboard, there are 8 unique paths. For a 2 x 5 chessboard, there are 16 unique paths. For a 2 x 6 chessboard, there are 32 unique paths. For a 2 x 7 chessboard, there are 64 unique paths. For a 2 x 8 chessboard, there are 128 unique paths. For a 3 x 3 chessboard, there are 12 unique paths. For a 3 x 4 chessboard, there are 38 unique paths. For a 3 x 5 chessboard, there are 125 unique paths. For a 3 x 6 chessboard, there are 414 unique paths. For a 3 x 7 chessboard, there are 1369 unique paths. For a 3 x 8 chessboard, there are 4522 unique paths. For a 4 x 4 chessboard, there are 184 unique paths. For a 4 x 5 chessboard, there are 976 unique paths. For a 4 x 6 chessboard, there are 5382 unique paths. For a 4 x 7 chessboard, there are 29739 unique paths. For a 4 x 8 chessboard, there are 163496 unique paths. For a 5 x 5 chessboard, there are 8512 unique paths. For a 5 x 6 chessboard, there are 79384 unique paths. For a 5 x 7 chessboard, there are 752061 unique paths. /*********************** * RookPaths.c * By: David Blume * dcb@wdl1.wdl.loral.com (Predecrement David) * * How many unique ways can a rook move from the bottom left corner * of a m * n chess board to the top right right? * * Contraints: The rook may not passover a square it has already visited. * What if we don't allow Down & Left moves? (much easier) * * This software is provided *as is.* It is not guaranteed to work on * any platform at any time anywhere. :-) Enjoy. ***********************/ #include #define kColumns 8 /* The maximum number of columns */ #define kRows 8 /* The maximum number of rows */ /* The following rule is for you to play with. */ #define kAllowDownLeft /* Whether or not to allow the rook to move D o r L */ /* Visual feedback defines... */ #undef kShowTraversals /* Whether or nor to show each successful graph */ #define kListResults /* Whether or not to list each n * m result */ #define kShowMatrix /* Display the final results in a matri x? */ char gmatrix[kColumns][kRows]; /* the working matrix * / long result[kColumns][kRows]; /* the result array */ /********************* * traverse * * This is the recursive function *********************/ traverse (short c, short r, short i, short j ) { /* made it to the top left! increase result, retract move, and return * / if (i == c && j == r) { #ifdef kShowTraversals short ti, tj; gmatrix[i][j] = 5; for (ti = c; ti >= 0; ti--) { for (tj = 0; tj <= r; tj++) { if (gmatrix[ti][tj] == 0) printf(". "); else if (gmatrix[ti][tj] == 1) printf("D "); else if (gmatrix[ti][tj] == 2) printf("R "); else if (gmatrix[ti][tj] == 3) printf("L "); else if (gmatrix[ti][tj] == 4) printf("U "); else if (gmatrix[ti][tj] == 5) printf("* "); } printf("\n"); } printf("\n"); #endif result[i][j] = result[i][j] + 1; gmatrix[i][j] = 0; return; } /* try to move, left up down right */ #ifdef kAllowDownLeft if (i != 0 && gmatrix[i-1][j] == 0) { /* left turn */ gmatrix[i][j] = 1; traverse(c, r, i-1, j); } #endif if (j != r && gmatrix[i][j+1] == 0) { /* turn up */ gmatrix[i][j] = 2; traverse(c, r, i, j+1); } #ifdef kAllowDownLeft if (j != 0 && gmatrix[i][j-1] == 0) { /* turn down */ gmatrix[i][j] = 3; traverse(c, r, i, j-1); } #endif if (i != c && gmatrix[i+1][j] == 0) { /* turn right */ gmatrix[i][j] = 4; traverse(c, r, i+1, j); } /* remove the marking on this square */ gmatrix[i][j] = 0; } main() { short i, j; /* initialize the matrix to 0 */ for (i = 0; i < kColumns; i++) { for (j = 0; j < kRows; j++) { gmatrix[i][j] = 0; } } /* call the recursive function */ for (i = 0; i < kColumns; i++) { for (j = 0; j < kRows; j++) { if (j >= i) { result[i][j] = 0; traverse (i, j, 0, 0); #ifdef kListResults printf("For a %d x %d chessboard, there are %d unique paths.\n", i+1, j+1, result[i][j]); fflush (stdout); #endif } } } /* print out the results */ #ifdef kShowMatrix printf("\n"); for (i = 0; i < kColumns; i++) { for (j = 0; j < kRows; j++) { short min = (i < j) ? i : j ; short max = (i < j) ? j : i ; printf("%6d", result[min][max]); } printf("\n"); } #endif } ==> competition/games/chess/size.of.game.tree.p <== How many different positions are there in the game tree of chess? ==> competition/games/chess/size.of.game.tree.s <== Consider the following assignment of bit strings to square states: Square State Bit String ------ ----- --- ------ Empty 0 White Pawn 100 Black Pawn 101 White Rook 11111 Black Rook 11110 White Knight 11101 Black Knight 11100 White Bishop 11011 Black Bishop 11010 White Queen 110011 Black Queen 110010 White King 110001 Black King 110000 Record a position by listing the bit string for each of the 64 squares. For a position with all the pieces still on the board, this will take 164 bits. As pieces are captured, the number of bits needed goes down. As pawns promote, the number of bits go up. For positions where a King and Rook are in position to castle if castling is legal, we will need a bit to indicate if in fact castling is legal. Same for positions where an en-passant capture may be possible. I'm going to ignore these on the grounds that a more clever encoding of a position than the one that I am proposing could probably save as many bits as I need for these considerations, and thus conjecture that 164 bits is enough to encode a chess position. This gives an upper bound of 2^164 positions, or 2.3x10^49 positions. Jurg Nievergelt, of ETH Zurich, quoted the number 2^70 (or about 10^21) in e-mail, and referred to his paper "Information content of chess positions", ACM SIGART Newsletter 62, 13-14, April 1977, to be reprinted in "Machine Intelligence" (ed Michie), to appear 1990. Note that this latest estimate, 10^21, is not too intractable: 10^7 computers running at 10^7 positions per second could scan those in 10^7 seconds, which is less than 6 months. In fact, suppose there is a winning strategy in chess for white. Suppose further that the strategy starts from a strong book opening, proceeds through middle game with only moves that Deep Thought (DT) would pick using the singular extension technique, and finally ends in an endgame that DT can analyze completely. The book opening might take you ten moves into the game and DT has demonstrated its ability to analyze mates-in-20, so how many nodes would DT really have to visit? I suggest that by using external storage such a optical WORM memory, you could easily build up a transposition table for such a midgame. If DT did not find a mate, you could progressively expand the width of the search window and add to the table until it did. Of course there would be no guarantee of success, but the table built would be useful regardless. Also, you could change the book opening and add to the table. This project could continue indefinitely until finally it must solve the game (possibly using denser and denser storage media as technology advances). What do you think? ------- I think you are a little bit too optimistic about the feasibility. Solving mate-in-19 when the moves are forcing is one thing, but solving mate-in-19 when the moves are not forcing is another. Of course, human beings are no better at the latter task. But to solve the game in the way you described would seem to require the ability to handle the latter task. Anyway, we cannot really think about doing the sort of thing you described; DT is just a poor man's chess machine project (relatively speaking). --Hsu i dont think that you understand the numbers involved. the size of the tree is still VERY large compared to all the advances that you cite. (speed of DT, size of worms, endgame projects, etc) even starting a project will probably be a waste of time since the next advance will overtake it rather than augment it. (if you start on a journey to the stars today, you will be met there by humans) ken ==> competition/games/cigarettes.p <== The game of cigarettes is played as follows: Two players take turns placing a cigarette on a circular table. The cigarettes can be placed upright (on end) or lying flat, but not so that it touches any other cigarette on the table. This continues until one person loses by not having a valid position on the table to place a cigarette. Is there a way for either of the players to guarantee a win? ==> competition/games/cigarettes.s <== The first person wins by placing a cigarette at the center of the table, and then placing each of his cigarettes in a position symmetric (with respect to the center) to the place the second player just moved. If the second player could move, then symmetrically, so can the first player. ==> competition/games/connect.four.p <== Is there a winning strategy for Connect Four? ==> competition/games/connect.four.s <== An AI program has solved Connect Four for the standard 7 x 6 board. The conclusion: White wins, was confirmed by the brute force check made by James D. Allen, which has been published in rec.games.programmer. The program called VICTOR consists of a pure knowledge-based evaluation function which can give three values to a position: 1 won by white, 0 still unclear. -1 at least a draw for Black, This evaluation function is based on 9 strategic rules concerning the game, which all nine have been (mathematically) proven to be correct. This means that a claim made about the game-theoretical value of a position by VICTOR, is correct, although no search tree is built. If the result 1 or -1 is given, the program outputs a set of rules applied, indicating the way the result can be achieved. This way one evaluation can be used to play the game to the end without any extra calculation (unless the position was still unclear, of course). Using the evaluation function alone, it has been shown that Black can at least draw the game on any 6 x (2n) board. VICTOR found an easy strategy for these boardsizes, which can be taught to anyone within 5 minutes. Nevertheless, this strategy had not been encountered before by any humans, as far as I know. For 7 x (2n) boards a similar strategy was found, in case White does not start the game in the middle column. In these cases Black can therefore at least draw the game. Furthermore, VICTOR needed only to check a few dozen positions to show that Black can at least draw the game on the 7 x 4 board. Evaluation of a position on a 7 x 4 or 7 x 6 board costs between 0.01 and 10 CPU seconds on a Sun4. For the 7 x 6 board too many positions were unclear. For that reason a combination of Conspiracy-Number Search and Depth First Search was used to determine the game-theoretical value. This took several hundreds of hours on a Sun4. The main reason for the large amount of search needed, was the fact that in many variations, the win for White was very difficult to achieve. This caused many positions to be unclear for the evaluation function. Using the results of the search, a database will be constructed of roughly 500.000 positions with their game-theoretical value. Using this datebase, VICTOR can play against humans or other programs, winning all the time (playing White). The average move takes less than a second of calculation (search in the database or evaluation of the position by the evaluation function). Some variations are given below (columns and rows are numbered as is customary in chess): 1. d1, .. The only winning move. After 1. .., a1 wins 2. e1. Other second moves for White has not been checked yet. After 1. .., b1 wins 2. f1. Other second moves for White has not been checked yet. After 1. .., c1 wins 2. f1. Only 2 g1 has not been checked yet. All other second moves for White give Black at least a draw. After 1. .., d2 wins 2. d3. All other second moves for White give black at least a draw. A nice example of the difficulty White has to win: 1. d1, d2 2. d3, d4 3. d5, b1 4. b2! The first three moves for White are forced, while alternatives at the fourth moves of White are not checked yet. A variation which took much time to check and eventually turned out to be at least a draw for Black, was: 1. d1, c1 2. c2?, .. f1 wins, while c2 does not. 2. .., c3 Only move which gives Black the draw. 3. c4, .. White's best chance. 3. .., g1!! Only 3 .., d2 has not been checked completely, while all other third moves for Black have been shown to lose. The project has been described in my 'doctoraalscriptie' (Master thesis) which has been supervised by Prof.Dr H.J. van den Herik of the Rijksuniversiteit Limburg (The Netherlands). I will give more details if requested. Victor Allis. Vrije Universiteit van Amsterdam. The Netherlands. victor@cs.vu.nl ==> competition/games/craps.p <== What are the odds in craps? ==> competition/games/craps.s <== The game of craps: There is a person who rolls the two dice, and then there is the house. 1) On the first roll, if a 7 or 11 comes up, the roller wins. If a 2, 3, or 12 comes up the house wins. Anything else is a POINT, and more rolling is necessary, as per rule 2. 2) If a POINT appears on the first roll, keep rolling the dice. At each roll, if the POINT appears again, the roller wins. At each roll, if a 7 comes up, the house wins. Keep rolling until the POINT or a 7 comes up. Then there are the players, and they are allowed to place their bets with either the roller or with the house. ----- My computations: On the first roll, P.roller.trial(1) = 2/9, and P.house.trial(1) = 1/9. Let P(x) stand for the probability of a 4,5,6,8,9,10 appearing. Then on the second and onwards rolls, the probability is: Roller: --- (i - 2) P.roller.trial(i) = \ P(x) * ((5/6 - P(x)) * P(x) (i > 1) / --- x = 4,5,6,8,9,10 House: --- (i - 2) P.house.trial(i) = \ P(x) * ((5/6 - P(x)) * 1/6 (i > 1) / --- x = 4,5,6,8,9,10 Reasoning (roller): For the roller to win on the ith trial, a POINT should have appeared on the first trial (the first P(x) term), and the same POINT should appear on the ith trial (the last P(x) term). All the in between trials should come up with a number other than 7 or the POINT (hence the (5/6 - P(x)) term). Similar reasoning holds for the house. The numbers are: P.roller.trial(i) (i > 1) = (i-1) (i-1) (i-1) 1/72 * (27/36) + 2/81 * (26/36) + 25/648 * (25/36) P.house.trial(i) (i > 1) = (i-1) (i-1) (i-1) 2/72 * (27/36) + 3/81 * (26/36) + 30/648 * (25/36) ------------------------------------------------- The total probability comes to: P.roller = 2/9 + (1/18 + 4/45 + 25/198) = 0.4929292929292929.. P.house = 1/9 + (1/9 + 2/15 + 15/99) = 0.5070707070707070.. which is not even. =========================================================================== == Avinash Chopde (with standard disclaimer) abc@unhcs.unh.edu, abc@unh.unh.edu {.....}!uunet!unh!abc ==> competition/games/crosswords.p <== Are there programs to make crosswords? What are the rules for cluing cryptic crosswords? Is there an on-line competition for cryptic cluers? ==> competition/games/crosswords.s <== You need to read the rec.puzzles.crosswords FAQL. ==> competition/games/cube.p <== What are some games involving cubes? ==> competition/games/cube.s <== Johan Myrberger's list of 3x3x3 cube puzzles (version 930222) Comments, corrections and contributions are welcome! MAIL: myrberger@e.kth.se Snailmail: Johan Myrberger Hokens gata 8 B S-116 46 STOCKHOLM SWEDEN A: Block puzzles A.1 The Soma Cube ______ ______ ______ ______ |\ \ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ | \_____\ | | |____ _____| | | | | |____ | | |____ |\| | \ |\ \| | |\| | \ |\| | \ | *_____|_____\ | \_____*_____| | *_____|_____\ | *_____|_____\ | |\ \ | | |\ \ | | | |\ \ | | | | \| \_____\ | \| \_____\ | \| | \_____\ \| | | * | |___| * | |___| *_____| | | *_____|_____| \| | \| | \| | *_____| *_____| *_____| ______ ______ ____________ |\ \ |\ \ |\ \ \ | \_____\ | \_____\ | \_____\_____\ | | |__________ _____| | |____ _____| | | | |\| | \ \ |\ \| | \ |\ \| | | | *_____|_____\_____\ | \_____*_____|_____\ | \_____*_____|_____| | | | | | | | | | | | | | | \| | | | \| | | | \| | | *_____|_____|_____| *_____|_____|_____| *_____|_____| A.2 Half Hour Puzzle ______ ______ ______ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ | | |__________ _____| | |____ | | |__________ |\| | \ \ |\ \| | \ |\| | \ \ | *_____|_____\_____\ | \_____*_____|_____\ | *_____|_____\_____\ | | | | | | | | | | | | |\ \ | \| | | | \| | | | \| | \_____\ | *_____|_____|_____| *_____|_____|_____| *_____| | |___| \| | *_____| ______ ______ ______ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ _____| | | _____| | | | | | |\ \| | |\ \| | |\| | | \_____*_____| | \_____*_____|______ ___|_*_____|______ | |\ \ | | | |\ \ \ |\ \ \ \ \| \_____\ | \| | \_____\_____\ | \_____\_____\_____\ * | |___| *_____| | | | | | | | | \| | \| | | \| | | | *_____| *_____|_____| *_____|_____|_____| A.3 Steinhaus's dissected cube ______ ______ ______ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ | | |__________ _____| | | | | |____ |\| | \ \ |\ \| | |\| | \ | *_____|_____\_____\ | \_____*_____| | *_____|_____\ | | | | | | |\ \ | | | |\ \ \| | | | \| \_____\ | \| | \_____\ *_____|_____|_____| * | |___| *_____| | | \| | \| | *_____| *_____| ____________ ______ ______ |\ \ \ |\ \ |\ \ | \_____\_____\ | \_____\ | \_____\ | | | | | | | ___________| | | \| | | |\| | |\ \ \| | *_____|_____|______ _________|_*_____| | \_____\_____*_____| \ |\ \ \ |\ \ \ \ | | |\ \ | \| \_____\_____\ | \_____\_____\_____\ \| | \_____\ | * | | | | | | | | *_____| | |___| \| | | \| | | | \| | *_____|_____| *_____|_____|_____| *_____| A.4 ______ |\ \ | \_____\ | | |____ Nine of these make a 3x3x3 cube. |\| | \ | *_____|_____\ | | | | \| | | *_____|_____| A.5 ______ ____________ |\ \ |\ \ \ | \_____\ | \_____\_____\ ____________ | | |____ | | | | |\ \ \ |\| | \ |\| | | | \_____\_____\ | *_____|_____\ | *_____|_____| | | | | | | | | | | | | \| | | \| | | \| | | *_____|_____| *_____|_____| *_____|_____| ______ ______ |\ \ |\ \ | \_____\ | \_____\ ______ ______ | | |____ | | |__________ |\ \ |\ \ |\| | \ |\| | \ \ | \_____\ | \_____\ | *_____|_____\ | *_____|_____\_____\ | | |___| | | | | | |____ | | | | | |\| | \| | |\| | | \ |\| | | | | *_____|_____*_____| | *_____|_____|_____\ | *_____|_____|_____| | | | | | | | | | | | | | | | \| | | | \| | | | \| | | | *_____|_____|_____| *_____|_____|_____| *_____|_____|_____| A.6 ______ ______ ______ ______ |\ \ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ | \_____\ | | |____ _____| | | | | |____ | | |____ |\| | \ |\ \| | |\| | \ |\| | \ | *_____|_____\ | \_____*_____| | *_____|_____\ | *_____|_____\ | |\ \ | | |\ \ | | | |\ \ | | | | \| \_____\ | \| \_____\ | \| | \_____\ \| | | * | |___| * | |___| *_____| | | *_____|_____| \| | \| | \| | *_____| *_____| *_____| ______ ____________ ____________ |\ \ |\ \ \ |\ \ \ | \_____\ | \_____\_____\ | \_____\_____\ _____| | |____ _____| | | | _____| | | | |\ \| | \ |\ \| | | |\ \| | | | \_____*_____|_____\ | \_____*_____|_____| | \_____*_____|_____| | | | | | | | | | | | | | \| | | | \| | | \| | | *_____|_____|_____| *_____|_____| *_____|_____| A.7 ____________ |\ \ \ | \_____\_____\ | | | | |\| | | Six of these and three unit cubes make a 3x3x3 cube. | *_____|_____| | | | | \| | | *_____|_____| A.8 Oskar's ____________ ______ |\ \ \ |\ \ | \_____\_____\ | \_____\ _____| | | | | | |__________ __________________ |\ \| | | |\| | \ \ |\ \ \ \ | \_____*_____|_____| x 5 | *_____|_____\_____\ | *_____\_____\_____\ | | | | | | | | | | | | | | \| | | \| | | | \| | | | *_____|_____| *_____|_____|_____| *_____|_____|_____| A.9 Trikub ____________ ______ ______ |\ \ \ |\ \ |\ \ | \_____\_____\ | \_____\ | \_____\ | | | | | | |__________ _____| | |____ |\| | | |\| | \ \ |\ \| | \ | *_____|_____| | *_____|_____\_____\ | \_____*_____|_____\ | | | | | | | | | | | | | | \| | | \| | | | \| | | | *_____|_____| *_____|_____|_____| *_____|_____|_____| ______ ______ ____________ |\ \ |\ \ |\ \ \ | \_____\ | \_____\ | \_____\_____\ | | |____ | | |____ _____| | | | |\| | \ |\| | \ |\ \| | | | *_____|_____\ | *_____|_____\ | \_____*_____|_____| | |\ \ | | | |\ \ | | | | \| \_____\ | \| | \_____\ \| | | * | |___| *_____| | | *_____|_____| \| | \| | *_____| *_____| and three single cubes in a different colour. The object is to build 3x3x3 cubes with the three single cubes in various positions. E.g: * * * as center * * * as edge * *(3) as * *(2) as * S * * * * *(2)* space *(2)* center * * * * * S (1)* * diagonal (2)* * diagonal (The other two variations with the single cubes in a row are impossible) A.10 ______ ______ ______ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ _____| | | | | |____ | | |____ |\ \| | |\| | \ |\| | \ | \_____*_____| | *_____|_____\ ___|_*_____|_____\ | |\ \ | | | |\ \ |\ \ \ | \| \_____\ | \| | \_____\ | \_____\_____\ | * | |___| *_____| | | | | | |___| \| | \| | \| | | *_____| *_____| *_____|_____| ______ ______ ______ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ | | |__________ _____| | |____ | | |____ |\| | \ \ |\ \| | \ |\| | \ | *_____|_____\_____\ | \_____*_____|_____\ | *_____|_____\______ | |\ \ | | | | | | | | | |\ \ \ \| \_____\ | | \| | | | \| | \_____\_____\ * | |___|_____| *_____|_____|_____| *_____| | | | \| | \| | | *_____| *_____|_____| B: Coloured blocks puzzles B.1 Kolor Kraze Thirteen pieces. Each subcube is coloured with one of nine colours as shown below. The object is to form a cube with nine colours on each face. ______ |\ \ | \_____\ | | | ______ ______ ______ ______ ______ ______ |\| 1 | |\ \ |\ \ |\ \ |\ \ |\ \ |\ \ | *_____| | \_____\ | \_____\ | \_____\ | \_____\ | \_____\ | \_____\ | | | | | | | | | | | | | | | | | | | | | |\| 2 | |\| 2 | |\| 2 | |\| 4 | |\| 4 | |\| 7 | |\| 9 | | *_____| | *_____| | *_____| | *_____| | *_____| | *_____| | *_____| | | | | | | | | | | | | | | | | | | | | | \| 3 | \| 3 | \| 1 | \| 1 | \| 5 | \| 5 | \| 5 | *_____| *_____| *_____| *_____| *_____| *_____| *_____| ______ ______ ______ ______ ______ ______ |\ \ |\ \ |\ \ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ | \_____\ | \_____\ | \_____\ | | | | | | | | | | | | | | | | | | |\| 9 | |\| 9 | |\| 3 | |\| 6 | |\| 6 | |\| 6 | | *_____| | *_____| | *_____| | *_____| | *_____| | *_____| | | | | | | | | | | | | | | | | | | \| 7 | \| 8 | \| 8 | \| 8 | \| 7 | \| 4 | *_____| *_____| *_____| *_____| *_____| *_____| B.2 Given nine red, nine blue and nine yellow cubes. Form a 3x3x3 cube in which all three colours appears in each of the 27 orthogonal rows. B.3 Given nine red, nine blue and nine yellow cubes. Form a 3x3x3 cube so that every row of three (the 27 orthogonal rows, the 18 diagonal rows on the nine square cross-sections and the 4 space diagonals) contains neither three cubes of like colour nor three of three different colours. B.4 Nine pieces, three of each type. Each subcube is coloured with one of three colours as shown below. The object is to build a 3x3x3 cube in which all three colours appears in each of the 27 orthogonal rows. (As in B.2) ______ ______ ______ |\ \ |\ \ |\ \ | \_____\ | \_____\ | \_____\ | | |____ | | |____ | | |____ |\| A | \ x 3 |\| B | \ x 3 |\| A | \ x 3 | *_____|_____\ | *_____|_____\ | *_____|_____\ | | | | | | | | | | | | \| B | C | \| A | C | \| C | B | *_____|_____| *_____|_____| *_____|_____| C: Strings of cubes C.1 Pululahua's dice 27 cubes are joined by an elastic thread through the centers of the cubes as shown below. The object is to fold the structure to a 3x3x3 cube. ____________________________________ |\ \ \ \ \ \ \ | \_____\_____\_____\_____\_____\_____\ | | | | | | | | |\| :77|77777|77: | :77|77777|77: | | *__:__|_____|__:__|__:__|_____|__:__| | | : |___| | : | : |___| | : | |\| : | \| 777|777 | \| : | | *__:__|_____*_____|_____|_____*__:__| | | : | | |___| | | : |____ \| 777|77777|77: | \| :77|777 | \ *_____|_____|__:__|_____*__:__|_____|_____\ | | : | | : | | | |\| : | + | 777|77777|77: | | *__:__|__:__|_____|_____|__:__| | | : | : | | | : | \| + | : | :77|77777|777 | *_____|__:__|__:__|_____|_____| | | : | : | \| 777|777 | *_____|_____| C.1.X The C.1 puzzle type exploited by Glenn A. Iba (quoted) INTRODUCTION "Chain Cube" Puzzles consist of 27 unit cubies with a string running sequentially through them. The string always enters and exits a cubie through the center of a face. The typical cubie has one entry and one exit (the ends of the chain only have 1, since the string terminates there). There are two ways for the string to pass through any single cubie: 1. The string enters and exits non-adjacent faces (i.e. passes straight through the cubie) 2. It enters and exits through adjacent faces (i.e. makes a "right angle" turn through the cubie) Thus a chain is defined by its sequence of straight steps and right angle turns. Reversing the sequence (of course) specifies the same chain since the chain can be "read" starting from either end. Before making a turn, it is possible to "pivot" the next cubie to be placed, so there are (in general) 4 choices of how to make a "Turn" in 3-space. The object is to fold the chain into a 3x3x3 cube. It is possible to prove that any solvable sequence must have at least 2 straight steps. [The smallest odd-dimensioned box that can be packed by a chain of all Turns and no Straights is 3x5x7. Not a 3x3x3 puzzle, but an interesting challenge. The 5x5x5 can be done too, but its not the smallest in volume]. With the aid of a computer search program I've produced a catalog of the number of solutions for all (solvable) sequences. Here is an example sequence that has a unique solution (up to reflections and rotations): (2 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1) the notation is a kind of "run length" coding, where the chain takes the given number of steps in a straight line, then make a right-angle turn. Equivalently, replace 1 by Turn, 2 by Straight followed by a Turn. The above sequence was actually a physical puzzle I saw at Roy's house, so I recorded the sequence, and verified (by hand and computer) that the solution is unique. There are always 26 steps in a chain, so the "sum" of the 1's and 2's in a pattern will always be 26. For purposes of taxonomizing, the "level" of a string pattern is taken to be the number of 2's occuring in its specification. COUNTS OF SOLVABLE AND UNIQUELY SOLVABLE STRING PATTERNS (recall that Level refers to the number of 2's in the chain spec) Level Solvable Uniquely Patterns Solvable 0 0 0 1 0 0 2 24 0 3 235 15 4 1037 144 5 2563 589 6 3444 1053 7 2674 1078 8 1159 556 9 303 187 10 46 34 11 2 2 12 0 0 13 0 0 _______ ______ Total Patterns: 11487 3658 SOME SAMPLE UNIQUELY SOLVABLE CHAINS In the following the format is: ( #solutions palindrome? #solutions-by-start-type chain-pattern-as string ) where #solutions is the total number of solutions up to reflections and rotations palindrome? is T or NIL according to whether or not the chain is a palindrome #solutions by-start-type lists the 3 separate counts for the number of solutions starting the chain of in the 3 distinct possible ways. chain-pattern-as-string is simply the chain sequence My intuition is that the lower level chains are harder to solve, because there are fewer straight steps, and staight steps are generally more constraining. Another way to view this, is that there are more choices of pivoting for turns because there are more turns in the chains at lower levels. Here are the uniquely solvable chains for level 3: (note that non-palindrome chains only appear once -- I picked a "canonical" ordering) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Level 3 ( 3 straight steps) -- 15 uniquely solvable patterns ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (1 NIL (1 0 0) "21121111112111111111111") (1 NIL (1 0 0) "21121111111111111121111") (1 NIL (1 0 0) "21111112112111111111111") (1 NIL (1 0 0) "21111111211111111111112") (1 NIL (1 0 0) "12121111111111112111111") (1 NIL (1 0 0) "11211211112111111111111") (1 NIL (1 0 0) "11112121111111211111111") (1 NIL (1 0 0) "11112112112111111111111") (1 NIL (1 0 0) "11112112111111211111111") (1 NIL (1 0 0) "11112111121121111111111") (1 NIL (1 0 0) "11112111111211211111111") (1 NIL (1 0 0) "11112111111112121111111") (1 NIL (1 0 0) "11111121122111111111111") (1 NIL (1 0 0) "11111112122111111111111") (1 NIL (1 0 0) "11111111221121111111111") C.2 Magic Interlocking Cube (Glenn A. Iba quoted) This chain problem is marketed as "Magic Interlocking Cube -- the Ultimate Cube Puzzle". It has colored cubies, each cubie having 6 distinctly colored faces (Red, Orange, Yellow, Green, Blue, and White). The object is to fold the chain into a 3x3x3 cube with each face being all one color (like a solved Rubik's cube). The string for the chain is actually a flexible rubber band, and enters a cubie through a (straight) slot that cuts across 3 faces, and exits through another slot that cuts the other 3 faces. Here is a rough attempt to picture a cubie: (the x's mark the slots cut for the rubber band to enter/exit) __________ / /| xxxxxxxxxxx | / / x | /_________/ x | | | x | | | | | | / | x | / | x | / | x |/ -----x----- Laid out flat the cubie faces would look like this: _________ | | | | | x | | x | |____x____|_________ _________ _________ | x | | | | | x | | | | | x | x x x x x x x x x x x | | x | | | | |____x____|_________|_________|_________| | x | | x | | x | | | |_________| The structure of the slots gives 3 choices of entry face, and 3 choices of exit face for each cube. It's complicated to specify the topology and coloring but here goes: Imagine the chain stretched out in a straight line from left to right. Let the rubber band go straight through each cubie, entering and exiting in the "middle" of each slot. It turns out that the cubies are colored so that opposite faces are always colored by the following pairs: Red-Orange Yellow-White Green-Blue So I will specify only the Top, Front, and Left colors of each cubie in the chain. Then I'll specify the slot structure. Color sequences from left to right (colors are R,O,Y,G,B,and W): Top: RRRRRRRRRRRRRRRRRRRRRRRRRRR Front: YYYYYYYYYYYYWWWYYYYYYYYYYYY Left: BBBBBGBBBGGGGGGGGGBBGGGGBBB For the slots, all the full cuts are hidden, so only the "half-slots" appear. Here is the sequence of "half slots" for the Top (Red) faces: (again left to right) Slots: ><><><><<><><<<><><>>>>><>> Where > = slot goes to left < = slot goes to right To be clearer, > (Left): _______ | | | | xxxxx | | | |_______| < (Right): _______ | | | | | xxxxx | | |_______| Knowing one slot of a cubie determines all the other slots. I don't remember whether the solution is unique. In fact I'm not certain whether I actually ever solved it. I think I did, but I don't have a clear recollection. D: Blocks with pins D.1 Holzwurm (Torsten Sillke quoted) Inventer: Dieter Matthes Distribution: Pyramo-Spiele-Puzzle Silvia Heinz Sendbuehl 1 D-8351 Bernried tel: +49-9905-1613 Pieces: 9 tricubes Each piece has one hole (H) which goes through the entire cube. The following puctures show the tricubes from above. The faces where you see a hole are marked with 'H'. If you see a hole at the top then there is a hole at the bottom too. Each peace has a worm (W) one one face. You have to match the holes and the worms. As a worm fills a hole completely, you can not put two worms at both ends of the hole of the same cube. __H__ _____ _____ | | | | | | | | | |W | | |_____|_____ |_____|_____ |_____|_____ | | | | | | | | | | | |W | | |H | H | |W |_____|_____| |_____|_____| |_____|_____| __H__ _____ _____ | | | | | | | | | | | W | |_____|_____ |_____|_____ |_____|_____ | | | | | | | | | | | | | W | H | | | H | |_____|_____| |_____|_____| |_____|_____| W __W__ _____ _____ | | | | | | | | H| |H | | |_____|_____ |_____|_____ |_____|_____ | | | | | | | | | | | H | | | | H| | W | |_____|_____| |_____|_____| |_____|_____| W Aim: build a 3*3*3 cube without a worm looking outside. take note, it is no matching problem, as | | worm> H| |H geometry/coloring/cheese.cube.p <== A cube of cheese is divided into 27 subcubes. A mouse starts at one corner and eats through every subcube. Can it finish in the middle? ==> geometry/coloring/cheese.cube.s <== Give the subcubes a checkerboard-like coloring so that no two adjacent subcubes have the same color. If the corner subcubes are black, the cube will have 14 black subcubes and 13 white ones. The mouse always alternates colors and so must end in a black subcube. But the center subcube is white, so the mouse can't end there. E.4 Cut the 3*3*3 cube into single cubes. At each slice you can rearrange the blocks. Can you do it with fewer than 6 cuts? ==> competition/games/go-moku.p <== For a game of k in a row on an n x n board, for what values of k and n is there a win? Is (the largest such) k eventually constant or does it increase with n? ==> competition/games/go-moku.s <== Berlekamp, Conway, and Guy's _Winning_Ways_ reports proof that the maximum k is between 4 and 7 inclusive, and it appears to be 5 or 6. They report: . 4-in-a-row is a draw on a 5x5 board (C. Y. Lee), but not on a 4x30 board (C. Lustenberger). . N-in-a-row is shown to be a draw on a NxN board for N>4, using a general pairing technique devised by A. W. Hales and R. I. Jewett. . 9-in-a-row is a draw even on an infinite board, a 1954 result of H. O. Pollak and C. E. Shannon. . More recently, the pseudonymous group T. G. L. Zetters showed that 8-in-a-row is a draw on an infinite board, and have made some progress on showing infinite 7-in-a-row to be a draw. Go-moku is 5-in-a-row played on a 19x19 go board. It is apparently a win for the first player, and so the Japanese have introduced several 'handicaps' for the first player (e.g., he must win with _exactly_ five: 6-in-a-row doesn't count), but apparently the game is still a win for the first player. None of these apparent results have been proven. ==> competition/games/hi-q.p <== What is the quickest solution of the game Hi-Q (also called Solitaire)? For those of you who aren't sure what the game looks like: 32 movable pegs ("+") are arranged on the following board such that only the middle position is empty ("-"). Just to be complete: the board consists of only these 33 positions. 1 2 3 4 5 6 7 1 + + + 2 + + + 3 + + + + + + + 4 + + + - + + + 5 + + + + + + + 6 + + + 7 + + + A piece moves on this board by jumping over one of its immediate neighbor (horizontally or vertically) into an empty space opposite. The peg that was jumped over, is hit and removed from the board. A move can contain multiple hits if you use the same peg to make the hits. You have to end with one peg exactly in the middle position (44). ==> competition/games/hi-q.s <== 1: 46*44 2: 65*45 3: 57*55 4: 54*56 5: 52*54 6: 73*53 7: 43*63 8: 75*73*53 9: 35*55 10: 15*35 11: 23*43*63*65*45*25 12: 37*57*55*53 13: 31*33 14: 34*32 15: 51*31*33 16: 13*15*35 17: 36*34*32*52*54*34 18: 24*44 Found by Ernest Bergholt in 1912 and was proved to be minimal by John Beasley in 1964. References The Ins and Outs of Peg Solitaire John D Beasley Oxford U press, 1985 ISBN 0-19-853203-2 Winning Ways, Vol. 2, Ch. 23 Berlekamp, E.R. Academic Press, 1982 ISBN 01-12-091102-7 ==> competition/games/jeopardy.p <== What are the highest, lowest, and most different scores contestants can achieve during a single game of Jeopardy? ==> competition/games/jeopardy.s <== highest: $283,200.00, lowest: -$29,000.00, biggest difference: $281,600.00 (1) Our theoretical contestant has an itchy trigger finger, and rings in with an answer before either of his/her opponents. (2) The daily doubles (1 in the Jeopardy! round, 2 in the Double Jeopardy! round) all appear under an answer in the $100 or $200 rows. (3) All answers given by our contestant are (will be?) correct. Therefore: Round 1 (Jeopardy!): Max. score per category: $1500. For 6 categories - $100 for the DD, that's $8900. Our hero bets the farm and wins - score: $17,800. Round 2 (Double Jeopardy!): Max. score per category: $3000. Assume that the DDs are found last, in order. For 6 categories - $400 for both DDs, that's $17,600. Added to his/her winnings in Round 1, that's $35,400. After the 1st DD, where the whole thing is wagered, the contestant's score is $70,800. Then the whole amount is wagered again, yielding a total of $141,600. Round 3 (Final Jeopardy!): Our (very greedy! :) hero now bets the whole thing, to see just how much s/he can actually win. Assuming that his/her answer is right, the final amount would be $283,200. But the contestant can only take home $100,000; the rest is donated to charity. To calculate the lowest possible socre: -1500 x 6 = -9000 + 100 = -8900. On the Daily Double that appears in the 100 slot, you bet the maximum allowed, 500, and lose. So after the first round, you are at -9400. -3000 x 6 = -18000 + 400 = -17600 On the two Daily Doubles in the 200 slots, bet the maximum allowed, 1000. So after the second round you are at -9400 + -19600 = -29000. This is the lowest score you can achieve in Jeopardy before the Final Jeopardy round. The caveat here is that you *must* be the person sitting in the left-most seat (either a returning champion or the luckiest of the three people who come in after a five-time champion "retires") at the beginning of the game, because otherwise you will not have control of the board when the first Daily Double comes along. The scenario for the maximum difference is the same as the highest score, except that on every question that isn't a daily double, the worst contestant rings in ahead of the best one, and makes a wrong guess, after which the best contestant rings in and gets it right. However, since contestants with negative scores are disqualified before Final Jeopardy!, it is arguable that the negative score ceases to exist at that point. This also applies to zero scores. In that case, someone else would have to qualify for Final Jeopardy! for the maximum difference to exist, taking one $100 or $200 question away from the best player. In that case the best player would score 8*$200 lower, so the maximum difference would be $281,600.00. ==> competition/games/nim.p <== Place 10 piles of 10 $1 bills in a row. A valid move is to reduce the last i>0 piles by the same amount j>0 for some i and j; a pile reduced to nothing is considered to have been removed. The loser is the player who picks up the last dollar, and they must forfeit half of what they picked up to the winner. 1) Who is the winner in Waldo Nim, the first or the second player? 2) How much more money than the loser can the winner obtain with best play on both parties? ==> competition/games/nim.s <== For the particular game described we only need to consider positions for which the following condition holds for each pile: (number of bills in pile k) + k >= (number of piles) + 1 A GOOD position is defined as one in which this condition holds, with equality applying only to one pile P, and all piles following P having the same number of bills as P. ( So the initial position is GOOD, the special pile being the first. ) I now claim that if I leave you a GOOD position, and you make any move, I can move back to a GOOD position. Suppose there are n piles and the special pile is numbered (n-p+1) (so that the last p piles each contain p bills). (1) You take p bills from p or more piles; (a) If p = n, you have just taken the last bill and lost. (b) Otherwise I reduce pile (n-p) (which is now the last) to 1 bill. (2) You take p bills from r(p; I take (p-q) bills from (q+r-p) piles (b) q+r<=p; I take (p-q) bills from (q+r) piles Verifying that each of the resulting positions is GOOD is tedious but straightforward. It is left as an exercise for the reader. -- RobH ==> competition/games/online/online.scrabble.p <== How can I play Scrabble online on the Internet? ==> competition/games/online/online.scrabble.s <== Announcing ScrabbleMOO, a server running at 134.53.14.110, port 7777 (nextsrv.cas.muohio.edu 7777). The server software is version 1.7.0 of the LambdaMOO server code. To reach it, you can use "telnet 134.53.14.110 7777", and sign on. You will have a unique name and password on the server, and directions are provided in the opening screen on how to accomplish signing on. The first time, you will need to type "create YourName YourPassword", and each time thereafter, "connect YourName YourPassword". There are currently 5 Scrabble boards set up, with global individual high score and game-cumulative high score lists. Games can be saved, and restored at a later time. There are complete command instructions at each board (via the command "instructions"); usage is simple and intuitive. There are commands to undo turns, exchange tiles, and pass, and there are a variety of options available to change the way the board and rack are displayed. We do not yet have a dictionary for challenges installed on-line, and that is coming very soon. I am seriously contemplating using the OSPD.shar wordlist that Ross Beresford listed in a recent Usenet article. It seems to have the full wordlist from the 1st edition of the OSPD, plus longer words from some other source. I have personal wordlists updating the OSPD to the 2nd edition, for words up to 4 letters long, and will have the longer words in the near future. Usage of a certain dictionary for challenges is not enforced, and really can't be. Many of the regular players there have their personal copy of the OSPD. It's all informal, and for fun. Players agree what dictionary to use on a game-by-game basis, though the OSPD is encouraged. There are even commands to enable kibitzing, if watching rather than playing is what you're into. Come by and try it out. We have all skill levels of players, and we welcome more! ==> competition/games/online/unlimited.adventures.p <== Where can I find information about unlimited adventures? ==> competition/games/online/unlimited.adventures.s <== ccosun.caltech.edu -- pub/adnd/inbound/UA wuarchive.wustl.edu -- pub/msdos_uploads/games/UA ==> competition/games/othello.p <== How good are computers at Othello? ==> competition/games/othello.s <== ("Othello" is a registered trademark of the Anjar Company Inc.) As of 1992, the best Othello programs may have reached or surpassed the best human players [2][3]. As early as 1980 Jonathon Cerf, then World Othello Champion, remarked: "In my opinion the top programs [...] are now equal (if not superior) to the best human players." [1] However, Othello's game theoretic value, unlike checkers, will likely remain unknown for quite some time. Barring some unforeseen shortcut or bankroll, a perfect Othello playing program would need to search in the neighborhood of 50 plies. Today, even a general 30 ply search to end the game, i.e. 30 remaining empty squares, is beyond reach. Furthermore, the game of Othello does not lend itself to endgame database techniques that have proven so effective in checkers, and in certain chess endgames. Progress of the best Othello computer programs: 1980 "Iago" (by Rosenbloom) [2] 1990 "Bill 3.0" (by Lee and Mahajan) [3] uses: 1. sophisticated searching and timing algorithms, e.g. iterative deepening, hash/killer tables, zero-window search. 2. lookup tables to encode positional evaluation knowledge. 3. Bayesian learning for the evaluation function. The average middle game search depth is 8 plies. Exhaustive endgame search within tournament-play time constraints, is usually possible with 13 to 15 empty squares remaining. "Bill 3.0" defeated Brian Rose, the highest rated American Othello player, by a score of 56-8. 1992 At the 4th AST Computer Olympiad [4][5], the top three programs were: Othel du Nord (France) Aida (The Netherlands) Jacp'Oth (France) References ---------- [1] Othello Quarterly 3(1) (1981) 12-16 [2] P.S. Rosenbloom, A World Championship-Level Othello Program, "Artificial Intelligence" 19 (1982) 279-320 [3] Kai-Fu Lee and Sanjoy Mahajan, The Development of a World Class Othello Program, "Artificial Intelligence" 43 (1990) 21-36 [4] D.M. Breuker and J. Gnodde, The AST 4th Computer Olympiad, "International Computer Chess Association Journal 15-3 (1992) 152-153 [5] Jos Uiterwijk, The AST 4th Conference on Computer Games, "International Computer Chess Association Journal 15-3 (1992) 158-161 Myron P. Souris EDS/Unigraphics St. Louis, Missouri souris@ug.eds.com ==> competition/games/pc/best.p <== What are the best PC games? ==> competition/games/pc/best.s <== Read "net pc games top 100" in newsgroup comp.sys.ibm.pc.games.announce. ==> competition/games/pc/reviews.p <== Are reviews of PC games available online? ==> competition/games/pc/reviews.s <== Presenting... the Game Bytes Issues Index! (Issues 1-8) Game Bytes has covered well over 100 games in the past several issues. Using this index, you can look up the particular games you're interested in, find out what issues of Game Bytes cover them, and download those issues. Also included is a list of the interviews GB has done to date - - the interviews from several issues ago still contain a lot of current material. The easiest way to use the games index is to employ the search command of your favorite word processor to find a distinctive string, such as "Ultima","Perfect", or "Lemmings". The list is alphabetized; series have been listed together rather than by individual subtitle. All issues of Game Bytes to date are available by anonymous FTP at ftp.ulowell.edu in the /msdos/Games/GameByte directory and are mirrored on other FTP sites as well. Contact Ross Erickson, ross@kaos.b11.ingr.com, if you need assistance acquiring Game Bytes or have other questions. Game Bytes Interview List, Issues 1 - 7, Chronological Order ----------------------------------------------------------------- Issue Person(s) Company Sample Games ----- --------- ------- ------------ 2 Richard Garriott Origin Ultima series 3 Chris Roberts Origin Wing Commander, Strike C. 4 ID Software team Apogee* Wolfenstein 3D, Commander Keen 5 Damon Slye Dynamix Red Baron, Aces of the Pacific 5 Scott Miller Apogee Wolf3D, C. Keen, Duke Nukem 6 Bob Bates (Part 1) Legend Spellcasting 101 7 Bob Bates (Part 2) "" "" 8 Looking Glass Tech Origin Underworld 1 and 2 * distributing/producing company Game Bytes Reviews Index, Issues 1 - 8, Alphabetical by Title --------------------------------------------------------------------- Title Review Preview Tips ----- ------ ------- ---- A-Train 3 A.T.A.C. 5 Aces of the Pacific 3 1 8 Action Stations! 8 Air Combat 5 Air Force Commander 8 Alien 3 (Sega Genesis) 7 Amazon 8 6 Axelay (Super Nintendo) 8 B-17 Flying Fortress 6 4 B.A.T. II: The Koshan Conspiracy 7 Battlecruiser 3000 A.D. 8 Birds of Prey 7 4 Carrier Strike 6 Carriers at War 6 Castle Wolfenstein 3-D 2 Challenge of the Five Realms 4 Chessmaster 3000 2 Civilization 5 Comanche: Maximum Overkill 6 Conflict: Korea 6 Conquered Kingdoms 7 Conquests of the Longbow 3 Contra 3: The Alien Wars (Super Nintendo) 5 Crisis in the Kremlin 6 D/Generation 2 Dark Sun: Shattered Lands 6 Darklands 7 3 7 Darkseed 5 Dune 3 Dungeon Master 7 Dynamix Football 3 Earl Weaver Baseball 2 4 Ecoquest: The Search for Cetus 2 5 Eric the Unready 8 Eye of the Beholder 2 1 Eye of the Beholder 3 8 F-117A Stealth Fighter 3 F-15 Strike Eagle III 5 Falcon 3.0 1 5,8 Falcon 3.0: Operation Flying Tiger 6 Flight Simulator 4.0 Scenery 8 Front Page Sports: Football 8 6 Galactix 6 Gateway 4 Global Conquest 3 Gods 6 Gravis Gamepad 4 Great Naval Battles 8 Greens! 2 Gunship 2000 2 Hardball 3 4,5 Hardball 3 Statistical Utilities 7 Harpoon 1.3 Designer Series / IOPG 6 Heaven and Earth 4 Heimdall 7 Hong Kong Mahjong 3 Indiana Jones and the Fate of Atlantis 5 Jack Nicklaus Golf: Signature Edition 2 Joe and Mac (SNES) 2 Johnny Castaway 8 King's Quest VI: Heir Today, Gone Tomorrow 6 Laura Bow 2: The Dagger of Amon Ra 4 3 Legends of Valor 8 Les Manley: Lost in L.A. 1 Links 386 Pro 5 1 Links Courses: Troon North 2 Loom -- CD-ROM version 5 Lord of the Rings II: The Two Towers 7 3 Lost Treasures of Infocom 5 Lure of the Temptress 8 Mantis: XF5700 Experimental Space Fighter 7 4 Martian Memorandum 5 Micro League Baseball 4 6 Might and Magic: Clouds of Xeen 8 Mike Ditka's Ultimate Football 6 Monkey Island 2: LeChuck's Revenge 5 NCAA Basketball (Super Nintendo) 8 NCAA: The Road to the Final Four 3 NFL Pro League 7 NHLPA Hockey '93 (Sega Genesis) 7 Nova 9 2 Oh No! More Lemmings 3 Out of This World 6 Pirates! Gold 2 Planet's Edge 3 Pools of Darkness 2 Powermonger 5 Prince of Persia 4 Prophecy of the Shadow 7 Pursue the Pennant 4.0 4 Quest for Glory I (VGA edition) 7 Quest for Glory III: The Wages of War 7 Rampart 4 Rampart (SNES) 7 RBI Baseball 4 (Sega Genesis) 7 Red Baron Mission Builder 8 4 Rex Nebular and the Cosmic Gender Bender 8 5 Risk for Windows 1 Robosport for Windows 8 Rules of Engagement 7 Secret Weapons of the Luftwaffe 4 Sega CD-ROM (Sega Genesis) 8 Sherlock Holmes, Consulting Detective Vol.I 7 Shining in the Darkness (Sega Genesis) 4 Siege 6 SimAnt 4 Solitaire's Journey 5 Sonic the Hedgehog 2 8 Space Megaforce (SNES) 7 Space Quest V: The Next Mutation 3 Speedball 2 5 Spellcasting 301: Spring Break 8 8 Spellcraft: Aspects of Valor 3 Splatterhouse 2 (Sega Genesis) 5 S.S.I. Goldbox summary 8 Star Control 2 8 Star Legions 6 Star Trek: 25th Anniversary 1 Street Fighter 2 8 Strike Commander 3 Stunt Island 8 7 Summer Challenge 8 5 Super Hi-Impact Football (Sega Genesis) 8 Super Star Wars (SNES) 7 Super Tetris 3 Take-a-Break Pinball 6 Tegel's Mercenaries 6 Terminator 2029: Cybergen 5 The 7th Guest 5 The Castle of Dr. Brain 5 The Incredible Machine 7 The Legend of Kyrandia 7 The Lost Admiral 6 The Magic Candle II: The Four and Forty 5 The Miracle 3 The Mystical Quest (SNES) 7 The Perfect General 3 Theatre of War 6 Thrustmaster 4 Thunderhawk 2 TimeQuest 2 Tony La Russa's Ultimate Baseball II 8 Turbo Science 7 Ultima 1, 2, and 3 (First Trilogy) 7 Ultima 7: Forge of Virtue 6 4 Ultima 7: The Black Gate 3 1 5,6 Ultima Underworld: The Stygian Abyss 3 7 Ultima Underworld 2: Labyrinth of Worlds 8 V for Victory: Utah Beach 7 Veil of Darkness 8 WaxWorks 7 Wayne Gretzky Hockey III 5 Wing Commander 2 1 Wing Commander 2: Special Operations 2 4 Winter Challenge 5 Wizardry 6: Bane of the Cosmic Forge 1 Wizardry 7: Crusaders of the Dark Savant 8 5 Wordtris 4 World Circuit 7 X-Wing: Star Wars Space Combat Simulator 7 ==> competition/games/pc/solutions.p <== What are the solutions to various popular PC games? ==> competition/games/pc/solutions.s <== Solutions, hints, etc. for many games exist at: pub/game_solutions directory on sun0.urz.uni-heidelberg.de pub/games/solutions directory on risc.ua.edu (130.160.4.7) pub/msdos/romulus directory on ftp.uwp.edu (131.210.1.4) ==> competition/games/poker.face.up.p <== In Face-Up Poker, two players each select five cards from a face-up deck, bet, discard and draw. Is there a winning strategy for this game? What if the players select cards alternately? ==> competition/games/poker.face.up.s <== If the first player draws four aces, the second player draws four kings. If the first player keeps the four aces on the draw, the second player draws a king-high straight flush, and if the first player pitches the aces to draw a straight flush, the second player can always make a higher straight flush. Instead, the winning strategy is for the first player to draw four tens. The second player cannot draw a royal flush, and in order to prevent the first player from getting one, the second player must draw at least one card higher than the ten from each suit, which means he can't do better than four-of-a-kind. Then the first player wins by drawing a straight flush from any suit. If the cards are dealt alternately as in real poker, the second player can always tie with proper strategy. The second player mirrors the first player's selections in rank and color. For example, if the first player picks up a red queen, the second player picks up a red queen. When they are done playing, their hands will be identical except one will have spades and hearts where the other has clubs and diamonds, and vice versa. Since suits aren't ranked in poker, the hands are tied. It is unknown if there is a winning strategy if the replacement cards are dealt together as in real poker, as opposed to alternately. ==> competition/games/risk.p <== What are the odds when tossing dice in Risk? ==> competition/games/risk.s <== Odds calculated with program by David Karr (karr@cs.cornell.edu): Attacker rolls 3 dice, defender rolls 2 dice: Attacker Defender Probability loses loses 0 2 2890/7776 = 0.3716563786 1 1 2611/7776 = 0.3357767490 2 0 2275/7776 = 0.2925668724 Attacker rolls 3 dice, defender rolls 1 dice: Attacker Defender Probability loses loses 0 1 855/1296 = 0.6597222222 1 0 441/1296 = 0.3402777778 Attacker rolls 2 dice, defender rolls 2 dice: Attacker Defender Probability loses loses 0 2 295/1296 = 0.2276234568 1 1 420/1296 = 0.3240740741 2 0 581/1296 = 0.4483024691 Attacker rolls 2 dice, defender rolls 1 dice: Attacker Defender Probability loses loses 0 1 125/216 = 0.5787037037 1 0 91/216 = 0.4212962963 Attacker rolls 1 dice, defender rolls 2 dice: Attacker Defender Probability loses loses 0 1 55/216 = 0.2546296296 1 0 161/216 = 0.7453703704 Attacker rolls 1 dice, defender rolls 1 dice: Attacker Defender Probability loses loses 0 1 15/36 = 0.4166666667 1 0 21/36 = 0.5833333333 ---------------------8<------snip here--------8<-------------------- /* * riskdice.c -- prints Risk dice odds * * This program calculates probabilities for one roll of the dice in Risk. * For each possible number of dice that the attacker might roll, for each * possible number of dice that the defender might roll, this program * lists all the possible outcomes (number of armies lost by attacker * and defender) and the probability of each outcome. * * Copyright 1993 by David A. Karr. */ #define MAX_ATTACK 3 /* max # of dice attacker may roll */ #define MAX_DEFEND 2 /* max # of dice defender may roll */ #define MAX_DICE MAX_ATTACK + MAX_DEFEND void main() { int a; /* number of dice rolled by attacker */ int d; /* number of dice rolled by defender */ void calc(); for (a = MAX_ATTACK; a > 0; --a) { for (d = MAX_DEFEND; d > 0; --d) { calc( a, d ); } } } void calc( a_dice, d_dice ) /* * Purpose: Print odds for the given numbers of dice rolled */ int a_dice; /* number of dice rolled by attacker */ int d_dice; /* number of dice rolled by defender */ { int num_dice; /* total number of dice rolled */ int num_armies; /* # armies that will be lost by both sides, total */ int kill_count[MAX_DEFEND + 1]; /* entry [i] counts # of times attacker loses i armies */ int roll[MAX_DICE + 1]; /* holds one roll of the dice */ int a_roll[MAX_ATTACK]; /* holds attacker's dice */ int d_roll[MAX_DEFEND]; /* holds defender's dice */ int n; /* cursor into the arrays */ int num_lost; /* # of armies lost by the attacker */ int cases; /* total # of events counted */ void dsort(); /* * The method is pure brute force. roll[] is set successively to * all possible rolls of the total number of dice; for each roll * the number of armies lost by the attacker (the outcome) is * computed and the event is counted. * Since all the counted events are equiprobable, the count of each * outcome merely needs to be scaled down by the total count to * obtain the probability of that outcome. */ /* The number of armies at stake is min(a_dice, d_dice) */ num_armies = a_dice < d_dice ? a_dice : d_dice; /* initialize event counters */ for (n = 0; n <= num_armies; ++n) kill_count[n] = 0; /* * The roll[] array is treated as a funny odometer whose wheels each * go from 1 to 6. Each roll of the dice appears in roll[0] through * roll[num_dice - 1], starting with all 1s and counting up to all 6s. * roll[num_dice] is used to detect when the other digits have * finished a complete cycle (it is tripped when they go back to 1s). */ num_dice = a_dice + d_dice; for (n = 0; n <= num_dice; ++n) roll[n] = 1; while (roll[num_dice] == 1) { /* examine a new possible roll of the dice */ /* * copy attacker's and defender's dice so as not to disturb * the "odometer" reading. */ for (n = 0; n < a_dice; ++n) a_roll[n] = roll[n]; for (n = 0; n < d_dice; ++n) d_roll[n] = roll[n + a_dice]; /* * sort attacker's and defender's dice, highest first. */ dsort(a_roll, a_dice); dsort(d_roll, d_dice); /* * compare attacker's and defender's dice, count attacker's loss */ num_lost = 0; for (n = 0; n < num_armies; ++n) if (d_roll[n] >= a_roll[n]) ++num_lost; ++kill_count[num_lost]; /* * Find next roll values (bump the "odometer" up one tick). */ n = 0; roll[0] += 1; while (roll[n] > 6) { /* place [n] rolled over */ roll[n] = 1; /* Carry 1 into the next place (which may in turn roll over) */ ++n; roll[n] += 1; } } cases = 0; for (n = 0; n <= num_armies; ++n) cases += kill_count[n]; printf( "Attacker rolls %d dice, defender rolls %d dice:\n\n", a_dice, d_dice ); printf( "Attacker Defender Probability\n" ); printf( " loses loses\n" ); for (n = 0; n <= num_armies; ++n) printf( "%5d %5d %5d/%d = %12.10lf\n", n, num_armies - n, kill_count[n], cases, ((double) kill_count[n]) / ((double) cases) ); printf( "\n\n" ); } void dsort( array, length ) /* * Sort the given array in descending order. */ int *array; int length; /* number of slots in the array */ { int level, n, tmp; /* Use bubble sort since the array will be tiny in this application */ for (level = 0; level < length - 1; ++level) { /* * Slots [0] through [level - 1] are already "stable." * Bubble up the value that belongs in the [level] slot. */ for (n = length - 1; n > level; --n) { if (array[n - 1] < array[n]) { /* swap them */ tmp = array[n - 1]; array[n - 1] = array[n]; array[n] = tmp; } } } } ==> competition/games/rubiks/rubiks.clock.p <== How do you quickly solve Rubik's clock? ==> competition/games/rubiks/rubiks.clock.s <== Solution to Rubik's Clock The solution to Rubik's Clock is very simple and the clock can be "worked" in 10-20 seconds once the solution is known. In this description of how to solve the clock I will describe the different clocks as if they were on a map (e.g. N,NE,E,SE,S,SW,W,NW); this leaves the middle clock which I will just call M. To work the Rubik's clock choose one side to start from; it does not matter from which side you start. Your initial goal will be to align the N,S,E,W and M clocks. Use the following algorithm to do this: [1] Start with all buttons in the OUT position. [2] Choose a N,S,E,W clock that does not already have the same time as M (i.e. not aligned with M). [3] Push in the closest two buttons to the clock you chose in [2]. [4] Using the knobs that are farest away from the clock you chose in [2] rotate the knob until M and the clock you chose are aligned. The time on the clocks at this point does not matter. [5] Go back to [1] until N,S,E,W and M are in alignment. [6] At this point N,S,E,W and M should all have the same time. Make sure all buttons are out and rotate any knob until N,S,E,W and M are pointing to 12 oclock. Now turn the puzzle over and repeat steps [1]-[6] for this side. DO NOT turn any knobs other than the ones described in [1]-[6]. If you have done this correctly then on both sides of the puzzle N,S,E,W and M will all be pointing to 12. Now to align NE,SE,SW,NW. To finish the puzzle you only need to work from one side. Choose a side and use the following algorithm to align the corners: [1] Start with all buttons OUT on the side you're working from. [2] Choose a corner that is not aligned. [3] Press the button closest to that corner in. [4] Using any knob except for that corner's knob rotate all the clocks until they are in line with the corner clock. (Here "all the clocks" means N,S,E,W,M and any other clock that you have already aligned) There is no need at this point to return the clocks to 12 although if it is less confusing you can. Remember to return all buttons to their up position before you do so. [5] Return to [1] until all clocks are aligned. [6] With all buttons up rotate all the clocks to 12. ==> competition/games/rubiks/rubiks.cube.p <== What is known about bounds on solving Rubik's cube? ==> competition/games/rubiks/rubiks.cube.s <== The "official" world record was set by Minh Thai at the 1982 World Championships in Budapest Hungary, with a time of 22.95 seconds. Keep in mind mathematicians provided standardized dislocation patterns for the cubes to be randomized as much as possible. The fastest cube solvers from 19 different countries had 3 attempts each to solve the cube as quickly as possible. Minh and several others have unofficially solved the cube in times between 16 and 19 seconds. However, Minh averages around 25 to 26 seconds after 10 trials, and my best average of ten trials is about 27 seconds (although it is usually higher). Consider that in the World Championships 19 of the world's fastest cube solvers each solved the cube 3 times and no one solved the cube in less than 20 seconds... God's algorithm is the name given to an as yet (as far as I know) undiscovered method to solve the rubik's cube in the least number of moves; as opposed to using 'canned' moves. The known lower bound is 18 moves. This is established by looking at things backwards: suppose we can solve a position in N moves. Then by running the solution backwards, we can also go from the solved position to the position we started with in N moves. Now we count how many sequences of N moves there are from the starting position, making certain that we don't turn the same face twice in a row: N=0: 1 (empty) sequence; N=1: 18 sequences (6 faces can be turned, each in 3 different ways) N=2: 18*15 sequences (take any sequence of length 1, then turn any of the five faces which is not the last face turned, in any of 3 different ways); N=3: 18*15*15 sequences (take any sequence of length 2, then turn any of the five faces which is not the last face turned, in any of 3 different ways); : : N=i: 18*15^(i-1) sequences. So there are only 1 + 18 + 18*15 + 18*15^2 + ... + 18*15^(n-1) sequences of moves of length n or less. This sequence sums to (18/14)*(15^n - 1) + 1. Trying particular values of n, we find that there are about 8.4 * 10^18 sequences of length 16 or less, and about 1.3 times 10^20 sequences of length 17 or less. Since there are 2^10 * 3^7 * 8! * 12!, or about 4.3 * 10^19, possible positions of the cube, we see that there simply aren't enough sequences of length 16 or less to reach every position from the starting position. So not every position can be solved in 16 or less moves - i.e. some positions require at least 17 moves. This can be improved to 18 moves by being a bit more careful about counting sequences which produce the same position. To do this, note that if you turn one face and then turn the opposite face, you get exactly the same result as if you'd done the two moves in the opposite order. When counting the number of essentially different sequences of N moves, therefore, we can split into two cases: (a) Last two moves were not of opposite faces. All such sequences can be obtained by taking a sequence of length N-1, choosing one of the 4 faces which is neither the face which was last turned nor the face opposite it, and choosing one of 3 possible ways to turn it. (If N=1, so that the sequence of length N-1 is empty and doesn't have a last move, we can choose any of the 6 faces.) (b) Last two moves were of opposite faces. All such sequences can be obtained by taking a sequence of length N-2, choosing one of the 2 opposite face pairs that doesn't include the last face turned, and turning each of the two faces in this pair (3*3 possibilities for how it was turned). (If N=2, so that the sequence of length N-2 is empty and doesn't have a last move, we can choose any of the 3 opposite face pairs.) This gives us a recurrence relation for the number X_N of sequences of length N: N=0: X_0 = 1 (the empty sequence) N=1: X_1 = 18 * X_0 = 18 N=2: X_2 = 12 * X_1 + 27 * X_0 = 243 N=3: X_3 = 12 * X_2 + 18 * X_1 = 3240 : : N=i: X_i = 12 * X_(i-1) + 18 * X_(i-2) If you do the calculations, you find that X_0 + X_1 + X_2 + ... + X_17 is about 2.0 * 10^19. So there are fewer essentially different sequences of moves of length 17 or less than there are positions of the cube, and so some positions require at least 18 moves. The upper bound of 50 moves is I believe due to Morwen Thistlethwaite, who developed a technique to solve the cube in a maximum of 50 moves. It involved a descent through a chain of subgroups of the full cube group, starting with the full cube group and ending with the trivial subgroup (i.e. the one containing the solved position only). Each stage involves a careful examination of the cube, essentially to work out which coset of the target subgroup it is in, followed by a table look-up to find a sequence to put it into that subgroup. Needless to say, it was not a fast technique! But it was fascinating to watch, because for the first three quarters or so of the solution, you couldn't really see anything happening - i.e. the position continued to appear random! If I remember correctly, one of the final subgroups in the chain was the subgroup generated by all the double twists of the faces - so near the end of the solution, you would suddenly notice that each face only had two colours on it. A few moves more and the solution was complete. Completely different from most cube solutions, in which you gradually see order return to chaos: with Morwen's solution, the order only re-appeared in the last 10-15 moves. * Mark's Update/Comments ---------------------------------------------- * Despite some accounts of Thistlethwaite's method, it is possible to * follow the progression of his algorithm. Clearly after Stage 2 is * completed the L and R faces will have L and R colours on them only. * After Stage 3 is complete the characteristics of the square's group * is clearly visible on all 6 sides. It is harder to understand what * is accomplished in Stage 1. * * --------------------------------------------------------------------- With God's algorithm, of course, I would expect this effect to be even more pronounced: someone solving the cube with God's algorithm would probably look very much like a film of someone scrambling the cube, run in reverse! Finally, something I'd be curious to know in this context: consider the position in which every cubelet is in the right position, all the corner cubelets are in the correct orientation, and all the edge cubelets are "flipped" (i.e. the only change from the solved position is that every edge is flipped). What is the shortest sequence of moves known to get the cube into this position, or equivalently to solve it from this position? (I know of several sequences of 24 moves that do the trick.) * Mark's Update/Comments ---------------------------------------------- * * This is from my file cmoves.txt which includes the best known * sequences for interesting patterns: * * p3 12 flip R1 L1 D2 B3 L2 F2 R2 U3 D1 R3 D2 F3 B3 D3 F2 D3 (20) * R2 U3 F2 D3 * * --------------------------------------------------------------------- The reason I'm interested in this particular position: it is the unique element of the centre of the cube group. As a consequence, I vaguely suspect (I'd hardly like to call it a conjecture :-) it may lie "opposite" the solved position in the cube graph - i.e. the graph with a vertex for each position of the cube and edges connecting positions that can be transformed into each other with a single move. If this is the case, then it is a good candidate to require the maximum possible number of moves in God's algorithm. -- David Seal dseal@armltd.co.uk To my knowledge, no one has ever demonstrated a specific cube position that takes 15 moves to solve. Furthermore, the lower bound is known to be greater than 15, due to a simple proof. * --------------------------------------------------------------------- * Mark> Definitely sequences exist in the square's group of length 15 * > e.g. Antipode 2 R2 B2 D2 F2 D2 F2 T2 L2 T2 D2 F2 T2 L2 T2 B2 * --------------------------------------------------------------------- The way we know the lower bound is by working backwards counting how many positions we can reach in a small number of moves from the solved position. If this is less than 43,252,003,274,489,856,000 (the total number of positions of Rubik's cube) then you need more than that number of moves to reach the other positions of the cube. Therefore, those positions will require more moves to solve. The answer depends on what we consider a move. There are three common definitions. The most restrictive is the QF metric, in which only a quarter-turn of a face is allowed as a single move. More common is the HF metric, in which a half-turn of a face is also counted as a single move. The most generous is the HS metric, in which a quarter- turn or half-turn of a central slice is also counted as a single move. These metrics are sometimes called the 12-generator, 18-generator, and 27-generator metrics, respectively, for the number of primitive moves. The definition does not affect which positions you can get to, or even how you get there, only how many moves we count for it. The answer is that even in the HS metric, the lower bound is 16, because at most 17,508,850,688,971,332,784 positions can be reached within 15 HS moves. In the HF metric, the lower bound is 18, because at most 19,973,266,111,335,481,264 positions can be reached within 17 HF moves. And in the QT metric, the lower bound is 21, because at most 39,812,499,178,877,773,072 positions can be reached within 20 QT moves. -- jjfink@skcla.monsanto.com writes: Lately in this conference I've noted several messages related to Rubik's Cube and Square 1. I've been an avid cube fanatic since 1981 and I've been gathering cube information since. Around Feb. 1990 I started to produce the Domain of the Cube Newsletter, which focuses on Rubik's Cube and all the cube variants produced to date. I include notes on unproduced prototype cubes which don't even exist, patent information, cube history (and prehistory), computer simulations of puzzles, etc. I'm up to the 4th issue. Anyways, if you're interested in other puzzles of the scramble by rotation type you may be interested in DOTC. It's available free to anyone interested. I am especially interested in contributing articles for the newsletter, e.g. ideas for new variants, God's Algorithm. Anyone ever write a Magic Dodecahedron simulation for a computer? Drop me a SASE (say empire size) if you're interested in DOTC or if you would like to exchange notes on Rubik's Cube, Square 1 etc. I'm also interested in exchanging puzzle simulations, e.g. Rubik's Cube, Twisty Torus, NxNxN Simulations, etc, for Amiga and IBM computers. I've written several Rubik's Cube solving programs, and I'm trying to make the definitive puzzle solving engine. I'm also interested in AI programs for Rubik's Cube and the like. Ideal Toy put out the Rubik's Cube Newsletter, starting with issue #1 on May 1982. There were 4 issues in all. They are: #1, May 1982 #2, Aug 1982 #3, Winter 1983 #4, Aug 1983 There was another sort of magazine, published in several languages called Rubik's Logic and Fantasy in space. I believe there were 8 issues in all. Unfortunately I don't have any of these! I'm willing to buy these off anyone interesting in selling. I would like to get the originals if at all possible... I'm also interested in buying any books on the cube or related puzzles. In particular I am _very_ interested in obtaining the following: Cube Games Don Taylor, Leanne Rylands Official Solution to Alexander's Star Adam Alexander The Amazing Pyraminx Dr. Ronald Turner-Smith The Winning Solution Minh Thai The Winning Solution to Rubik's Revenge Minh Thai Simple Solutions to Cubic Puzzles James G. Nourse I'm also interested in buying puzzles of the mechanical type. I'm still missing the Pyraminx Star (basically a Pyraminx with more tips on it), Pyraminx Ball, and the Puck. If anyone out here is a fellow collector I'd like to hear from you. If you have a cube variant which you think is rare, or an idea for a cube variant we could swap notes. I'm in the middle of compiling an exhaustive library for computer simulations of puzzles. This includes simulations of all Uwe Meffert's puzzles which he prototyped but _never_ produced. In fact, I'm in the middle of working on a Pyraminx Hexagon solver. What? Never heard of it? Meffert did a lot of other puzzles which never were made. I invented some new "scramble by rotation" puzzles myself. My favourite creation is the Twisty Torus. It is a torus puzzle with segments (which slide around 360 degrees) with multiple rings around the circumference. The computer puzzle simulation library I'm forming will be described in depth in DOTC #4 (The Domain of the Cube Newsletter). So if you have any interesting computer puzzle programs please email me and tell me all about them! Also to the people interested in obtaining a subscription to DOTC, who are outside of Canada (which it seems is just about all of you!) please don't send U.S. or non-Canadian stamps (yeah, I know I said Self-Addressed Stamped Envelope before). Instead send me an international money order in Canadian funds for $6. I'll send you the first 4 issues (issue #4 is almost finished). Mark Longridge Address: 259 Thornton Rd N, Oshawa Ontario Canada, L1J 6T2 Email: mark.longridge@canrem.com One other thing, the six bucks is not for me to make any money. This is only to cover the cost of producing it and mailing it. I'm just trying to spread the word about DOTC and to encourage other mechanical puzzle lovers to share their ideas, books, programs and puzzles. Most of the programs I've written and/or collected are shareware for C64, Amiga and IBM. I have source for all my programs (all in C or Basic) and I am thinking of providing a disk with the 4th issue of DOTC. If the response is favourable I will continue to provide disks with DOTC. -- Mark Longridge writes: It may interest people to know that in the latest issue of "Cubism For Fun" % (# 28 that I just received yesterday) there is an article by Herbert Kociemba from Darmstadt. He describes a program that solves the cube. He states that until now he has found no configuration that required more than 21 turns to solve. He gives a 20 move manoeuvre to get at the "all edges flipped/ all corners twisted" position: DF^2U'B^2R^2B^2R^2LB'D'FD^2FB^2UF'RLU^2F' or in Varga's parlance: dofitabiribirilobadafodifobitofarolotifa Other things #28 contains are an analysis of Square 1, an article about triangular tilings by Martin Gardner, and a number of articles about other puzzles. -- % CFF is a newsletter published by the Dutch Cubusts Club NKC. Secretary: Anneke Treep Postbus 8295 6710 AG Ede The Netherlands Membership fee for 1992 is DFL 20 (about$ 11). -- -- dik t. winter ~References: Mathematical Papers ------------------- Rubik's Revenge: The Group Theoretical Solution Mogens Esrom Larsen A.M.M. Vol. 92 No. 6, June-July 1985, pages 381-390 Rubik's Groups E. C. Turner & K. F. Gold, American Mathematical Monthly, vol. 92 No. 9 November 1985, pp. 617-629. Cubelike Puzzles - What Are They and How Do You Solve Them? J.A. Eidswick A.M.M. Vol. 93 No. 3 March 1986, pp 157-176 The Slice Group in Rubik's Cube, David Hecker, Ranan Banerji Mathematics Magazine, Vol. 58 No. 4 Sept 1985 The Group of the Hungarian Magic Cube Chris Rowley Proceedings of the First Western Austrialian Conference on Algebra, 1982 Books ----- Rubik's Cubic Compendium Erno Rubik, Tamas Varga, et al, Edited by David Singmaster Oxford University Press, 1987 Enslow Publishers Inc ==> competition/games/rubiks/rubiks.magic.p <== How do you solve Rubik's Magic? ==> competition/games/rubiks/rubiks.magic.s <== The solution is in a 3x3 grid with a corner missing. +---+---+---+ +---+---+---+---+ | 3 | 5 | 7 | | 1 | 3 | 5 | 7 | +---+---+---+ +---+---+---+---+ | 1 | 6 | 8 | | 2 | 4 | 6 | 8 | +---+---+---+ +---+---+---+---+ | 2 | 4 | Original Shape +---+---+ To get the 2x4 "standard" shape into this shape, follow this: 1. Lie it flat in front of you (4 going across). 2. Flip the pair (1,2) up and over on top of (3,4). 3. Flip the ONE square (2) up and over (1). [Note: if step 3 won't go, start over, but flip the entire original shape over (exposing the back).] 4. Flip the pair (2,4) up and over on top of (5,6). 5. Flip the pair (1,2) up and toward you on top of (blank,4). 6. Flip the ONE square (2) up and left on top of (1). 7. Flip the pair (2,4) up and toward you. Your puzzle won't be completely solved, but this is how to get the shape. Notice that 3,5,6,7,8 don't move. ==> competition/games/scrabble.p <== What are some exceptional Scrabble Brand Crossword Game (TM) games? ==> competition/games/scrabble.s <== The shortest Scrabble game: The Scrabble Players News, Vol. XI No. 49, June 1983, contributed by Kyle Corbin of Raleigh, NC: [J] J U S S O X [X]U which can be done in 4 moves, JUS, SOX, [J]US, and [X]U. In SPN Vol. XI, No. 52, December 1983, Alan Frank presented what he claimed is the shortest game where no blanks are used, also four moves: C WUD CUKES DEY S This was followed in SPN, Vol. XII No. 54, April 1984, by Terry Davis of Glasgow, KY: V V O[X] [X]U, which is three moves. He noted that the use of two blanks prevents such plays as VOLVOX. Unfortunately, it doesn't prevent SONOVOX. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Record for the highest Scrabble score in a single turn (in a legal position): According to the Scrabble Players Newspaper (since renamed to Scrabble Players News) issue 44, p13, the highest score for one turn yet discovered, using the Official Scrabble Players Dictionary, 1st ed. (the 2nd edition is now in use in club and tournament play) and the Websters 9th New Collegiate Dictionary, was the following: d i s e q u i l i b r a t e D . . . . . . . e . . . . . . e . . . . . . . e . . . . . o m r a d i o a u t o g r a p(h)Y . . . . . . . . . . . w a s T . . . . . . . . . . b e . . h . . . . . . . . . . a . . g o . . . c o n j u n c t i v a L . . . . . . . . . . . . . n o . . . . . . . f i n i k i n G . . . . . . . a . . . (l) e i . . . . . . . d . s p e l t Z . . . . . . w e . . . . . . e . . . . . . r . . . . . . o r m e t h o x y f l u r a n e S for 1682 points. According to the May 1986 issue of GAMES, the highest known score achievable in one turn is 1,962 points. The word is BENZOXYCAMPHORS formed across the three triple-word scores on the bottom of the board. Apparently it was discovered by Darryl Francis, Ron Jerome, and Jeff Grant. As for other Scrabble trivia, the highest-scoring first move based on the Official Scrabble Players Dictionary is 120 points, with the words JUKEBOX, QUIZZED, SQUEEZE, or ZYMURGY. If Funk & Wagnall's New Standard Dictionary is used then ZYXOMMA, worth 130 points, can be formed. The highest-scoring game, based on Webster's Second and Third and on the Oxford English Dictionary, was devised by Ron Jerome and Ralph Beaman and totalled 4,142 points for the two players. The highest-scoring words in the game were BENZOXYCAMPHORS, VELVETEEN, and JACKPUDDINGHOOD. The following example of a SCRABBLE game produced a score of 2448 for one player and 1175 for the final word. It is taken from _Beyond Language_ (1967) by Dmitri Borgman (pp. 217-218). He credits this solution to Mrs. Josefa H. Byrne of San Francisco and implies that all words can be found in _Webster's Second Edition_. The two large words (multiplied by 27 as they span 3 triple word scores) are ZOOPSYCHOLOGIST (a psychologist who treats animals rather than humans) and PREJUDICATENESS (the condition or state of being decided beforehand). The asterisks (*) represent the blank tiles. (Please excuse any typo's). Board Player1 Player2 Z O O P S Y C H O L O G I S T ABILITY 76 ERI, YE 9 O N H A U R O W MAN, MI 10 EN 2 * R I B R O V E I FEN, FUN 14 MANIA 7 L T I K E G TABU 12 RIB 6 O L NEXT 11 AM 4 G I AX 9 END 6 I T IT, TIKE 10 LURE 6 * Y E LEND, LOGIC*AL 79 OO*LOGICAL 8 A R FUND, JUD 27 ATE, MA 7 L E N D M I ROVE 14 LO 2 E A Q DARE, DE 13 ES, ES, RE 6 W A X F E N U RE, ROW 14 IRE, IS, SO 7 E T A B U I A DARED, QUAD 22 ON 4 E N A M D A R E D WAX, WEE 27 WIG 9 P R E J U D I C A T E N E S S CHIT, HA 14 ON 2 PREJUDICATENESS, AN, MANIAC, QUADS, WEEP 911 OOP 8 ZOOPSYCHOLOGIST, HABILITY, TWIG, ZOOLOGICAL 1175 -------------------------------------- Total: 2438 93 F, N, V, T in loser's hand: +10 -10 -------------------------------------- Final Score: 2448 83 --------------------------------------------------------------------------- It is possible to form the following 14 7-letter OSPD words from the non-blank tiles: HUMANLY FATUOUS AMAZING EERIEST ROOFING TOILERS QUIXOTE JEWELRY CAPABLE PREVIEW BIDDERS HACKING OVATION DONATED ==> competition/games/set.p <== What is the size of the largest collection of cards from which NO "set" can be selected ? ==> competition/games/set.s <== I can get 20: 1ROL 1GDL 1GDM 1GOM 1GSL 1PDH 1PDM 1POL 1POM 2RSL 2PDM 3ROL 3ROM 3RSL 3RSH 3GDM 3GOL 3GSL 3GSM 3POM This collection of 20 is a local maximum. The small C progam shown below was used to check for all possible extensions to a collection of 21. Of course this leaves open the question whether there exists a completely different collection of 21 from which no "set" can be selected. -- Gene Miller ------- C Program enclosed ------- #define N 21 static int data[N][4]= { 1, 1, 2, 1, /* 00 */ 1, 2, 1, 1, /* 01 */ 1, 2, 1, 2, /* 02 */ 1, 2, 2, 2, /* 03 */ 1, 2, 3, 1, /* 04 */ 1, 3, 1, 3, /* 05 */ 1, 3, 1, 2, /* 06 */ 1, 3, 2, 1, /* 07 */ 1, 3, 2, 2, /* 08 */ 2, 1, 3, 1, /* 09 */ 2, 3, 1, 2, /* 10 */ 3, 1, 2, 1, /* 11 */ 3, 1, 2, 2, /* 12 */ 3, 1, 3, 1, /* 13 */ 3, 1, 3, 3, /* 14 */ 3, 2, 1, 2, /* 15 */ 3, 2, 2, 1, /* 16 */ 3, 2, 3, 1, /* 17 */ 3, 2, 3, 2, /* 18 */ 3, 3, 2, 2, /* 19 */ 0, 0, 0, 0 /* 20 */ /* leave space for Nth combo */ }; main() { int x, y, z, w; for (x=1; x<=3; x++) /* check all combos */ for (y=1; y<=3; y++) for (z=1; z<=3; z++) for (w=1; w<=3; w++) printf ("%d %d %d %d -> sets=%d\n", x, y, z, w, check (x, y, z, w)); } int check(x,y,z,w) int x, y, z, w; { int i,j,k,m; int errors, sets; for (i=0; i competition/games/soma.p <== What is the solution to Soma Cubes? ==> competition/games/soma.s <== The soma cube is dissected in excruciating detail in volume 2 of "Winning Ways" by Conway, Berlekamp and Guy, in the same chapter as the excruciatingly detailed dissection of Rubik's Cube. ==> competition/games/square-1.p <== Does anyone have any hints on how to solve the Square-1 puzzle? ==> competition/games/square-1.s <== SHAPES 1. There are 29 different shapes for a side, counting reflections: 1 with 6 corners, 0 edges 3 with 5 corners, 2 edges 10 with 4 corners, 4 edges 10 with 3 corners, 6 edges 5 with 2 corners, 8 edges 2. Naturally, a surplus of corners on one side must be compensated by a deficit of corners on the other side. Thus there are 1*5 + 3*10 + C(10,2) = 5 + 30 + 55 = 90 distinct combinations of shapes, not counting the middle layer. 3. You can reach two squares from any other shape in at most 7 transforms, where a transform consists of (1) optionally twisting the top, (2) optionally twisting the bottom, and (3) flipping. 4. Each transform toggles the middle layer between Square and Kite, so you may need 8 transforms to reach a perfect cube. 5. The shapes with 4 corners and 4 edges on each side fall into four mutually separated classes. Side shapes can be assigned values: 0: Square, Mushroom, and Shield; 1: Left Fist and Left Paw; 2: Scallop, Kite, and Barrel; 3. Right Fist and Right Paw. The top and bottom's sum or difference, depending on how you look at them, is a constant. Notice that the side shapes with bilateral symmetry are those with even values. 6. To change this constant, and in particular to make it zero, you must attain a position that does not have 4 corners and 4 edges on each side. Almost any such position will do, but returning to 4 corners and 4 edges with the right constant is left to your ingenuity. 7. If the top and bottom are Squares but the middle is a Kite, just flip with the top and bottom 30deg out of phase and you will get a cube. COLORS 1. I do not know the most efficient way to restore the colors. What follows is my own suboptimal method. All flips keep the yellow stripe steady and flip the blue stripe. 2. You can permute the corners without changing the edges, so first get the edges right, then the corners. 3. This transformation sends the right top edge to the bottom and the left bottom edge to the top, leaving the other edges on the same side as they started: Twist top 30deg cl, flip, twist top 30deg ccl, twist bottom 150deg cl, flip, twist bottom 30deg cl, twist top 120deg cl, flip, twist top 30deg ccl, twist bottom 150deg cl, flip, twist bottom 30deg cl. Cl and ccl are defined looking directly at the face. With this transformation you can eventually get all the white edges on top. 4. Check the parity of the edge sequence on each side. If either is wrong, you need to fix it. Sorry -- I don't know how! (See any standard reference on combinatorics for an explanation of parity.) 5. The following transformation cyclically permutes ccl all the top edges but the right one and cl all the bottom edges but the left one. Apply the transformation in 3., and turn the whole cube 180deg. Repeat. This is a useful transformation, though not a cure-all. 6. Varying the transformation in 3. with other twists will produce other results. 7. The following transformation changes a cube into a Comet and Star: Flip to get Kite and Kite. Twist top and bottom cl 90deg and flip to get Barrel and Barrel. Twist top cl 30 and bottom cl 60 and flip to get Scallop and Scallop. Twist top cl 60 and bottom cl 120 and flip to get Comet and Star. The virtue of the Star is that it contains only corners, so that you can permute the corners without altering the edges. 8. To reach a Lemon and Star instead, replace the final bottom cl 120 with a bottom cl 60. In both these transformation the Star is on the bottom. 9. The following transformation cyclically permutes all but the bottom left rear. It sends the top left front to the bottom, and the bottom left front to the top. Go to Comet and Star. Twist star cl 60. Go to Lemon and Star -- you need not return all the way to the cube, but do it if you're unsure of yourself by following 7 backwards. Twist star cl 60. Return to cube by following 8 backwards. With this transformation you should be able to get all the white corners on top. 10. Check the parity of the corner sequences on both sides. If the bottom parity is wrong, here's how to fix it: Go to Lemon and Star. The colors on the Star will run WWGWWG. Twist it 180 and return to cube. 11. If the top parity is wrong, do the same thing, except that when you go from Scallop and Scallop to Lemon and Star, twist the top and bottom ccl instead of cl. The colors on the Star should now run GGWGGW. 12. Once the parity is right on both sides, the basic method is to go to Comet and Star, twist the star 120 cl (it will be WGWGWG), return to cube, twist one or both sides, go to Comet and Star, undo the star twist, return to cube, undo the side twists. With no side twists, this does nothing. If you twist the top, you will permute the top corners. If you twist the bottom, you will permute the bottom corners. Eventually you will get both the top and the bottom right. Don't forget to undo the side twists -- you need to have the edges in the right places. Happy twisting.... -- Col. G. L. Sicherman gls@windmill.att.COM ==> competition/games/think.and.jump.p <== THINK & JUMP: FIRST THINK, THEN JUMP UNTIL YOU ARE LEFT WITH ONE PEG! O - O O - O / \ / \ / \ / \ O---O---O---O---O BOARD DESCRIPTION: To the right is a model of \ / \ / \ / \ / the Think & Jump board. The O---O---O---O---O---O O's represent holes which / \ / \ / \ / \ / \ / \ contain pegs. O---O---O---O---O---O---O \ / \ / \ / \ / \ / \ / O---O---O---O---O---O DIRECTIONS: To play this brain teaser, you begin / \ / \ / \ / \ by removing the center peg. Then, O---O---O---O---O moving any direction in the grid, \ / \ / \ / \ / jump over one peg at a time, O - O O - O removing the jumped peg - until only one peg is left. It's harder then it looks. But it's more fun than you can imagine. SKILL CHART: 10 pegs left - getting better 5 pegs left - true talent 1 peg left - you're a genius Manufactured by Pressman Toy Corporation, NY, NY. ==> competition/games/think.and.jump.s <== Three-color the board in the obvious way. The initial configuration has 12 of each color, and each jump changes the parity of all three colors. Thus, it is impossible to achieve any position where the colors do not have the same parity; in particular, (1,0,0). If you remove the requirement that the initially-empty cell must be at the center, the game becomes solvable. The demonstration is left as an exercise. Karl Heuer rutgers!harvard!ima!haddock!karl karl@haddock.ima.isc.com Here is one way of reducing Think & Jump to two pegs. Long simplifies Balsley's scintillating snowflake solution: 1 U-S A - B C - D 2 H-U / \ / \ / \ / \ 3 V-T E---F---G---H---I 4 S-H \ / \ / \ / \ / 5 D-M J---K---L---M---N---O 6 F-S / \ / \ / \ / \ / \ / \ 7 Q-F P---Q---R---S---T---U---V 8 A-L \ / \ / \ / \ / \ / \ / 9 S-Q W---X---Y---Z---a---b 10 P-R / \ / \ / \ / \ 11 Z-N c---d---e---f---g 12 Y-K \ / \ / \ / \ / 13 h-Y h - i j - k 14 k-Z The board should now be in the snowflake pattern, i.e. look like o - * * - o / \ / \ / \ / \ *---o---*---o---* \ / \ / \ / \ / *---*---*---*---*---* / \ / \ / \ / \ / \ / \ o---o---o---o---o---o---o \ / \ / \ / \ / \ / \ / *---*---*---*---*---* / \ / \ / \ / \ *---o---*---o---* \ / \ / \ / \ / o - * * - o where o is empty and * is a peg. The top and bottom can now be reduced to single pegs individually. For example, we could continue 15 g-T 16 Y-a 17 i-Z 18 T-e 19 j-Y 20 b-Z 21 c-R 22 Z-X 23 W-Y 24 R-e which finishes the bottom. The top can be done in a similar manner. -- Chris Long ==> competition/games/tictactoe.p <== In random tic-tac-toe, what is the probability that the first mover wins? ==> competition/games/tictactoe.s <== Count cases. First assume that the game goes on even after a win. (Later figure out who won if each player gets a row of three.) Then there are 9!/5!4! possible final boards, of which 8*6!/2!4! - 2*6*4!/0!4! - 3*3*4!/0!4! - 1 = 98 have a row of three Xs. The first term is 8 rows times (6 choose 2) ways to put down the remaining 2 Xs. The second term is the number of ways X can have a diagonal row plus a horizontal or vertical row. The third term is the number of ways X can have a vertical and a horizontal row, and the 4th term is the number of ways X can have two diagonal rows. All the two-row configurations must be subtracted to avoid double-counting. There are 8*6!/1!5! = 48 ways O can get a row. There is no double- counting problem since only 4 Os are on the final board. There are 6*2*3!/2!1! = 36 ways that both players can have a row. (6 possible rows for X, each leaving 2 possible rows for O and (3 choose 2) ways to arrange the remaining row.) These cases need further consideration. There are 98 - 36 = 62 ways X can have a row but not O. There are 48 - 36 = 12 ways O can have a row but not X. There are 126 - 36 - 62 - 12 = 16 ways the game can be a tie. Now consider the 36 configurations in which each player has a row. Each such can be achieved in 5!4! = 2880 orders. There are 3*4!4! = 1728 ways that X's last move completes his row. In these cases O wins. There are 2*3*3!3! = 216 ways that Xs fourth move completes his row and Os row is already done in three moves. In these cases O also wins. Altogether, O wins 1728 + 216 = 1944 out of 2880 times in each of these 36 configurations. X wins the other 936 out of 2880. Altogether, the probability of X winning is ( 62 + 36*(936/2880) ) / 126. win: 737 / 1260 ( 0.5849206... ) lose: 121 / 420 ( 0.2880952... ) draw: 8 / 63 ( 0.1269841... ) The computer output below agress with this analysis. 1000000 games: won 584865, lost 288240, tied 126895 Instead, how about just methodically having the program play every possible game, tallying up who wins? Wonderful idea, especially since there are only 9! ~ 1/3 million possible games. Of course some are identical because they end in fewer than 8 moves. It is clear that these should be counted multiple times since they are more probable than games that go longer. The result: 362880 games: won 212256, lost 104544, tied 46080 #include int board[9]; int N, move, won, lost, tied; int perm[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; int rows[8][3] = { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 } }; main() { do { bzero((char *)board, sizeof board); for ( move=0; move<9; move++ ) { board[perm[move]] = (move&1) ? 4 : 1; if ( move >= 4 && over() ) break; } if ( move == 9 ) tied++; #ifdef DEBUG printf("%1d%1d%1d\n%1d%1d%1d w %d, l %d, t %d\n%1d%1d%1d\n\n", board[0], board[1], board[2], board[3], board[4], board[5], won, lost, tied, board[6], board[7], board[8]); #endif N++; } while ( nextperm(perm, 9) ); printf("%d games: won %d, lost %d, tied %d\n", N, won, lost, tied); exit(0); } int s; int *row; over() { for ( row=rows[0]; row= 0 && c[i] >= c[i+1] ) i--; if ( i < 0 ) return 0; while ( c[j] <= c[i] ) j--; t = c[i]; c[i] = c[j]; c[j] = t; i++; j = n-1; while ( i < j ) { t = c[i]; c[i] = c[j]; c[j] = t; i++; j--; } return 1; } ==> competition/tests/analogies/long.p <== 1. Host : Guest :: Cynophobia : ? 2. Mountain : Plain :: Acrocephalic : ? 3. Lover : Believer :: Philofelist : ? 4. 4 : 6 :: Bumblebee : ? 5. 2 : 1 :: Major : ? 6. 1 : 24 :: Group : ? 7. 4 : 64 :: Crotchet : ? 8. Last : First :: Grave : ? 9. 7 : 9 :: Throne : ? 10. Pride : Hatred :: Beelzebub : ? 11. Dollar : Bond :: Grant : ? 12. Ek : Sankh :: 1 : ? ==> competition/tests/analogies/long.s <== 1. Lyssophobia Cynophobia is the fear of dogs; lyssophobia is the fear of rabies. As Rodney Adams pointed out, a word meaning the fear of fleas would be even better, but I've been unable to locate such a word (although surely one must exists). 2. Homalocephalic Acrocephalic is having a pointed head; homalocephalic is having a flat head. Rodney Adamas suggested "planoccipital", but on checking this apparently refers to having a flat back of the skull, so he only gets partial credit. 3. Galeanthropist A philofelist is a cat-lover (also commonly called an ailurophile); a galeanthropist is a person who believes they are a cat. 4. Blue Bird A Camp Fire Girl who is 4 is in the Bumblebee Club; a Campfire Girl who is 6 in the Blue Bird Club. I should have had "4 or 5" instead of "4" to remove ambiguity (e.g. Mark Brader suggested "triplane"). 5. Brigadier A 2-star general in the army is a major general; a 1-star general in the army is a brigadier general. 6. Field Army Army groupings; there are 24 "groups" in a "field army". 7. Hemidemisemiquaver A crotchet is a quarter-note; a hemidemisemiquaver is a sixty-fourth note. Rodney Adams and Mark Brader both got this. 8. Prestissimo In music prestissimo means extremely fast; grave means very slow to the point of solemnity. This question was poorly worded (I received both "womb" and "cradle" as answers). 9. Seraph In the ninefold hierarchy of angels, a throne ranks 7th and a seraph 9th (9th being most powerful). Rodney Adams got this one. 10. Sonneillon In Father Sebastien Machaelis's (one of the more famous exorcists) hierarchy of devils, Beelzebub is responsible for pride, Sonneillon for hatred. 11. Roosevelt Grant is on the $50 bill; Roosevelt on the $50 savings bond. 12. 10^14 Ek is 1 in Hindi; sankh is 10^14 (one hundred quadrillion). -- Chris Long, 265 Old York Rd., Bridgewater, NJ 08807-2618 ==> competition/tests/analogies/pomfrit.p <== 1. NATURAL: ARTIFICIAL :: ANKYLOSIS: ? 2. RESCUE FROM CHOKING ON FOOD, etc.: HEIMLICH :: ADJUSTING MIDDLE EAR PRESSUR E: ? 3. LYING ON OATH: PERJURY :: INFLUENCING A JURY: ? 4. RECTANGLE: ELLIPSE :: MERCATOR: ? 5. CLOSED: CLEISTOGAMY :: OPEN: ? 6. FO'C'SLE: SYNCOPE :: TH'ARMY: ? 7. FILMS: OSCAR :: MYSTERY NOVELS: ? 8. QUANTITATIVE DATA: STATISTICS :: HUMAN SETTLEMENTS: ? 9. 7: 19 : : SEPTIMAL: ? 10. 3 TO 2: SESQUILATERAL :: 7 TO 5: ? 11. SICILY: JAPAN :: MAFIA: ? 12. CELEBRITIES: SYCOPHANTIC :: ANCESTORS: ? 13. 95: 98 :: VENITE: ? 14. MINCES: EYES :: PORKIES: ? 15. POSTAGE STAMPS: PHILATELIST: MATCHBOX LABELS: ? 16. MALE: FEMALE :: ARRENOTOKY: ? 17 TAILOR: DYER :: SARTORIAL: ? 18. HERMES: BACCHUS :: CADUCEUS: ? 19. 2823: 5331 :: ELEPHANT: ? 20. CENTRE OF GRAVITY: BARYCENTRIC :: ROTARY MOTION: ? 21. CALIFORNIA: EUREKA :: NEW YOKK: ? 22. MARRIAGE: DIGAMY :: COMING OF CHRIST: ? 23. 6: 5 :: PARR: ? 24. GROUP: INDIVIDUAL :: PHYLOGENESIS: ? 25. 12: 11 :: EPSOM: ? ==> competition/tests/analogies/pomfrit.s <== 1. ARTHRODESIS 2. VALSALVA 3. EMBRACERY 4. MOLLWEIDE 5. CHASMOGAMY 6. SYNAL(O)EPHA 7. EDGAR 8. EKISTICS 9. DECENNOVAL 10. SUPERBIQUINTAL 11. YAKUZA 12. FILIOPETISTIC 13. CANTATE 14. LIES 15. PHILLUMENIST 16. THELYTOKY 17. TINCTORIAL 18. THYRSUS 19. ANTIQUARIAN 20. TROCHILIC 21. EXCELSIOR (mottos) 22. PAROUSIA 23. HOWARD (wives of Henry VIII) 24. ONTOGENESIS 25. GLAUBER (salts) ==> competition/tests/analogies/quest.p <== 1. Mother: Maternal :: Stepmother: ? 2. Club: Axe :: Claviform: ? 3. Cook Food: Pressure Cooker :: Kill Germs: ? 4. Water: Air :: Hydraulic: ? 5. Prediction: Dirac :: Proof: ? 6. Raised: Sunken :: Cameo: ? 7. 1: 14 :: Pound: ? 8. Malay: Amok :: Eskimo Women: ? 9. Sexual Intercourse: A Virgin :: Bearing Children: ? 10. Jaundice, Vomiting, Hemorrhages: Syndrome :: Jaundice: ? 11. Guitar: Cello :: Segovia: ? 12. Bars: Leaves :: Eagle: ? 13. Roll: Aileron :: Yaw: ? 14. 100: Century :: 10,000: ? 15. Surface: Figure :: Mobius: ? 16. Logic: Philosophy :: To Know Without Conscious Reasoning: ? 17. Alive: Parasite :: Dead: ? 18. Sea: Land :: Strait: ? 19. Moses: Fluvial :: Noah: ? 20. Remnant: Whole :: Meteorite: ? 21. Opossum, Kangaroo, Wombat: Marsupial :: Salmon, Sturgeon, Shad: ? 22. Twain/Clemens: Allonym :: White House/President: ? 23. Sculptor: Judoka :: Fine: ? 24. Dependent: Independent :: Plankton: ? 25. Matthew, Mark, Luke, John: Gospels :: Joshua-Malachi: ? 26. Luminous Flux: Lumen :: Sound Absorption: ? 27. 2: 3 :: He: ? 28. Growth: Temperature :: Pituitary Gland: ? 29. Spider: Arachnoidism :: Snake: ? 30. Epigram: Anthology :: Foreign Passages: ? 31. Pathogen: Thermometer :: Lethal Wave: ? 32. Russia: Balalaika :: India: ? 33. Involuntary: Sternutatory :: Voluntary: ? 34. Unusual Hunger: Bulimia :: Hunger for the Unusual: ? 35. Blind: Stag :: Tiresias: ? 36. River: Fluvial :: Rain: ? 37. Country: City :: Tariff: ? 38. $/Dollar: Logogram :: 3, 5, 14, 20/Cent: ? 39. Lung Capacity: Spirometer :: Arterial Pressure: ? 40. Gold: Ductile :: Ceramic: ? 41. 7: 8 :: Uranium: ? 42. Judaism: Messiah :: Islam: ? 43. Sight: Amaurosis :: Smell: ? 44. Oceans: Cousteau :: Close Encounters of the Third Kind: ? 45. Diamond/Kimberlite: Perimorph :: Fungus/Oak: ? 46. Compulsion to Pull One's Hair: Trichotillomania :: Imagine Oneself As a Beast: ? 47. Cross: Neutralism :: Hexagram: ? 48. Wing: Tail :: Fuselage: ? 49. Bell: Loud :: Speak: ? 50. Benevolence: Beg :: Philanthropist: ? 51. 10: Decimal :: 20: ? 52. Five-sided Polyhedron: Pentahedron :: ? Faces of Parallelepiped Bounded by a Square: ? 53. Motor: Helicopter :: Airflow: ? 54. Man: Ant :: Barter: ? 55. United States: Soviet Union :: Cubism: ? 56. State: Stipend :: Church: ? 57. Motorcycle: Bicycle :: Motordrome: ? 58. Transparent: Porous :: Obsidian: ? 59. pi*r^2*h: 1/3*pi*r^2*h :: Cylinder: ? ==> competition/tests/analogies/quest.s <== Annotated solutions. If there is more than one word that fits the analogy, we list the best word first. Goodness of fit considers many factors, such as parallel spelling, pronunciation or etymology. In general, a word that occurs in Merriam-Webster's Third New International Dictionary is superior to one that does not. If we are unsure of the answer, we mark it with a question mark. Most of these answers are drawn from Herbert M. Baus, _The Master Crossword Puzzle Dictionary_, Doubleday, New York, 1981. The notation in parentheses refers to the heading and subheading, if any, in Baus. 1. Mother: Maternal :: Stepmother: Novercal (STEPMOTHER, pert.) 2. Club: Axe :: Claviform: Dolabriform, Securiform (AXE, -shaped) "Claviform" is from Latin "clava" for "club"; "securiform" is from Latin "secura" for "axe"; "dolabriform" is from Latin "dolabra" for "to hit with an axe." Thus "securiform" has the more parallel etymology. However, only "dolabriform" occurs in Merriam-Webster's Third New International Dictionary. 3. Cook Food: Pressure Cooker :: Kill Germs: Autoclave (PRESSURE, cooker) 4. Water: Air :: Hydraulic: Pneumatic (AIR, pert.) 5. Prediction: Dirac :: Proof: Anderson (POSITRON, discoverer) 6. Raised: Sunken :: Cameo: Intaglio (GEM, carved) 7. 1: 14 :: Pound: Stone (ENGLAND, weight) 8. Malay: Amok :: Eskimo Women: Piblokto (ESKIMO, hysteria) 9. Sexual Intercourse: A Virgin :: Bearing Children: A Nullipara 10. Jaundice, Vomiting, Hemorrhages: Syndrome :: Jaundice: Symptom (EVIDENCE) 11. Guitar: Cello :: Segovia: Casals (SPAIN, cellist) 12. Bars: Leaves :: Eagle: Stars (INSIGNIA) 13. Roll: Aileron :: Yaw: Rudder (AIRCRAFT, part) 14. 100: Century :: 10,000: Myriad, Banzai? (NUMBER) "Century" usually refers to one hundred years, while "myriad" refers to 10,000 things, but "century" can also mean 100 things. "Banzai" is Japanese for 10,000 years. 15. Surface: Figure :: Mobius: Klein 16. Logic: Philosophy :: To Know Without Conscious Reasoning: Theosophy (MYSTICISM) There are many schools of philosophy that tout the possibility of knowledge without conscious reasoning (e.g., intuitionism). "Theosophy" is closest in form to the word "philosophy." 17. Alive: Parasite :: Dead: Saprophyte (SCAVENGER) 18. Sea: Land :: Strait: Isthmus (CONNECTION) 19. Moses: Fluvial :: Noah: Diluvial (FLOOD, pert.) 20. Remnant: Whole :: Meteorite: Meteoroid? (METEOR) A meteorite is the remains of a meteoroid after it has partially burned up in the atmosphere. The original meteoroid may have come from an asteroid, comet, dust cloud, dark matter, supernova, interstellar collision or other sources as yet unknown. 21. Opossum, Kangaroo, Wombat: Marsupial :: Salmon, Sturgeon, Shad: Andromous (SALMON) 22. Twain/Clemens: Allonym :: White House/President: Metonym (FIGURE, of speech ) 23. Sculptor: Judoka :: Fine: Martial (SELF, -defense) 24. Dependent: Independent :: Plankton: Nekton (ANIMAL, free-swimming) 25. Matthew, Mark, Luke, John: Gospels :: Joshua-Malachi: Nebiim (HEBREW, bible books) 26. Luminous Flux: Lumen :: Sound Absorption: Sabin (SOUND, absorption unit) 27. 2: 3 :: He: Li (ELEMENT) 28. Growth: Temperature :: Pituitary Gland: Hypothalamus (BRAIN, part) 29. Spider: Arachnoidism :: Snake: Ophidism, Ophidiasis, Ophiotoxemia None of these words is in Webster's Third. 30. Epigram: Anthology :: Foreign Passages: Chrestomathy, Delectus (COLLECTION) These words are equally good answers. 31. Pathogen: Thermometer :: Lethal Wave: Dosimeter? (X-RAY, measurement) What does "lethal wave" refer to? If it is radiation, then a dosimeter measures the dose, not the effect, as does a thermometer. 32. Russia: Balalaika :: India: Sitar, Sarod (INDIA, musical instrument) Both are guitar-like instruments (lutes) native to India. 33. Involuntary: Sternutatory :: Voluntary: Expectorant? (SPIT) A better word would be an agent that tends to cause snorting or exsufflation, which is the voluntary, rapid expulsion of air from the lungs. 34. Unusual Hunger: Bulimia :: Hunger for the Unusual: Allotriophagy, Pica (HUNGER, unusual) These words are synonyms. 35. Blind: Stag :: Tiresias: Actaeon (STAG, changed to) 36. River: Fluvial :: Rain: Pluvial (RAIN, part.) 37. Country: City :: Tariff: Octroi (TAX, kind) 38. $/Dollar: Logogram :: 3, 5, 14, 20/Cent: Cryptogram (CODE) 39. Lung Capacity: Spirometer :: Arterial Pressure: Sphygmomanometer (PULSE, measurer) 40. Gold: Ductile :: Ceramic: Fictile (CLAY, made of) 41. 7: 8 :: Uranium: Neptunium (ELEMENT, chemical) 42. Judaism: Messiah :: Islam: Mahdi (MOHAMMEDAN, messiah) 43. Sight: Amaurosis :: Smell: Anosmia, Anosphresia (SMELL, loss) These words are synonyms. 44. Oceans: Cousteau :: Close Encounters of the Third Kind: Spielburg, Truffaut Steven Spielburg was the person most responsible for the movie; Francois Truffaut was a French person appearing in the movie. 45. Diamond/Kimberlite: Perimorph :: Fungus/Oak: Endophyte, Endoparasite (PARASITE, plant) An endoparasite is parasitic, while an endophyte may not be. Which answer is best depends upon the kind of fungus. 46. Compulsion to Pull One's Hair: Trichotillomania :: Imagine Oneself As a Beast: Zoanthropy, Lycanthropy Neither word is exactly right: "zoanthropy" means imagining oneself to be an animal, while "lycanthropy" means imagining oneself to be a wolf. 47. Cross: Neutralism :: Hexagram: Zionism (ISRAEL, doctrine) 48. Wing: Tail :: Fuselage: Empennage, Engines, Waist? (TAIL, kind) "Empennage" means the tail assemply of an aircraft, which is more a synonym for "tail" than "wing" is for "fuselage." The four primary forces on an airplane are: lift from the wings, negative lift from the tail, drag from the fuselage, and thrust from the engines. The narrow part at the end of the fuselage is called the "waist." 49. Bell: Loud :: Speak: Hear, Stentorian? The Sanskrit root of "bell" means "he talks" or "he speaks"; the Sanskrit root of "loud" means "he hears". A bell that makes a lot of noise is loud; a speaker who makes a lot of noise is stentorian. 50. Benevolence: Beg :: Philanthropist: Mendicant, Mendicate? If the analogy is attribute: attribute :: noun: noun, the answer is "mendicant"; if the analogy is noun: verb :: noun: verb the answer is "mendicate." 51. 10: Decimal :: 20: Vigesimal (TWENTY, pert.) 52. Five-sided Polyhedron: Pentahedron :: Faces of Parallelepiped Bounded by a Square: ? Does this mean a parallelepiped all of whose faces are bounded by a square (and what does "bounded" mean), or does it mean all six parallelograms that form the faces of a parallelepiped drawn in a plane inside of a square? 53. Motor: Helicopter :: Airflow: Autogiro (HELICOPTER) 54. Man: Ant :: Barter: Trophallaxis 55. United States: Soviet Union :: Cubism: ? (ART, style) If the emphasis is on opposition and collapse, there were several movements that opposed Cubism and that died out (e.g., Purism, Suprematism, Constructivism). If the emphasis is on freedom of perspective versus constraint, there were several movements that emphasized exact conformance with nature (e.g., Naturalism, Realism, Photo-Realism). If the emphasis is on dominating the art scene, the only movement that was contemporary with Cubism and of the same popularity as Cubism was Surrealism. A better answer would be an art movement named "Turkey-ism", since the Soviet Union offered to exchange missiles in Cuba for missiles in Turkey during the Cuban Missile Crisis. 56. State: Stipend :: Church: Prebend (STIPEND) 57. Motorcycle: Bicycle :: Motordrome: Velodrome (CYCLE, track) 58. Transparent: Porous :: Obsidian: Pumice (GLASS, volcanic) 59. pi*r^2*h: 1/3*pi*r^2*h :: Cylinder: Cone ==> competition/tests/math/putnam/putnam.1967.p <== In article <5840002@hpesoc1.HP.COM>, nicholso@hpesoc1.HP.COM (Ron Nicholson) wr ites: > Say that we have a hallway with n lockers, numbered from sequentialy > from 1 to n. The lockers have two possible states, open and closed. > Initially all the lockers are closed. The first kid who walks down the > hallway flips every locker to the opposite state, that is, opens them > all. The second kid flips the first locker door and every other locker > door to the opposite state, that is, closes them. The third kid flips > every third door, opening some, closing others. The forth kid does every > fourth door, etc. > > After n kid have passed down the hallway, which lockers are open, and > which are closed? B4. (a) Kids run down a row of lockers, flipping doors (closed doors are opened and opened doors are closed). The nth boy flips every nth lockers' door. If all the doors start out closed, which lockers will remain closed after infinitely many kids? ==> competition/tests/math/putnam/putnam.1967.s <== B4. (a) Only lockers whose numbers have an odd number of factors will remain closed, which are the squares. ==> competition/tests/math/putnam/putnam.1987.p <== WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION FORTY EIGHTH ANNUAL Saturday, December 5, 1987 Examination A; Problem A-1 ------- --- Curves A, B, C, and D, are defined in the plane as follows: A = { (x,y) : x^2 - y^2 = x/(x^2 + y^2) }, B = { (x,y) : 2xy + y/(x^2 + y^2) = 3 }, C = { (x,y) : x^3 - 3xy^2 + 3y = 1 }, D = { (x,y) : 3yx^2 - 3x - y^3 = 0 }. Prove that the intersection of A and B is equal to the intersection of C and D. Problem A-2 ------- --- The sequence of digits 1 2 3 4 5 6 7 8 9 1 0 1 1 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 ... is obtained by writing the positive integers in order. If the 10^n th digit in this sequence occurs in the part of the sequence in which the m-digit numbers are placed, define f(n) to be m. For example f(2) = 2 because the 100th digit enters the sequence in the placement of the two-digit integer 55. Find, with proof, f(1987). Problem A-3 ------- --- For all real x, the real valued function y = f(x) satisfies y'' - 2y' + y = 2e^x. (a) If f(x) > 0 for all real x, must f'(x) > 0 for all real x? Explain. (b) If f'(x) > 0 for all real x, must f(x) > 0 for all real x? Explain. Problem A-4 ------- --- Let P be a polynomial, with real coefficients, in three variables and F be a function of two variables such that P(ux,uy,uz) = u^2*F(y-x,z-x) for all real x,y,z,u, and such that P(1,0,0) = 4, P(0,1,0) = 5, and P(0,0,1) = 6. Also let A,B,C be complex numbers with P(A,B,C) = 0 and |B-A| = 10. Find |C-A|. Problem A-5 ------- --- ^ Let G(x,y) = ( -y/(x^2 + 4y^2) , x/(x^2 + 4y^2), 0 ). Prove or disprove that there is a vector-valued function ^ F(x,y,z) = ( M(x,y,z) , N(x,y,z) , P(x,y,z) ) with the following properties: (1) M,N,P have continuous partial derivatives for all (x,y,z) <> (0,0,0) ; ^ ^ (2) Curl F = 0 for all (x,y,z) <> (0,0,0) ; ^ ^ (3) F(x,y,0) = G(x,y). Problem A-6 ------- --- For each positive integer n, let a(n) be the number of zeros in the base 3 representation of n. For which positive real numbers x does the series inf ----- \ x^a(n) > ------ / n^3 ----- n = 1 converge? -- Examination B; Problem B-1 ------- --- 4/ (ln(9-x))^(1/2) dx Evaluate | --------------------------------- . 2/ (ln(9-x))^(1/2) + (ln(x+3))^(1/2) Problem B-2 ------- --- Let r, s, and t be integers with 0 =< r, 0 =< s, and r+s =< t. Prove that ( s ) ( s ) ( s ) ( s ) ( 0 ) ( 1 ) ( 2 ) ( s ) t+1 ----- + ------- + ------- + ... + ------- = ---------------- . ( t ) ( t ) ( t ) ( t ) ( t+1-s )( t-s ) ( r ) ( r+1 ) ( r+2 ) ( r+s ) ( r ) ( n ) n(n-1)...(n+1-k) ( Note: ( k ) denotes the binomial coefficient ---------------- .) k(k-1)...3*2*1 Problem B-3 ------- --- Let F be a field in which 1+1 <> 0. Show that the set of solutions to the equation x^2 + y^2 = 1 with x and y in F is given by (x,y) = (1,0) r^2 - 1 2r and (x,y) = ( ------- , ------- ), r^2 + 1 r^2 + 1 where r runs through the elements of F such that r^2 <> -1. Problem B-4 ------- --- Let ( x(1), y(1) ) = (0.8,0.6) and let x(n+1) = x(n)*cos(y(n)) - y(n)*sin(y(n)) and y(n+1) = x(n)*sin(y(n)) + y(n)*cos(y(n)) for n = 1,2,3,... . For each of the limits as n --> infinity of x(n) and y(n), prove that the limit exists and find it or prove that the limit does not exist. Problem B-5 ------- --- Let O(n) be the n-dimensional zero vector (0,0,...,0). Let M be a 2n x n matrix of complex numbers such that whenever ( z(1), z(2), ..., z(2n)*M = O(n), with complex z(i), not all zero, then at least one of the z(i) is not real. Prove that for arbitrary real number r(1), r(2), ..., r(2n), there are complex numbers w(1), w(2), ..., w(n) such that ( ( w(1) ) ) ( r(1) ) ( ( . ) ) ( . ) Re ( M*( . ) ) = ( . ) . ( ( . ) ) ( . ) ( ( w(n) ) ) ( r(2n) ) (Note: If C is a matrix of complex numbers, Re(C) is the matrix whose entries are the real parts of entries of C.) Problem B-6 ------- --- Let F be the field of p^2 elements where p is an odd prime. Suppose S is a set of (p^2-1)/2 distinct nonzero elements of F with the property that for each a <> 0 in F, exactly one of a and -a is in S. Let N be the number of elements in the intersection of S with { 2a : a e S }. Prove that N is even. -- ==> competition/tests/math/putnam/putnam.1987.s <== Problem A-1 ------- --- Let z=x+i*y. Then A and B are the real and imaginary parts of z^2=3i+1/z, and C, D are likewise Re and Im of z^3-3iz=1, and the two equations are plainly equivalent. Alternatively, having seen this, we can formulate a solution that avoids explicitly invoking the complex numbers, starting with C=xA-yB, D=yA+xB. Problem A-2 ------- --- Counting, we see that the numbers from 1 to n digits take up (10^n*(9n-1)+1)/9 spaces in the above sequence. Hence we need to find the least n for which 10^n*(9n-1)+1 > 9*10^1987, but it is easy to see that n = 1984 is the minimum such. Therefore f(1987) = 1984. In general, I believe, f(n) = n + 1 - g(n), where g(n) equals the largest value of m such that (10^m-1)/9 + 1 =< n if n>1, and g(0) = g(1) is defined to be 0. Hence, of course, g(n) = [log(9n-8)] if n>0. Therefore f(0) = 1, f(n) = n + 1 - [log(9n-8)] for n>0. Q.E.D. Problem A-3 ------- --- We have a differential equation, solve it. The general solution is y = f(x) = e^x*(x^2 + a*x + b), where a and b are arbitrary real constants. Now use completing the square and the fact that e^x > 0 for all real x to deduce that (1) f(x) > 0 for all real x iff 4b > a^2. (2) f'(x) > 0 for all real x iff 4b > a^2 + 4. It is now obvious that (2) ==> (1) but (1) /==> (2). Q.E.D. Problem A-4 ------- --- Setting x=0, u=1 we find F(y,z)=P(0,y,z) so F is a polynomial; keeping x=0 but varying u we find F(uy,uz)=u^2*F(y,z), so F is homogeneous of degree 2, i.e. of the form Ay^2+Byz+Cz^2, so P(x,y,z)=R(y-x)^2+S(y-x)(z-x)+T(z-x)^2 for some real R,S,T. The three given values of P now specify three linear equations on R,S,T, easily solved to give (A,B,C)=(5,-7,6). If now P(A,B,C)=0 then (C-A)=r(B-A), r one of the two roots of 5-7r+6r^2. This quadratic has negative discrminant (=-71) so its roots are complex conjugates; since their product is 5/6, each one has absolute value sqrt(5/6). (Yes, you can also use the Quadratic Equation.) So if B-A has absolute value 10, C-A must have absolute value 10*sqrt(5/6)=5*sqrt(30)/3. Problem A-5 ------- --- There is no such F. Proof: assume on the contrary that G extends to a curl-free vector field on R^3-{0}. Then the integral of G around any closed path in R^3-{0} vanishes because such a path bounds some surface [algebraic topologists, read: because H^2(R^3-{0},Z)=0 :-) ]. But we easily see that the integral of F around the closed path z=0, x^2+4y^2=1 (any closed path in the xy-plane that goes around the origin will do) is nonzero--- contradiction. Problem A-6 ------- --- For n>0 let T(n) = x^a(n)/n^3 and U(n) = T(3n) + T(3n+1) + T(3n+2) and for k>=0 let Z(k) = sum {n=3^k to 3^(k+1)-1} T(n) We have Z(k+1) = sum {n=3^(k+1) to 3^(k+2)-1} T(n) = sum {n=3^k to 3^(k+1)-1} [T(3n) + T(3n+1) + T(3n+2)] = sum {n=3^k to 3^(k+1)-1} U(n) Let us compare U(n) to T(n). We have a(3n)=a(n)+1 and a(3n+1)=a(3n+2)=a(n). Thus U(n) = x^[a(n)+1]/(3n)^3 + x^a(n)/(3n+1)^3 + x^a(n)/(3n+2)^3 and so U(n) has as upper bound x^a(n) * (x+2)/(3n)^3 = T(n) * (x+2)/27 and as lower bound x^a(n) * (x+2)/(3n+2)^3 = T(n) * (x+2)/(3+2/n)^3 in other words U(n) = T(n) * (x+2)/(27+e(n)), where e(n)<(3+2/n)^3-27 tends to 0 when n tends to infinity. It follows then that Z(k+1)= Z(k)*(x+2)/(27+f(k)) where f(k)<(3+2/3^k)^3-27 tends to 0 for n tending to infinity. Now the series is the sum of all Z(k). Thus for x>25 we have Z(k+1)>Z(k) for k large enough, and the series diverges; for x<25 we have Z(k+1)< r * Z(k) (with r=(x+2)/27<1) for every k, and the series converges. For x=25 the series diverges too (I think so), because Z(k+1)/Z(k) tends to 1 for k tending to infinity. Another proof: I would say,for x<25. Let S(m) be the sum above taken over 3^m <= n < 3^(m+1). Then for the n's in S(m), the base 3 representation of n has m+1 digits. Hence we can count the number of n's with a(n)=k as being the number of ways to choose a leading nonzero digit, times the number of ways to choose k positions out of the m other digits for the k zeroes, times the number of ways to choose nonzero digits for the m-k remaining positions, namely ( m ) m-k 2 ( ) 2 . ( k ) Hence we have 3^(m+1)-1 m ----- ----- \ a(n) \ ( m ) m-k k > x = > 2 ( ) 2 x / / ( k ) ----- ----- n=3^m k=0 m = 2 (x+2) . m -3m m -3(m+1) Hence we can bound S(m) between 2 (x+2) 3 and 2 (x+2) 3 . It is then clear that the original sum converges just when inf ----- \ m -3m > (x+2) 3 converges, or when x<25. / ----- m=0 Problem B-1 ------- --- Write the integrand as (ln(x+3))^(1/2) 1 - --------------------------------- . (ln(9-x))^(1/2) + (ln(x+3))^(1/2) Use the change of variables x = 6-t on the above and the fact that the two are equal to deduce that the original is equal to 1. QED. Problem B-3 ------- --- First note that the above values for x and y imply that x^2 + y^2 = 1. On the other foot note that if x<>1 ,x^2 + y^2 = 1, and 2 <> 0, then (x,y) is of the required form, with r = y/(1-x). Also note that r^2 <> -1, since this would imply x = 1. Derivation of r: We want x = (r^2-1)/(r^2+1) ==> 1-x = 2/(r^2+1), and also y = 2r/(r^2+1) ==> 1-x = (2y)/(2r) if 2<>0. Hence if 2<>0, r = y/(1-x). The above statement is false in some cases if 1+1 = 0 in F. For example, in Z(2) the solution (0,1) is not represented. QED. Problem B-4 ------- --- Observe that the vector (x(n+1), y(n+1)) is obtained from (x(n), y(n)) by a rotation through an angle of y(n). So if Theta(n) is the inclination of (x(n), y(n)), then for all n, Theta(n+1) = Theta(n) + y(n) Furthermore, all vectors have the same length, namely that of (x1, y1), which is 1. Therefore y(n) = sin (Theta(n)) and x(n) = cos (Theta(n)). Thus the recursion formula becomes (*) Theta(n+1) = Theta(n) + sin (Theta(n)) Now 0 < Theta(1) < pi. By induction 0 < sin(Theta(n)) = sin(pi - Theta(n)) < pi - Theta(n), so 0 < Theta(n+1) < Theta(n) + (pi - Theta(n)) = pi. Consequently, {Theta(n)} is an increasing sequence bounded above by pi, so it has a limit, Theta. From (*) we get Theta = Theta + sin(Theta), so with Theta in the interval (0,pi], the solution is Theta = pi. Thus lim (x(n),y(n)) = (cos(Theta), sin(Theta)) = (-1, 0). Problem B-5 ------- --- First note that M has rank n, else its left nullspace N has C-dimension >n and so R-dimension >2n, and thus nontrivially intersects the R-codimension 2n subspace of vectors all of whose coordinates are real. Thus the subspace V of C^(2n) spanned by M's columns has C-dimsension n and so R-dimension 2n, and to prove the R-linear map Re: V-->R^(2n) surjective, we need only prove it injective. So assume on the contrary that v is a nonzero vector in V all of whose coordinates are purely imaginary, and let W be the orthogonal complement of ; this is a subspace of C^(2n) of C-dim. 2n-1 and R-dim. 4n-2 . W contains N, which we've seen has R-dimension 2n; it also contains the orthogonal complement of in R^(2n), which has R-dimension 2n-1. Since (2n)+(2n-1) > (4n-2), these two real subspaces of W intersect nontrivially, producing a nonzero real vector in N---contradiction. So Re: V-->R^(2n) indeed has zero kernel and cokernel, Q.E.D. . Problem B-6 ------- --- Let P be the product of elements of S; then P'=2^|S|*P, the product of the elements of 2S, is either P or -P according to whether |2S-S| is even or odd. (each element of 2S is either in S or in -S, so match the factors in the products for P and P'.) But by Fermat's little theorem, 2^(p-1)=1, and since |S|=(p^2-1)/2=(p-1)*(p+1)/2 is a multiple of p-1, also 2^|S|=1 and P=P', Q.E.D. . This solution--analogous to one of Gauss' proof of Quadratic Reciprocity--is undoubtedly what the proposers had in mind, and had it been the only solution, B-6 would be a difficult problem on a par with B-6 problems of previous years. Unfortunately, just knowing that F* is a cyclic group of order |F|-1 for any finite field F, one can split F* into cosets of the subgroup generated by 2 and -1 and produce a straightforward, albeit plodding and uninspired, proof. I wonder how many of the contestants' answers to B-6 went this way and how many found the intended solution. Another proof: Given such a set S, it is immediate to verify that for any a in S, if one deletes a and adjoins -a to obtain a new set S' then the number of elements in the intersection of S' and 2S' is congruent (modulo 2) to the number of elements in the intersection of S and 2S. If S and S' are any two sets meeting the condition of this problem, then S can be changed to S' by repeating this operation several times. So, it suffices to prove the result for any one set S meeting the condition of the problem. A simple candidate for such an S is obtained by letting (u, v) be a basis for F over the field of p elements and letting S be the unions of the sets {au + bv: 1 <= u <= (p-1)/2, 0 <= b < p} and {bv: 0 <= b < (p-1)/2}. An elementary counting argument completes the proof. ==> competition/tests/math/putnam/putnam.1988.p <== Problem A-1: Let R be the region consisting of the points (x,y) of the cartesian plane satisfying both |x| - |y| <= 1 and |y| <= 1. Sketch the region R and find its area. Problem A-2: A not uncommon calculus mistake is to believe that the product rule for derivatives says that (fg)' = f'g'. If f(x) = exp(x^2), determine, with proof, whether there exists an open interval (a,b) and a non-zero function g defined on (a,b) such that the wrong product rule is true for x in (a,b). Problem A-3: Determine, with proof, the set of real numbers x for which sum from n=1 to infinity of ((1/n)csc(1/n) - 1)^x converges. Problem A-4: (a) If every point on the plane is painted one of three colors, do there necessarily exist two points of the same color exactly one inch apart? (b) What if "three" is replaced by "nine"? Justify your answers. Problem A-5: Prove that there exists a *unique* function f from the set R+ of positive real numbers to R+ such that f(f(x)) = 6x - f(x) and f(x) > 0 for all x > 0. Problem A-6: If a linear transformation A on an n-dimensional vector space has n + 1 eigenvectors such that any n of them are linearly independent, does it follow that A is a scalar multiple of the identity? Prove your answer. --------------------------------------------------------------------------- Problem B-1: A *composite* (positive integer) is a product ab with a and b not necessarily distinct integers in {2,3,4,...}. Show that every composite is expressible as xy + xz + yz + 1, with x, y, and z positive integers. Problem B-2: Prove or disprove: If x and y are real numbers with y >= 0 and y(y+1) <= (x+1)^2, then y(y-1) <= x^2. Problem B-3: For every n in the set Z+ = {1,2,...} of positive integers, let r(n) be the minimum value of |c-d sqrt(3)| for all nonnegative integers c and d with c + d = n. Find, with proof, the smallest positive real number g with r(n) <= g for all n in Z+. Problem B-4: Prove that if sum from n=1 to infinity a(n) is a convergent series of positive real numbers, then so is sum from n=1 to infinity (a(n))^(n/(n+1)). Problem B-5: For positive integers n, let M(n) be the 2n + 1 by 2n + 1 skew-symmetric matrix for which each entry in the first n subdiagonals below the main diagonal is 1 and each of the remaining entries below the main diagonal is -1. Find, with proof, the rank of M(n). (According to the definition the rank of a matrix is the largest k such that there is a k x k submatrix with non-zero determinant.) One may note that M(1) = ( 0 -1 1 ) and M(2) = ( 0 -1 -1 1 1 ) ( 1 0 -1 ) ( 1 0 -1 -1 1 ) ( -1 1 0 ) ( 1 1 0 -1 -1 ) ( -1 1 1 0 -1 ) ( -1 -1 1 1 0 ) Problem B-6: Prove that there exist an infinite number of ordered pairs (a,b) of integers such that for every positive integer t the number at + b is a triangular number if and only if t is a triangular number. (The triangular numbers are the t(n) = n(n + 1)/2 with n in {0,1,2,...}.) ==> competition/tests/math/putnam/putnam.1988.s <== % % Layout % \def\layout{\hsize 150truemm % 210mm - 1in * 2 for margins \vsize 246truemm % 297mm - 1in * 2 for margins \advance \vsize by -24 pt \topskip=10pt plus 1 pt} \magnification=1200 \layout \parindent=0pt \parskip=\medskipamount \newdimen\digitindent \digitindent=16truemm \newdimen\solindent \solindent=24truemm \newdimen\problemskip\newdimen\subproblemskip \problemskip=\bigskipamount \subproblemskip=\medskipamount \hoffset=\digitindent \def\problem #1 { \vskip \problemskip\hskip-\digitindent\hbox to\digitindent {\bf #1\hfill}\ignorespaces} \def\solution #1 { \vskip \problemskip\hskip-\solindent\hbox to\solindent {\bf #1\hfill}\ignorespaces} \def\notes #1 { \vskip \problemskip\hskip-\solindent\hbox to\solindent {\bf #1\hfill}\ignorespaces} \def\subproblem #1 {\vskip \subproblemskip\hskip-\digitindent \hbox to\digitindent{\hfill{\bf #1}\hfill}\ignorespaces} \def\endpage {\vfill\supereject\dosupereject} \headline={\headlinemacro} \footline={\hfil} \def\activeheadline{\hglue -\digitindent Chris Long, Rutgers University \hfill January 22, 1989} \let\headlinemacro=\activeheadline \advance \baselineskip by 6pt % % Aliases % \def\streck{\hbox {\vbox {\vfill \hrule width 0.5pt height 6pt \vskip 0.7pt}}} \def\C{\hbox{\hskip 1.5pt \streck \hskip -3.2pt {\rm C}}} \def\Q{\hbox{ \streck \hskip -3pt {\rm Q}}} \def\negativethinspace{\mskip-\thinmuskip} \def\R{\hbox{$\rm I \negativethinspace R $}} \def\Z{\hbox{$\rm Z \negativethinspace \negativethinspace Z $}} \def\N{\hbox{$\rm I \negativethinspace N $}} \def\H{\hbox{$\rm I \negativethinspace H $}} \def\adj{\rm adj} \def\det{\rm det} \def\Matrix#1{\left\lgroup\matrix{#1}\rgroup\right} \def\mod #1 {({\rm mod~}#1)} \def\Mod #1 {\ ({\rm mod~}#1)} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} % % Body of article % \problem {A-1:} Let $R$ be the region consisting of the points $(x,y)$ of the cartesian plane satisfying both $|x| - |y| \le 1$ and $|y| \le 1$. Sketch the region $R$ and find its area. \solution {Solution:} The area is $6$; the graph I leave to the reader. \problem {A-2:} A not uncommon calculus mistake is to believe that the product rule for derivatives says that $(fg)' = f'g'$. If $f(x) = e^{x^{2}}$, determine, with proof, whether there exists an open interval $(a,b)$ and a non-zero function $g$ defined on $(a,b)$ such that the wrong product rule is true for $x$ in $(a,b)$. \solution {Solution:} We find all such functions. Note that $(fg)' = f'g' \Rightarrow f'g' = f'g + fg'$ hence if $g(x), f'(x) - f(x) \neq 0$ we get that $g'(x)/g(x) = f'(x)/(f'(x) - f(x))$. For the particular $f$ given, we then get that $g'(x)/g(x) = (2x)e^{x^2}/( (2x-1) (e^{x^2}) ) \Rightarrow g'(x)/g(x) = 2x/(2x-1)$ (since $e^{x^2} > 0$). Integrating, we deduce that $\ln{|g(x)|} = x + (1/2)\ln{|2x-1|} + c$ (an arbitrary constant) $\Rightarrow |g(x)| = e^{c} \sqrt{|2x-1|} e^{x} \Rightarrow g(x) = C \sqrt{|2x-1|} e^{x}, C$ arbitrary $\neq 0$. We finish by noting that any $g(x)$ so defined is differentiable on any open interval that does not contain $1/2$. Q.E.D. \problem {A-3:} Determine, with proof, the set of real numbers $x$ for which $\sum_{n=1}^{\infty} {( {1\over n} \csc ({1\over n}) - 1)}^{x}$ converges. \solution {Solution:} The answer is $x > {1\over 2}$. To see this, note that by Taylor's theorem with remainder $\sin( {1\over{n}} ) = \sum_{i=1}^{k-1} { {(-1)}^{i-1} {n}^{-(2i+1)} } + c { {(-1)}^{k-1} {n}^{-(2k+1)} }$, where $0 \leq c \leq {1\over n}$. Hence for $n\geq 1 ( 1/n )/( 1/n - 1/(3! n^{3}) + 1/(5! n^{5}) - 1 < (1/n) \csc(1/n) - 1 < ( 1/n )/( 1/n - 1/(3! n^{3}) ) - 1 \Rightarrow$ for $n$ large enough, $ (1/2) 1/(3! n^{2}) < (1/n) \csc(1/n) - 1 < 2\cdot 1/(3! n^{2})$. Applying the p-test and the comparison test, we see that $\sum_{n=1}^{\infty} {( {1\over n} \csc({1\over n}) - 1)}^{x}$ converges iff $x > {1\over 2}$. Q.E.D. \problem {A-4:} Justify your answers. \subproblem {(a)} If every point on the plane is painted one of three colors, do there necessarily exist two points of the same color exactly one inch apart? \solution {Solution:} The answer is yes. Assume not and consider two equilateral triangles with side one that have exactly one common face $\Rightarrow$ all points a distance of $\sqrt{3}$ apart are the same color; now considering a triangle with sides $\sqrt{3}, \sqrt{3}, 1$ we reach the desired contradiction. Here is a pretty good list of references for the chromatic number of the plane (i.e., how many colors do you need so that no two points 1 away are the same color) up to around 1982 (though the publication dates are up to 1985). This asks for the chromatic number of the graph where two points in R^2 are connected if they are distance 1 apart. Let this chromatic number be chi(2) and in general let chi(n) be the chromatic number of R^n. By a theorem in [2] this is equivalent to finding what the maximum chromatic number of a finite subgraph of this infinite graph is. [1] H. Hadwiger, ``Ein Ueberdeckungssatz f\"ur den Euklidischen Raum,'' Portugal. Math. #4 (1944), p.140-144 This seems to be the original reference for the problem [2] N.G. de Bruijn and P. Erd\"os, ``A Color Problem for Infinite Graphs and a Problem in the Theory of Relations,'' Nederl. Akad. Wetensch. (Indag Math) #13 (1951), p. 371-373. [3] H. Hadwiger, ``Ungel\"oste Probleme No. 40,'' Elemente der Math. #16 (1961), p. 103-104. Gives the upper bound of 7 with the hexagonal tiling and also a reference to a Portugese journal where it appeared. [4] L. Moser and W. Moser, ``Solution to Problem 10,'' Canad. Math. Bull. #4 (1961), p. 187-189. Shows that any 6 points in the plane only need 3 colors but gives 7 points that require 4 (``the Moser Graph'' see [7]). [5] Paul Erd\"os, Frank Harary, and William T. Tutte, ``On the Dimension of a Graph,'' Mathematika #12 (1965), p. 118-122. States that 34.'' States a question of L. Moser: Let R be large and S a measurable set in the circle of radius R so that no two points of S have distance 1. Denote by m(S) the measure of S. Determine Lim_{R => infty} max m(S)/R^2. Erd\"os conjectures that this limit is less than 1/4. Erd\"os asks the following: ``Let S be a subset of the plane. Join two points of S if their distances is 1. This gives a graph G(S). Assume that the girth (shortest circuit) of G(S) is k. Can its chromatic number be greater than 3? Wormald proved that such a graph exists for k<6. The problem is open for k>5. Wormald suggested that this method may work for k=6, but probably a new idea is needed for k>6. A related (perhaps identical) question is: `Does G(S) have a subgraph that has girth k and chromatic number 4?' '' [7] N. Wormald, ``A 4-chromatic graph with a special plane drawing,'' J. Austr. Math. Soc. Ser. A #28 (1970), p. 1-8. The reference for the above question. [8] R.L. Graham, ``Old and New Euclidean Ramsey Theorems,'' in ``Discrete Geometry and Convexity,'' Edited by Jacob E. Goodman, Erwin Lutwak, Joseph Malkevitch, and Richard Pollack, Annals of the New York Academy of Sciences Vol. 440, New York Academy of Sciences 1985, Pages 20-30. States that the best current bounds are 3 0$ for all $x > 0$. \solution {Solution 1:} Clearly $f(x) = 2x$ is one such solution; we need to show that it is the {\it only} solution. Let $f^{1}(x) = f(x), f^{n}(x) = f(f^{n-1}(x))$ and notice that $f^{n}(x)$ is defined for all $x>0$. An easy induction establishes that for $n>0 f^{n}(x) = a_{n} x + b_{n} f(x)$, where $a_{0} = 0, b_{0} = 1$ and $a_{n+1} = 6 b_{n}, b_{n+1} = a_{n} - b_{n} \Rightarrow b_{n+1} = 6 b_{n-1} - b_{n}$. Solving this latter equation in the standard manner, we deduce that $\lim_{n\to \infty} a_{n}/b_{n} = -2$, and since we have that $f^{n}(x) > 0$ and since $b_{n}$ is alternately negative and positive; we conclude that $2x \leq f(x) \leq 2x$ by letting $n \rightarrow \infty$. Q.E.D. \solution {Solution 2:} (Dan Bernstein, Princeton) As before, $f(x) = 2x$ works. We must show that if $f(x) = 2x + g(x)$ and $f$ satisfies the conditions then $g(x) = 0$ on ${\R}^{+}$. Now $f(f(x)) = 6x - f(x)$ means that $2f(x) + g(f(x)) = 6x - 2x - g(x)$, i.e., $4x + 2g(x) + g(f(x)) = 4x - g(x)$, i.e., $3g(x) + g(f(x)) = 0$. This then implies $g(f(f(x))) = 9g(x)$. Also note that $f(x) > 0$ implies $g(x) > -2x$. Suppose $g(x)$ is not $0$ everywhere. Pick $y$ at which $g(y) \neq 0$. If $g(y) > 0$, observe $g(f(y)) = -3g(y) < 0$, so in any case there is a $y_{0}$ with $g(y_{0}) < 0$. Now define $y_{1} = f(f(y_{0})), y_{2} = f(f(y_{1}))$, etc. We know $g(y_{n+1})$ equals $g(f(f(y_{n}))) = 9g(y_{n})$. But $y(n+1) = f(f(y_{n})) = 6y_{n} - f(y_{n}) < 6y_{n}$ since $f>0$. Hence for each $n$ there exists $y_{n} < 6^{n} y_{0}$ such that $g(y_{n}) = 9^{n} g(y_{0})$. The rest is obvious: $0 > g(y_{0}) = 9^{-n} g(y_{n}) > -2\cdot 9^{-n} y_{n} > -2 (6/9)^{n} y_{0}$, and we observe that as $n$ goes to infinity we have a contradiction. Q.E.D. \problem {A-6:} If a linear transformation $A$ on an $n$-dimensional vector space has $n+1$ eigenvectors such that any $n$ of them are linearly independent, does it follow that $A$ is a scalar multiple of the identity? Prove your answer. \solution {Solution:} The answer is yes. First note that if $x_{1}, \ldots, x_{n+1}$ are the eigenvectors, then we must have that $a_{n+1} x_{n+1} = a_{1} x_{1} + \cdots + a_{n} x_{n}$ for some non-zero scalars $a_{1}, \ldots, a_{n+1}$. Multiplying by $A$ on the left we see that $\lambda_{n+1} a_{n+1} x_{n+1} = \lambda_{1} a_{1} x_{1} + \cdots + \lambda_{n} a_{n} x_{n}$, where $\lambda_{i}$ is the eigenvalue corresponding to the eigenvectors $x_{i}$. But since we also have that $\lambda_{n+1} a_{n+1} x_{n+1} = \lambda_{n+1} a_{1} x_{1} + \cdots + \lambda_{n+1} a_{n} x_{n}$ we conclude that $\lambda_{1} a_{1} x_{1} + \cdots + \lambda_{n} a_{n} x_{n} = \lambda_{n+1} a_{1} x_{1} + \cdots + \lambda_{n+1} a_{n} x_{n} \Rightarrow a_{1} (\lambda_{1} - \lambda_{n+1}) x_{1} + \cdots + a_{n} (\lambda_{n} - \lambda_{n+1}) x_{1} = 0 \Rightarrow \lambda_{1} = \cdots = \lambda_{n+1} = \lambda$ since $x_{1}, \ldots, x_{n}$ are linearly independent. To finish, note that the dimension of the eigenspace of $\lambda$ is equal to $n$, and since this equals the dimension of the nullspace of $A - \lambda I$ we conclude that the rank of $A - \lambda I$ equals $n - n = 0 \Rightarrow A - \lambda I = 0$. Q.E.D. \problem {B-1:} A {\it composite} (positive integer) is a product $ab$ with $a$ and $b$ not necessarily distinct integers in $\{ 2,3,4,\ldots \}$. Show that every composite is expressible as $xy + xz + yz + 1$, with $x, y$, and $z$ positive integers. \solution {Solution:} Let $x = a-1, y = b-1, z = 1$; we then get that $xy + xz + yz + 1 = (a-1)(b-1) + a-1 + b-1 + 1 = ab$. Q.E.D. \problem {B-2:} Prove or disprove: If $x$ and $y$ are real numbers with $y \geq 0$ and $y(y+1) \leq {(x+1)}^2$, then $y(y-1) \leq x^2$. \solution {Solution:} The statement is true. If $x+1 \geq 0$ we have that $\sqrt{y(y+1)} - 1 \leq x \Rightarrow x^{2} \geq y^{2} + y + 1 - 2 \sqrt{y^{2}+y} \geq y^{2} - y$ since $2y + 1 \geq 2 \sqrt{y^{2}+y}$ since ${(2y + 1)}^{2} \geq 4 (y^{2}+y)$ if $y\geq 0$. If $x+1 < 0$, we see that $\sqrt{y(y+1)} \leq -x - 1 \Rightarrow x^{2} \geq y^{2} + y + 1 + 2 \sqrt{y^{2}+y} \geq y^{2} - y$. Q.E.D. \problem {B-3:} For every $n$ in the set ${\Z}^{+} = \{ 1,2,\ldots \}$ of positive integers, let $r(n)$ be the minimum value of $|c-d \sqrt{3}|$ for all nonnegative integers $c$ and $d$ with $c + d = n$. Find, with proof, the smallest positive real number $g$ with $r(n) \leq g$ for all $n$ in ${\Z}^{+}$. \solution {Solution:} The answer is $(1 + \sqrt{3})/2$. We write $|c-d\sqrt{3}|$ as $|(n-d) - d\sqrt{3}|$; I claim that the minimum over all $d, 0 \leq d \leq n$, occurs when $d = e = \floor{n/(1+\sqrt{3})}$ or when $d = f = e+1 = \floor{n/(1+\sqrt{3})} + 1$. To see this, note that $(n-e) - e \sqrt{3} > 0$ and if $e' (n-e) - e \sqrt{3}$, and similarly for $f'>f$. Now let $r = n/(1+\sqrt{3}) - \floor{n/(1+\sqrt{3})}$ and note that $|(n-e) - e \sqrt{3}| = r (1+\sqrt{3})$ and $|(n-f) - f \sqrt{3}| = (1-r) (1+\sqrt{3})$. Clearly one of these will be $\leq (1+\sqrt{3})/2$. To see that $(1+\leq{3})/2$ cannot be lowered, note that since $1+\sqrt{3}$ is irrational, $r$ is uniformly distributed $\mod{1} $. Q.E.D. \notes {Notes:} We do not really need the result that $x$ irrational $\Rightarrow x n - \floor{x n}$ u. d. $\mod{1} $, it would suffice to show that $x$ irrational $\Rightarrow x n - \floor{x n}$ is dense in $(0,1)$. But this is obvious, since if $x$ is irrational there exists arbitrarily large $q$ such that there exists $p$ with $(p,q) = 1$ such that $p/q < x < (p+1)/q$. The nifty thing about the u. d. result is that it answers the question: what number $x$ should we choose such that the density of $\{ n : r(n) < x \}$ equals $t, 0 < t < 1$? The u. d. result implies that the answer is $t (1+\sqrt{3})/2$. The u. d. result also provides the key to the question: what is the average value of $r(n)$? The answer is $(1+\sqrt{3})/4$. \problem {B-4:} Prove that if $\sum_{n=1}^{\infty} a(n)$ is a convergent series of positive real numbers, then so is $\sum_{n=1}^{\infty} {(a(n))}^{n/(n+1)}$. \solution {Solution:} Note that the subseries of terms ${a(n)}^{n\over{n+1}}$ with ${a(n)}^{1\over{n+1}} \leq {1\over 2}$ converges since then ${a(n)}^{n\over{n+1}}$ is dominated by $1/2^{n}$, the subseries of terms ${a(n)}^{n\over{n+1}}$ with ${a(n)}^{1\over{n+1}} > {1\over 2}$ converges since then ${a(n)}^{n\over{n+1}}$ is dominated by $2 a(n)$, hence $\sum_{n=1}^{\infty} {a(n)}^{n\over{n+1}}$ converges. Q.E.D. \problem {B-5:} For positive integers $n$, let $M(n)$ be the $2n + 1$ by $2n + 1$ skew-symmetric matrix for which each entry in the first $n$ subdiagonals below the main diagonal is $1$ and each of the remaining entries below the main diagonal is $-1$. Find, with proof, the rank of $M(n)$. (According to the definition the rank of a matrix is the largest $k$ such that there is a $k \times k$ submatrix with non-zero determinant.) One may note that \break\hfill $M(1) = \left( \matrix{0&-1&1 \cr 1&0&-1 \cr -1&1&0} \right)$ and $M(2) = \left( \matrix{0&-1&-1&1&1 \cr 1&0&-1&-1&1 \cr 1&1&0&-1&-1 \cr -1&1&1&0&-1 \cr -1&-1&1&1&0} \right)$. \solution {Solution 1:} Since $M(n)$ is skew-symmetric, $M(n)$ is singular for all $n$, hence the rank can be at most $2n$. To see that this is indeed the answer, consider the submatrix $M_{i}(n)$ obtained by deleting row $i$ and column $i$ from $M(n)$. From the definition of the determinant we have that $\det(M_{i}(n)) = \sum {(-1)}^{\delta(k)} a_{1 k(1)} \cdots a_{(2n) k(2n)}$, where $k$ is member of $S_{2n}$ (the group of permutations on $\{1,\ldots,2n\}$) and $\delta(k)$ is $0$ if $k$ is an even permutation or $1$ if $k$ is an odd permutation. Now note that ${(-1)}^{\delta(k)} a_{1 k(1)} \cdots a_{(2n) k(2n)}$ equals either $0$ or $\pm 1$, and is non-zero iff $k(i) \neq i$ for all $i$, i.e. iff $k$ has no fixed points. If we can now show that the set of all elements $k$ of $S_{2n}$, with $k(i) \neq i$ for all $i$, has odd order, we win since this would imply that $\det(M_{i}(n))$ is odd $\Rightarrow \det(M_{i}) \neq 0$. To show this, let $f(n)$ equal the set of all elements $k$ of $S_n$ with $k(i) \neq i$ for all $i$. We have that $f(1) = 0, f(2) = 1$ and we see that $f(n) = (n-1) ( f(n-1) + f(n-2) )$ by considering the possible values of $f(1)$ and whether or not $f(f(1)) = 1$; an easy induction now establishes that $f(2n)$ is odd for all $n$. Q.E.D. \notes {Notes:} In fact, it is a well-known result that $f(n) = n! ( 1/2! - 1/3! + \cdots + {(-1)}^{n}/n! )$. \solution {Solution 2:} As before, since $M(n)$ is skew-symmetric $M(n)$ is singular for all $n$ and hence can have rank at most $2n$. To see that this is the rank, let $M_{i}(n)$ be the submatrix obtained by deleting row $i$ and column $i$ from $M(n)$. We finish by noting that ${M_{i}(n)}^{2} \equiv I_{2n} \Mod{2} $, hence $M_{i}(n)$ is nonsingular. Q.E.D. \problem {B-6:} Prove that there exist an infinite number of ordered pairs $(a,b)$ of integers such that for every positive integer $t$ the number $at + b$ is a triangular number if and only if $t$ is a triangular number. (The triangular numbers are the $t(n) = n(n + 1)/2$ with $n$ in $ \{ 0,1,2,\ldots \}$ ). \solution {Solution:} Call a pair of integers $(a,b)$ a {\it triangular pair} if $at + b$ is a triangular number iff $t$ is a triangular number. I claim that $(9,1)$ is a triangular pair. Note that $9 (n(n+1)/2) + 1 = (3n+1)(3n+2)/2$ hence $9t+1$ is triangular if $t$ is. For the other direction, note that if $ 9t+1 = n(n+1)/2 \Rightarrow n = 3k+1$ hence $ 9t+1 = n(n+1)/2 = 9(k(k+1)/2)+1 \Rightarrow t = k(k+1)/2$, therefore $t$ is triangular. Now note that if $(a,b)$ is a triangular pair then so is $(a^{2},(a+1)b)$, hence we can generate an infinite number of triangular pairs starting with $(9,1)$. Q.E.D. \notes {Notes:} The following is a proof of necessary and sufficient conditions for $(a,b)$ to be a triangular pair. I claim that $(a,b)$ is a triangular pair iff for some odd integer $o$ we have that $a = o^{2}, b = (o^{2}-1)/8$. I will first prove the direction $\Leftarrow$. Assume we have $a = o^{2}, b = (o^{2}-1)/8$. If $t = n(n+1)/2$ is any triangular number, then the identity $o^{2} n(n+1)/2 + (o^{2}-1)/8 = (on + (o-1)/2) (on + (o+1)/2)/2$ shows that $at + b$ is also a triangular number. On the other hand if $o^{2} t + (o^{2}-1)/8 = n(n+1)/2$, the above identity implies we win if we can show that $( n - (o-1)/2 )/o$ is an integer, but this is true since $o^{2} t + (o^{2}-1)/8 \equiv n(n+1)/2 \Mod{o^{2}} \Rightarrow 4n^{2} + 4n \equiv -1 \Mod{o^{2}} \Rightarrow {(2n + 1)}^{2} \equiv 0 \Mod{o^{2}} \Rightarrow 2n + 1 \equiv 0 \Mod{o} \Rightarrow n \equiv (o-1)/2 \Mod{o} $. For the direction $\Rightarrow$ assume that $(a,b)$ and $(a,c), c\ge b$, are both triangular pairs; to see that $b = c$ notice that if $at + b$ is triangular for all triangular numbers $t$, then we can choose $t$ so large that if $c>b$ then $at + c$ falls between two consecutive triangular numbers; contradiction hence $b = c$. Now assume that $(a,c)$ and $(b,c)$ are both triangular pairs; I claim that $a = b$. But this is clear since if $(a,c)$ and $(b,c)$ are triangular pairs $\Rightarrow (ab,bc+c)$ and $(ab,ac+c)$ are triangular pairs $\Rightarrow bc+c = ac+c$ by the above reasoning $\Rightarrow bc=ac \Rightarrow$ either $a=b$ or $c=0 \Rightarrow a=b$ since $c=0 \Rightarrow a=b=1$. For a proof of this last assertion, assume $(a,0), a>1$, is a triangular pair; to see that this gives a contradiction note that if $(a,0)$ is a triangular pair $\Rightarrow (a^{2},0)$ is also triangular pair, but this is impossible since then we must have that $a(a^{3}+1)/2$ is triangular (since $a^{2} a (a^{3}+1)/2$ is triangular) but $(a^{2}-1)a^{2}/2 < a(a^{3}+1)/2 < a^{2}(a^{2}+1)/2$ (if $a>1$). We are now done, since if $(a,b)$ is a triangular pair $\Rightarrow a 0 + b = n(n+1)/2$ for some $n\geq 0 \Rightarrow b = ({(2n+1)}^{2} - 1)/8$. Q.E.D. \bye ==> competition/tests/math/putnam/putnam.1990.p <== Problem A-1 How many primes among the positive integers, written as usual in base 10, are such that their digits are alternating 1's and 0's, beginning and ending with 1? Problem A-2 Evaluate \int_0^a \int_0^b \exp(\max{b^2 x^2, a^2 y^2}) dy dx where a and b are positive. Problem A-3 Prove that if 11z^10 + 10iz^9 + 10iz - 11 = 0, then |z| = 1. (Here z is a complex number and i^2 = -1.) Problem A-4 If \alpha is an irrational number, 0 < \alpha < 1, is there a finite game with an honest coin such that the probability of one player winning the game is \alpha? (An honest coin is one for which the probability of heads and the probability of tails are both 1/2. A game is finite if with probability 1 it must end in a finite number of moves.) Problem A-5 Let m be a positive integer and let G be a regular (2m + 1)-gon inscribed in the unit circle. Show that there is a positive constant A, independent of m, with the following property. For any point p inside G there are two distinct vertices v_1 and v_2 of G such that 1 A | |p - v_1| - |p - v_2| | < --- - ---. m m^3 Here |s - t| denotes the distance between the points s and t. Problem A-6 Let \alpha = 1 + a_1 x + a_2 x^2 + ... be a formal power series with coefficients in the field of two elements. Let / 1 if every block of zeros in the binary expansion of n / has an even number of zeros in the block, a_n = { \ 0 otherwise. (For example, a_36 = 1 because 36 = 100100_2 and a_20 = 0 because 20 = 10100_2.) Prove that \alpha^3 + x \alpha + 1 = 0. Problem B-1 A dart, thrown at random, hits a square target. Assuming that any two points of the target of equal area are equally likely to be hit, find the probability that the point hit is nearer to the center than to any edge. Express your answer in the form (a \sqrt(b) + c) / d, where a, b, c, d are integers. Problem B-2 Let S be a non-empty set with an associative operation that is left and right cancellative (xy = xz implies y = z, and yx = zx implies y = z). Assume that for every a in S the set { a^n : n = 1, 2, 3, ... } is finite. Must S be a group? Problem B-3 Let f be a function on [0,\infty), differentiable and satisfying f'(x) = -3 f(x) + 6 f(2x) for x > 0. Assume that |f(x)| <= \exp(-\sqrt(x)) for x >= 0 (so that f(x) tends rapidly to 0 as x increases). For n a non-negative integer, define \mu_n = \int_0^\infty x^n f(x) dx (sometimes called the nth moment of f). a. Express \mu_n in terms of \mu_0. b. Prove that the sequence { \mu_n 3^n / n! } always converges, and that the limit is 0 only if \mu_0 = 0. Problem B-4 Can a countably infinite set have an uncountable collection of non-empty subsets such that the intersection of any two of them is finite? Problem B-5 Label the vertices of a trapezoid T (quadrilateral with two parallel sides) inscribed in the unit circle as A, B, C, D so that AB is parallel to CD and A, B, C, D are in counterclockwise order. Let s_1, s_2, and d denote the lengths of the line segments AB, CD, and OE, where E is the point of intersection of the diagonals of T, and O is the center of the circle. Determine the least upper bound of (s_1 - s_2) / d over all such T for which d \ne 0, and describe all cases, if any, in which it is attained. Problem B-6 Let (x_1, x_2, ..., x_n) be a point chosen at random from the n-dimensional region defined by 0 < x_1 < x_2 < ... < x_n < 1. Let f be a continuous function on [0, 1] with f(1) = 0. Set x_0 = 0 and x_{n+1} = 1. Show that the expected value of the Riemann sum \sum_{i = 0}^n (x_{i+1} - x_i) f(x_{i+1}) is \int_0^1 f(t)P(t) dt, where P is a polynomial of degree n, independent of f, with 0 \le P(t) \le 1 for 0 \le t \le 1. ==> competition/tests/math/putnam/putnam.1990.s <== Problem A-1 How many primes among the positive integers, written as usual in base 10, are such that their digits are alternating 1's and 0's, beginning and ending with 1? Solution: Exactly one, namely 101. 1 is not prime; 101 is prime. The sum 100^n + 100^{n - 1} + ... + 1 is divisible by 101 if n is odd, 10^n + 10^{n - 1} + ... + 1 if n is even. (To see the second part, think about 101010101 = 102030201 - 1020100 = 10101^2 - 1010^2.) Problem A-2 Evaluate \int_0^a \int_0^b \exp(\max{b^2 x^2, a^2 y^2}) dy dx where a and b are positive. Solution: Split the inner integral according to the max{}. The easy term becomes an integral of t e^{t^2}. The other term becomes an easy term after you switch the order of integration. Your answer should have an e^{(ab)^2}. Problem A-3 Prove that if 11z^10 + 10iz^9 + 10iz - 11 = 0, then |z| = 1. (Here z is a complex number and i^2 = -1.) Solution: z is not zero, so divide by z^5 to make things a bit more symmetric. Now write z = e^{i \theta} and watch the formula dissolve into a simple trigonometric sum. The 11 sin 5 \theta term dominates the sum when that sine is at its maximum; by this and similar considerations, just *write down* enough maxima and minima of the function that it must have ten real roots for \theta. (This cute solution is due to Melvin Hausner, an NYU math professor.) Problem A-4 If \alpha is an irrational number, 0 < \alpha < 1, is there a finite game with an honest coin such that the probability of one player winning the game is \alpha? (An honest coin is one for which the probability of heads and the probability of tails are both 1/2. A game is finite if with probability 1 it must end in a finite number of moves.) Solution: Yes. Write \alpha in binary---there's no ambiguity since it's irrational. At the nth step (n >= 0), flip the coin. If it comes up heads, go to the next step. If it comes up tails, you win if the nth bit of \alpha is 1. Otherwise you lose. The probability of continuing forever is zero. The probability of winning is \alpha. This problem could have been better stated. Repeated flips of the coin must produce independent results. The note that ``finite'' means only ``finite with probability 1'' is hidden inside parentheses, even though it is crucial to the result. In any case, this problem is not very original: I know I've seen similar problems many times, and no serious student of probability can take more than ten minutes on the question. Problem A-5 Let m be a positive integer and let G be a regular (2m + 1)-gon inscribed in the unit circle. Show that there is a positive constant A, independent of m, with the following property. For any point p inside G there are two distinct vertices v_1 and v_2 of G such that 1 A | |p - v_1| - |p - v_2| | < --- - ---. m m^3 Here |s - t| denotes the distance between the points s and t. Solution: Place G at the usual roots of unity. Without loss of generality assume that p = re^{i\theta} is as close to 1 as to any other vertex; in other words, assume |\theta| <= 2\pi / (4m + 2) = \pi / (2m + 1). Now take the distance between p and the two farthest (not closest!) vertices. Make sure to write | |X| - |Y| | as the ratio of | |X|^2 - |Y|^2 | to |X| + |Y|. I may have miscalculated, but I get a final result inversely proportional to (4m + 2)^2, from which the given inequality follows easily with, say, A = 0.01. Alternate solution: The maximum distance between p and a point of G is achieved between two almost-opposite corners, with a distance squared of double 1 + \cos\theta for an appropriately small \theta, or something smaller than 2 - A/m^2 for an appropriate A. Now consider the set of distances between p and the vertices; this set is 2m + 1 values >= 0 and < 2 - A/m^2, so that there are two values at distance less than 1/m - A/m^3 as desired. Problem A-6 Let \alpha = 1 + a_1 x + a_2 x^2 + ... be a formal power series with coefficients in the field of two elements. Let / 1 if every block of zeros in the binary expansion of n / has an even number of zeros in the block, a_n = { \ 0 otherwise. (For example, a_36 = 1 because 36 = 100100_2 and a_20 = 0 because 20 = 10100_2.) Prove that \alpha^3 + x \alpha + 1 = 0. Solution: (Put a_0 = 1, of course.) Observe that a_{4n} = a_n since adding two zeros on the right end does not affect the defining property; a_{4n + 2} = 0 since the rightmost zero is isolated; and a_{2n + 1} = a_n since adding a one on the right does not affect the defining property. Now work in the formal power series ring Z_2[[x]]. For any z in that ring that is a multiple of x, define f(z) as a_0 + a_1 z + a_2 z^2 + ... . Clearly f(z) = f(z^4) + z f(z^2) by the relations between a's. Now over Z_2, (a + b)^2 = a^2 + b^2, so f(z) = f(z)^4 + z f(z)^2. Plug in x for z and cancel the f(x) to get 1 = \alpha^3 + x \alpha as desired. Problem B-1 A dart, thrown at random, hits a square target. Assuming that any two points of the target of equal area are equally likely to be hit, find the probability that the point hit is nearer to the center than to any edge. Express your answer in the form (a \sqrt(b) + c) / d, where a, b, c, d are integers. Solution: This is straightforward. The closer-to-the-center region is centered on a square of side length \sqrt 2 - 1; surrounding the square and meeting it at its corners are parabolic sections extending out halfway to the edge. b is 2 and d is 6; have fun. Problem B-2 Let S be a non-empty set with an associative operation that is left and right cancellative (xy = xz implies y = z, and yx = zx implies y = z). Assume that for every a in S the set { a^n : n = 1, 2, 3, ... } is finite. Must S be a group? Solution: Yes. There is a minimal m >= 1 for which a^m = a^n for some n with n > m; by cancellation, m must be 1. We claim that a^{n-1} is an identity in S. For ba = ba^n = ba^{n-1}a, so by cancellation b = ba^{n-1}, and similarly on the other side. Now a has an inverse, a^{n-2}. This problem is not new. Problem B-3 Let f be a function on [0,\infty), differentiable and satisfying f'(x) = -3 f(x) + 6 f(2x) for x > 0. Assume that |f(x)| <= \exp(-\sqrt(x)) for x >= 0 (so that f(x) tends rapidly to 0 as x increases). For n a non-negative integer, define \mu_n = \int_0^\infty x^n f(x) dx (sometimes called the nth moment of f). a. Express \mu_n in terms of \mu_0. b. Prove that the sequence { \mu_n 3^n / n! } always converges, and that the limit is 0 only if \mu_0 = 0. Solution: The only trick here is to integrate \mu_n by parts the ``wrong way,'' towards a higher power of x. A bit of manipulation gives the formula for \mu_n as \mu_0 times n! / 3^n times the product of 2^k / (2^k - 1) for 1 <= k <= n. Part b is straightforward; the product converges since the sum of 1 / (2^k - 1) converges (absolutely---it's positive). Problem B-4 Can a countably infinite set have an uncountable collection of non-empty subsets such that the intersection of any two of them is finite? Solution: Yes. A common example for this very well-known problem is the set of rationals embedded in the set of reals. For each real take a Cauchy sequence converging to that real; those sequences form the subsets of the countably infinite rationals, and the intersection of any two of them had better be finite since the reals are Archimedian. Another example, from p-adics: Consider all binary sequences. With sequence a_0 a_1 a_2 ... associate the set a_0, a_0 + 2a_1, a_0 + 2a_1 + 4a_2, etc.; or stick 1 bits in all the odd positions to simplify housekeeping (most importantly, to make the set infinite). Certainly different sequences give different sets, and the intersection of two such sets is finite. Alternative solution: Let C be a countable collection of non-empty subsets of A with the property that any two subsets have finite intersection (from now on we call this property, countable intersection property). Clearly such a collection exists. We will show that C is not maximal, that is, there exists a set which does not belong to C and it intersects finitely with any set in C. Hence by Zorn's lemma, C can be extended to an uncountable collection. Let A1, A2, .... be an enumeration of sets in C. Then by axiom of choice, pick an element b sub i from each of A sub i - Union {from j=1 to i-1} of A sub j. It is easy to see that each such set is non-empty. Let B be the set of all b sub i's. Then clearly B is different from each of the A sub i's and its intersection with each A sub i is finite. Yet another alternative solution: Let the countable set be the lattice points of the plane. For each t in [0,pi) let s(t) be the lattice points in a strip with angle of inclination t and width greater than 1. Then the set of these strips is uncountable. The intersection of any two is bounded, hence finite. More solutions: The problem (in effect) asks for an uncountable collection of sets of natural numbers that are "almost disjoint," i.e., any two have a finite intersection. Here are two elementary ways to get such a collection. 1. For any set A={a, b, c, ...} of primes, let A'={a, ab, abc, ...}. If A differs from B then A' has only a finite intersection with B'. 2. For each real number, e.g. x=0.3488012... form the set S_x={3, 34, 348, 3488, ...}. Different reals give almost disjoint sets. Problem B-5 Label the vertices of a trapezoid T (quadrilateral with two parallel sides) inscribed in the unit circle as A, B, C, D so that AB is parallel to CD and A, B, C, D are in counterclockwise order. Let s_1, s_2, and d denote the lengths of the line segments AB, CD, and OE, where E is the point of intersection of the diagonals of T, and O is the center of the circle. Determine the least upper bound of (s_1 - s_2) / d over all such T for which d \ne 0, and describe all cases, if any, in which it is attained. Solution: Center the circle at the origin and rotate the trapezoid so that AB and CD are horizontal. Assign coordinates to A and D, polar or rectangular depending on your taste. Now play with s_1 - s_2 / d for a while; eventually you'll find the simple form, after which maximization is easy. The answer, if I've calculated right, is 2, achieved when rotating the trapezoid by 90 degrees around the circle would take one vertex into another. (A right triangle, with the hypoteneuse the length-two diamater and d = 1, is a degenerate example.) Alternative solution: Let a be the distance from O (the center of the circle) to AB (that is the side with length s1), and b the distance from O to CD. Clearly, a = sqrt(1-s1*s1/4) and b = sqrt(1-s2*s2/4). Then with some mathematical jugglery, one can show that (s1-s2)/d = (s1*s1-s2*s2)/(b*s1-a*s2). Then differentiating this with respect to s1 and s2 and equating to 0 yields s1*s1+s2*s2=4, and hence s1=2*b and s2=2*a. The value of (s1-s2)/d for these values is then 2. Hence (s1-s1)/d achieves its extremeum when s1*s1+s2*s2=4 (that this value is actually a maximum is then easily seen), and the lub is 2. Problem B-6 Let (x_1, x_2, ..., x_n) be a point chosen at random from the n-dimensional region defined by 0 < x_1 < x_2 < ... < x_n < 1. Let f be a continuous function on [0, 1] with f(1) = 0. Set x_0 = 0 and x_{n+1} = 1. Show that the expected value of the Riemann sum \sum_{i = 0}^n (x_{i+1} - x_i) f(x_{i+1}) is \int_0^1 f(t)P(t) dt, where P is a polynomial of degree n, independent of f, with 0 \le P(t) \le 1 for 0 \le t \le 1. Solution: Induct right to left. Show that for each k, given x_{k-1}, the expected value at a point chosen with x_{k-1} < x_k < ... < x_n < 1 is a polynomial of the right type with the right degree. It's pretty easy once you find the right direction. 0 \le P(t) \le 1 comes for free: if P(t) is out of range at a point, it is out of range on an open interval, and setting f to the characteristic function of that interval produces a contradiction. ==> competition/tests/math/putnam/putnam.1992.p <== Problem A1 Prove that f(n) = 1 - n is the only integer-valued function defined on the integers that satisfies the following conditions. (i) f(f(n)) = n, for all integers n; (ii) f(f(n + 2) + 2) = n for all integers n; (iii) f(0) = 1. Problem A2 Define C(alpha) to be the coefficient of x^1992 in the power series expansion about x = 0 of (1 + x)^alpha. Evaluate \int_0^1 C(-y-1) ( 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/(y+1992) ) dy. Problem A3 For a given positive integer m, find all triples (n,x,y) of positive integers, with n relatively prime to m, which satisfy (x^2 + y^2)^m = (xy)^n. Problem A4 Let f be an infinitely differentiable real-valued function defined on the real numbers. If f(1/n) = n^2/(n^2 + 1), n = 1,2,3,..., compute the values of the derivatives f^(k)(0), k = 1,2,3,... . Problem A5 For each positive integer n, let a_n = { 0 if the number of 1's in the binary representation of n is even, 1 if the number of 1's in the binary representation of n is odd. Show that there do not exist positive integers k and m such that a_{k+j} = a_{k+m+j} = a_{k+2m+j}, for 0 <= j <= m - 1. Problem A6 Four points are chosen at random on the surface of a sphere. What is the probability that the center of the sphere lies inside the tetrahedron whose vertices are at the four points? (It is understood that each point is independently chosen relative to a uniform distribution on the sphere.) Problem B1 Let S be a set of n distinct real numbers. Let A_S be the set of numbers that occur as averages of two distinct elements of S. For a given n >= 2, what is the smallest possible number of distinct elements in A_S? Problem B2 For nonnegative integers n and k, define Q(n,k) to be the coefficient of x^k in the expansion of (1+x+x^2+x^3)^n. Prove that Q(n,k) = \sum_{j=0}^n {n \choose j} {n \choose k - 2j}, where {a \choose b} is the standard binomial coefficient. (Reminder: For integers a and b with a >= 0, {a \choose b} = a!/b!(a-b)! for 0 <= b <= a, and {a \choose b} = 0 otherwise.) Problem B3 For any pair (x,y) of real numbers, a sequence (a_n(x,y))_{n>=0} is defined as follows: a_0(x,y) = x a_{n+1}(x,y) = ( (a_n(x,y))^2 + y^2 ) / 2, for all n >= 0. Find the area of the region { (x,y) | (a_n(x,y))_{n>=0} converges }. Problem B4 Let p(x) be a nonzero polynomial of degree less than 1992 having no nonconstant factor in common with x^3 - x. Let ( d^1992 / dx^1992 ) ( p(x) / x^3 - x ) = f(x) / g(x) for polynomials f(x) and g(x). Find the smallest possible degree of f(x). Problem B5 Let D_n denote the value of the (n-1) by (n-1) determinant | 3 1 1 1 ... 1 | | 1 4 1 1 ... 1 | | 1 1 5 1 ... 1 | | 1 1 1 6 ... 1 | | . . . . ... . | | 1 1 1 1 ... n+1 | Is the set {D_n/n!}_{n >= 2} bounded? Problem B6 Let M be a set of real n by n matrices such that (i) I \in M, where I is the n by n identity matrix; (ii) if A \in M and B \in M, then either AB \in M or -AB \in M, but not both; (iii) if A \in M and B \in M, then either AB = BA or AB = -BA; (iv) if A \in M and A \noteq I, there is at least one B \in M such that AB = -BA. Prove that M contains at most n^2 matrices. ==> competition/tests/math/putnam/putnam.1992.s <== Now the unofficial solutions. Thanks to Noam Elkies for the B6 solution; thanks also to Peter Akemann, Greg John, and Peter Montgomery. The Putnam exam deserves criticism this year for an exceptional number of typos and poorly worded problems. How can someone taking the Putnam be sure that his solutions will be graded carefully, if the exam itself shows sloppy typography, grammar, and style? Problem A1 Prove that f(n) = 1 - n is the only integer-valued function defined on the integers that satisfies the following conditions. (i) f(f(n)) = n, for all integers n; (ii) f(f(n + 2) + 2) = n for all integers n; (iii) f(0) = 1. (The comma in (i) is wrong. Either ``conditions.'' should be ``conditions:'' or the semicolons should be periods. Little things...) Solution: Certainly if f(n) = 1 - n then (i), (ii), and (iii) hold. Conversely, say (i), (ii), and (iii) hold. We show that f(k) = 1 - k and f(1 - k) = k for every k >= 0. For k = 0 and 1 we have f(0) = 1 and f(1) = f(f(0)) = 0. For k >= 2, by induction we have f(k - 2) = 3 - k and f(3 - k) = k - 2. Note that f(n + 2) + 2 = f(f(f(n + 2) + 2)) = f(n). So f(k) = f(k - 2) - 2 = 1 - k and f(1 - k) = f(3 - k) + 2 = k as desired. As k and 1 - k for k >= 1 cover the integers, we are done. Problem A2 Define C(alpha) to be the coefficient of x^1992 in the power series expansion about x = 0 of (1 + x)^alpha. Evaluate \int_0^1 C(-y-1) ( 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/(y+1992) ) dy. Solution: C(alpha) is given by the usual binomial coefficient formula {alpha \choose 1992} = \alpha (\alpha - 1) ... (\alpha - 1991) / 1992!. Hence C(-y-1) = (-y-1)(-y-2)...(-y-1992)/1992! = (y+1)...(y+1992)/1992!. Set f(y) = (y+1)(y+2)...(y+1992). Now f has logarithmic derivative f'/f = ( 1/(y+1) + 1/(y+2) + ... + 1/(y+1992) ). Hence our integral equals \int_0^1 f(y)/1992! f'(y)/f(y) dy = \int_0^1 f'(y) dy/1992! = (f(1) - f(0))/1992! = (1993! - 1992!)/1992! = 1993 - 1 = 1992. Problem A3 For a given positive integer m, find all triples (n,x,y) of positive integers, with n relatively prime to m, which satisfy (x^2 + y^2)^m = (xy)^n. Solution: Certainly xy < x^2 + y^2 so m < n. Put n = m + k, k > 0. Let d be the greatest common divisor of x and y. Say x = ds, y = dt. Now d^{2m}(s^2 + t^2)^m = d^{2n}(st)^n, so (s^2 + t^2)^m = d^{2k}(st)^n. If a prime p divides s then p divides d^{2k}(st)^n = (s^2 + t^2)^m, so p must divide t. But s and t are relatively prime. Hence s = 1. Similarly t = 1. So d^{2k} = 2^m. Hence d is a power of 2, say d = 2^j, and m = 2jk. As n = m + k = 2jk + k we see that k is a common factor of m and n. Thus k = 1. So m = 2j, n = 2j + 1, x = y = d = 2^j. If m is odd then there are no solutions; if m is even then the only possible solution is (m + 1,2^{m/2},2^{m/2}). This does satisfy the given conditions. Problem A4 Let f be an infinitely differentiable real-valued function defined on the real numbers. If f(1/n) = n^2/(n^2 + 1), n = 1,2,3,..., compute the values of the derivatives f^(k)(0), k = 1,2,3,... . (``Let f be a foo. If bar, compute blah.'' Does this mean that one need only answer the question if ``bar'' happens to be true? May one choose his favorite f, such as f(x) = x, observe that it does not satisfy ``bar'', and [successfully] answer the question without computing anything? ``If ..., compute'' should be ``Assume ... . Compute''.) Solution: We first observe that the function g(x) = 1/(1 + x^2) satisfies all the known properties of f: it is infinitely differentiable, and g(1/n) = n^2/(n^2 + 1). From the Taylor expansion of g around 0, g(x) = 1 - x^2 + x^4 - x^6 + ..., we see that g^(k)(0) is 0 for k odd, (-1)^{k/2}k! for k even. Can f differ from g in its derivatives at 0? The difference h = f - g is an infinitely differentiable function with roots at 1/n for every positive n. We show that any such function has all derivatives 0 at 0. Suppose not. Take the least k >= 0 for which h^(k)(0) is nonzero. Without loss of generality say it is positive. By continuity h^(k) is positive in an open interval U around 0. Let S be the set of positive elements of U. Now h^(k-1) is increasing on S, and by minimality of k we have h^(k-1)(0) = 0, so h^(k-1) is positive on S. Then h^(k-2) is increasing on S, and h^(k-2)(0) = 0, so h^(k-2) is positive on S. In general h^j is positive on S for j down from k to 0 by induction. In particular h is positive on S, but this is impossible, as 1/n is in S for n sufficiently large. Thus f has all the same derivatives as g: f^(k)(0) is 0 for k odd, (-1)^{k/2}k! for k even. Alternative solution: Let g(x) = 1/(1 + x^2). We may compute the derivatives as before, and again the problem reduces to showing that all derivatives of f(x)-g(x) = h(x) vanish at 0. By continuity, h^(0) vanishes at 0. We now proceed by induction using the nth mean value theorem, which states that h(x) = h(0) + h'(0) + ... + h^(n-1)(0)/(n-1)! + h^(n)(\theta)/n!, where 0 <= \theta <= x. By induction, the derivatives up to the (n-1)-th vanish at 0, and if we take x = 1, 1/2, ... we get h^(n)(\theta_n) = 0, where 0 <= \theta_n <= 1/n. Hence \{\theta_n\} tends to 0. But h is infinitely differentiable, so h^n is infinitely differentiable and hence continuous. It follows that h^(n)(0) = 0. Yet another solution: Consider only n divided by l.c.m/(1,2,\ldots,k). f^(k)(0) = \lim_{n\rightarrow\infty} ( \sum_{i=0}^k {k\choose i}(-1)^{i+1} f(i/n) ) / (1/n)^k = \lim_{n\rightarrow\infty} ( \sum_{i=0}^k {k\choose i}(-1)^{i+1} g(i/n) ) / (1/n)^k =g^{k}(0)= \cos(\pi k/2) k! Or replace n by n*l.c.m.(1,2,\ldots,k) in the above and allow n to be any positive integer. Problem A5 For each positive integer n, let a_n = { 0 if the number of 1's in the binary representation of n is even, 1 if the number of 1's in the binary representation of n is odd. Show that there do not exist positive integers k and m such that a_{k+j} = a_{k+m+j} = a_{k+2m+j}, for 0 <= j <= m - 1. (Is every student supposed to know what the writer means by ``the binary representation of n''? Anyway, this problem is well known in some circles. I don't think Putnam writers should copy problems.) Solution: Let us suppose the opposite. Pick m minimal such that, for some k, a_{k+j} = a_{k+m+j} for every 0 <= j <= 2m - 1. The minimality guarantees that m is odd. (Indeed, say m = 2m'. If k = 2k' is even, then put j = 2j' for 0 <= j' <= m - 1 = 2m' - 1. Now a_n = a_{2n} so a_{k'+j'} = a_{k+j} = a_{k+m+j} = a_{k'+m'+j'} as desired. If on the other hand k = 2k' - 1 is odd, then put j = 2j' + 1 for 0 <= j' <= 2m' - 1. Now a_{k'+j'} = a_{k+j} = a_{k+m+j} = a_{k'+m'+j'} as desired.) We cannot have m = 1. Indeed, if a_k = a_{k+1} = a_{k+2}, then we have a_{2n} = a_{2n+1} for n = k/2 if k is even or n = (k+1)/2 if k is odd. But a_{2n} + a_{2n+1} = 1 always. Hence m is an odd number greater than 1. Define b_n = (a_n + a_{n-1}) mod 2. For 1 <= j <= 2m - 1 we have b_{k+j} = b_{k+m+j}. This range of j covers at least 5 values; we can certainly choose j so as to make k+j equal to 2 mod 4. Then k+m+j is odd. But b_n is 0 when n is 2 mod 4, and b_n is 1 when n is odd, so we have a contradiction. Problem A6 Four points are chosen at random on the surface of a sphere. What is the probability that the center of the sphere lies inside the tetrahedron whose vertices are at the four points? (It is understood that each point is independently chosen relative to a uniform distribution on the sphere.) Solution: Pick three points A, B, C, and consider the spherical triangle T defined by those points. The center of the sphere lies in the convex hull of A, B, C, and another point P if and only if it lies in the convex hull of T and P. This happens if and only if P is antipodal to T. So the desired probability is the expected fraction of the sphere's surface area which is covered by T. Denote the antipode to a point P by P'. We consider the eight spherical triangles ABC, A'BC, AB'C, A'B'C, ABC', A'BC', AB'C', A'B'C'. Denote these by T_0, T_1, T_2, T_3, T_4, T_5, T_6, T_7; we regard each T_i as a function of the random variables A, B, C. There is an automorphism of our probability space defined by (A,B,C) -> (A,B,C'). Hence T_0 and T_4 have the same distribution, and similarly T_1 and T_5, T_2 and T_6, and T_3 and T_7. Of course the same applies to B, so that T_0 and T_2, T_1 and T_3, T_4 and T_6, and T_5 and T_7 all have the same distribution. Finally T_0 and T_1, T_2 and T_3, T_4 and T_5, and T_6 and T_7 all have the same distribution. We conclude that all the T_i have exactly the same distribution. In particular the fractional area A_i of T_i has the same distribution for all i. On the other hand the total fractional area of all the T_i is exactly 1: the eight triangles cover the sphere exactly once. Hence each T_i has expected fractional area 1/8. In particular, T_0, the probability we wanted, has expected value 1/8. Note that this proof does not require the full strength of uniform distribution in the usual measure; nor does it require independence between all the variables. It requires only certain automorphisms of the probability space. Problem B1 Let S be a set of n distinct real numbers. Let A_S be the set of numbers that occur as averages of two distinct elements of S. For a given n >= 2, what is the smallest possible number of distinct elements in A_S? (``Smallest possible number of distinct elements in A_S''? Who talks about ``the number of _distinct_ elements'' of a set? How about just ``the number of elements''? Or ``the size''? Aargh. The quantifiers here are completely out of whack: n has to be fixed [not ``given''] before anything else, and it's not immediately clear that ``smallest possible'' refers to ``the minimum over all S''. Proposed rewrite: ``Fix n >= 2. For any set S of n real numbers, let A_S be the set of averages of two distinct elements of S. What is the minimum, over all S, of the size of A_S?'') Solution: We put the elements of S in order: s_1 < s_2 < ... < s_n. We have s_1 + s_2 < s_1 + s_3 < ... < s_1 + s_{n-1} < s_1 + s_n < s_2 + s_n < s_3 + s_n < ... < s_{n-1} + s_n. Hence the 2n - 3 averages (s_i + s_j)/2, i < j, with i = 1 or j = n, are all distinct. So A_S has size at least 2n - 3. This is achieved if, for instance, S = {1,2,...,n}. Problem B2 For nonnegative integers n and k, define Q(n,k) to be the coefficient of x^k in the expansion of (1+x+x^2+x^3)^n. Prove that Q(n,k) = \sum_{j=0}^n {n \choose j} {n \choose k - 2j}, where {a \choose b} is the standard binomial coefficient. (Reminder: For integers a and b with a >= 0, {a \choose b} = a!/b!(a-b)! for 0 <= b <= a, and {a \choose b} = 0 otherwise.) Solution: (1+x^2)(1+x) = 1+x+x^2+x^3, so (1+x^2)^n(1+x)^n = (1+x+x^2+x^3)^n, so (\sum {n\choose j} x^{2j}) (\sum {n\choose m} x^m) = \sum Q(n,k)x^k. The coefficient of x^k on the left is the sum of {n\choose j}{n\choose m} over all j,m with m + 2j = k, i.e., \sum_j {n\choose j}{n\choose k-2j}. Problem B3 For any pair (x,y) of real numbers, a sequence (a_n(x,y))_{n>=0} is defined as follows: a_0(x,y) = x a_{n+1}(x,y) = ( (a_n(x,y))^2 + y^2 ) / 2, for all n >= 0. Find the area of the region { (x,y) | (a_n(x,y))_{n>=0} converges }. (The parentheses in (a_n(x,y))^2 are confusing, as the writer also uses parentheses to denote the entire sequence of a_n.) Solution: Note that (x,y) and (x,-y) produce the same sequence, and (-x,y) and (x,y) produce the same sequence after the first step. So we will restrict attention to nonnegative x and y and quadruple our final answer. Fix x and y. Set f(z) = ( z^2 + y^2 ) / 2, so that a_n(x,y) = f(a_{n-1}(x,y)). Now f'(z) = z, so f is increasing on the positive reals. So (a_n(x,y))_n is monotone---either increasing, decreasing, or constant. We consider several (non-exclusive) possibilities. Case 1. Say y > 1. Then f(z) > (1 + z^2)/2 + (y - 1) >= z + (y - 1), so a_n(x,y) increases by at least y - 1 at each step. Case 2. Say f(x) < x. Then we have 0 < a_n(x,y) < a_{n-1}(x,y) <= x for every n. (Indeed, for n = 1 we have 0 < f(x) < x. For n >= 2 we have a_{n-1}(x,y) < a_{n-2}(x,y) by induction. So a_n(x,y) < a_{n-1}(x,y), as f is increasing.) As (a_n(x,y))_n is decreasing and bounded below, it converges. Case 3. Say f(x) > x > 1. Define g(z) = f(z) - z, so that g(x) > 0. We have g'(z) = z - 1, so g is increasing past 1. Now a_n(x,y) >= x + ng(x). (Indeed, for n = 1 we have a_1(x,y) = f(x) = x + g(x). For n >= 2 set a = a_{n-1}(x,y). We have a >= x + (n-1)g(x) > x by induction. So g(a) > g(x), and a_n(x,y) = f(a) = a + g(a) > a + g(x) >= x + ng(x) as desired.) So a_n increases without bound. Case 4. Say x < 1, y < 1. Then f(x) < f(1) < (1 + 1)/2 = 1. Similarly a_n(x,y) < 1 for every n. As (a_n(x,y))_n is bounded and monotone, it converges. Let's put this all together. For y > 1 the sequence diverges. For y < 1 and x < 1 the sequence does converge. For y < 1 and x > 1, the sequence converges if f(x) < x, and diverges if f(x) > x. The points we miss in this tally---y = 1, x = 1, f(x) = x---have zero total area. The condition f(x) < x is equivalent to (x-1)^2 + y^2 < 1, which describes a quarter-circle of radius 1 in the region y > 0, x > 1. Thus the total area for positive x and y is 1 (for the square y < 1, x < 1) plus pi/4 (for the quarter-circle). The final answer is quadruple this, or 4 + pi. Problem B4 Let p(x) be a nonzero polynomial of degree less than 1992 having no nonconstant factor in common with x^3 - x. Let ( d^1992 / dx^1992 ) ( p(x) / (x^3 - x) ) = f(x) / g(x) for polynomials f(x) and g(x). Find the smallest possible degree of f(x). (The second sentence is backwards---``let'' should be followed immediately by the variable being introduced. Would you say ``Let 2 equal x + y for integers x and y''?) Solution: First divide p(x) by x^3 - x: p(x) = (x^3 - x)q(x) + r(x), with r of degree at most 2. Now f(x)/g(x) = D^1992 (q(x) + r(x)/(x^3-x)) = D^1992 (r(x)/(x^3-x)), as q has degree less than 1992; here we write D for d/dx. We expand r(x)/(x^3-x) in partial fractions as -r(0)/x + r(1)/2(x-1) + r(-1)/2(x+1). Now the 1992nd derivative of this is Cr(0)/x^1993 + Cr(1)/(x-1)^1993 + Cr(-1)/(x+1)^1993 for a certain nonzero constant C which we don't care about. This then equals (Cr(0)(x^2-1)^1993 + Cr(1)(x^2+x)^1993 + Cr(-1)(x^2-x)^1993)/(x^3-x)^1993. The numerator and denominator here are coprime, for none of x, x-1, x+1 divide the numerator. (If, for instance, x divided the numerator, then r(0) would have to be 0, but then p(x) would have a factor of x in common with x^3-x, contrary to hypothesis.) So f(x) is a multiple of the numerator and g(x) is a multiple of the denominator. Our question is thus ``What is the smallest possible degree of the polynomial P = U(x^2-1)^1993 + V(x^2+x)^1993 + W(x^2-x)^1993, over all U, V, W which can arise as U=Cr(0), V=Cr(1), W=Cr(-1)?'' P has degree at most 2.1993. Its 2.1993 coefficient is U + V + W. Its 2.1993-1 coefficient is 1993V - 1993W. Its 2.1993-2 coefficient is -1993U + 1993.(1992/2)V + 1993.(1992/2)W. If all three of these are zero then by linear algebra all of U, V, W are zero, which is not possible. Hence P, and thus also f, has degree at least 2.1993-2, or double 1992. This is achieved if, for instance, p(x) = r(x) = 3x^2 - 2, so that r(0)+r(1)+r(-1)=-2+1+1=0 and r(1)=r(-1). (The degree restriction on p in this problem seems somewhat strange, though it simplifies the solution slightly. Noam Elkies notes that the ``nonzero constant C'' above will be zero---so that f will be 0--- if we're working over a field with characteristic dividing 1992!. Should the problem have explicitly identified the ground field as the reals?) Problem B5 Let D_n denote the value of the (n-1) by (n-1) determinant | 3 1 1 1 ... 1 | | 1 4 1 1 ... 1 | | 1 1 5 1 ... 1 | | 1 1 1 6 ... 1 | | . . . . ... . | | 1 1 1 1 ... n+1 | Is the set {D_n/n!}_{n >= 2} bounded? (``The value of the determinant''? Why not just ``the determinant''? Why talk about ``the set'' when it's much more common to talk about ``the sequence''? And where's the period on the first sentence?) Solution: No, it is the harmonic series. We subtract the first row from each of the other rows, to get a matrix 3 1 1 1 ... 1, -2 3 0 0 ... 0, -2 0 4 0 ... 0, ..., -2 0 0 0 ... n. Then we subtract 1/3 of the new second row from the first, 1/4 of the new third row from the first, and so on, to kill all the 1's along the top. We are left with a triangular matrix, with diagonal X 3 4 ... n, where X equals 3 - (-2)/3 - (-2)/4 - ... - (-2)/n = 3 + 2/3 + 2/4 + ... + 2/n = 2(1 + 1/2 + 1/3 + 1/4 + ... + 1/n). Thus the determinant is n! times 1 + 1/2 + 1/3 + ... + 1/n. Q. E. D. Problem B6 Let M be a set of real n by n matrices such that (i) I \in M, where I is the n by n identity matrix; (ii) if A \in M and B \in M, then either AB \in M or -AB \in M, but not both; (iii) if A \in M and B \in M, then either AB = BA or AB = -BA; (iv) if A \in M and A \noteq I, there is at least one B \in M such that AB = -BA. Prove that M contains at most n^2 matrices. Solution (courtesy Noam Elkies): Fix A in M. By (iii) AB = eBA, where e is either +1 or -1, for any B in M. Then AAB = AeBA = eABA = e^2BAA = BAA. So A^2 commutes with any B in M. Of course the same is true of -A^2. On the other hand by (ii) A^2 or -A^2 is in M. Pick C = A^2 or C = -A^2 so that C is in M. If C is not I, then by (iv) we can find a B in M such that CB = -BC. But we know CB = BC for any B in M. Thus CB = 0, which is impossible, as by (ii) no two elements of M can multiply to 0. We conclude that C must be I. In other words, for any A in M, either A^2 or -A^2 must be I. Now suppose M has more than n^2 matrices. The space of real n by n matrices has dimension n^2, so we can find a nontrivial linear relation \sum_{D in M} x_D D = 0. Pick such a relation with the smallest possible number of nonzero x_D. We will construct a smaller relation, obtaining a contradiction and finishing the proof. Pick an A with x_A nonzero, and multiply by it: \sum_{D in M} x_D DA = 0. In light of (ii) the matrices DA run over M modulo sign. Hence we have a new relation \sum_{E in M} y_E E = 0. The point of this transformation is that now the coefficient y_I of I is +- x_A, which is nonzero. Pick any C other than I such that y_C is nonzero. By (iv) pick B in M such that CB = -BC. Multiply \sum_{E in M} y_E E = 0 by B on both the left and the right, and add: \sum_{E in M} y_E (BE + EB) = 0. Now by (iii) we have BE + EB = (1 + e_{BE})BE, where e_{BE} is either +1 or -1. In particular e_{BI} = 1 (clear) and e_{BC} = -1 (by construction of B). So we get \sum_{E in M} y_E (1 + e_{BE}) BE = 0, where at least one term does not disappear and at least one term does disappear. As before the matrices BE run over M modulo sign. So we have a relation with fewer terms as desired. ---Dan Bernstein, brnstnd@ocf.berkeley.edu, 7 December 1992