home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Sunny 1,000 Collection
/
SUNNY1000.iso
/
Files
/
Dos
/
Boardak
/
INETPUZ.ZIP
/
COMPETIT.TXT
< prev
next >
Wrap
Text File
|
1995-02-05
|
252KB
|
6,178 lines
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 <stdio.h>
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 <stdio.h>
#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 <worm
| |
is not allowed.
E: Other
E.1 Rubik's cube
E.2 Magic cube
Make a magic cube with the numbers 1 - 27.
E.3 ==> 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) piles;
I take r bills from (p-r) piles.
(3) You take q(<p) bills from p or more piles;
I take (p-q) bills from q piles.
(4) You take q(<p) bills from r(<p) piles;
(a) q+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 <mark.longridge@canrem.com> 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 <dik@cwi.nl>
~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<N; i++) /* check for pre-existing combos */
if (x==data[i][0] &&
y==data[i][1] &&
z==data[i][2] &&
w==data[i][3] ) {
return -1; /* discard pre-existing*/
}
data[N-1][0] = x; /* make this the Nth combo */
data[N-1][1] = y;
data[N-1][2] = z;
data[N-1][3] = w;
sets = 0; /* start counting sets */
for (i=0; i<N; i++) /* look for sets */
for (j=i+1; j<N; j++)
for (k=j+1; k<N; k++) {
errors = 0;
for (m=0; m<4; m++) {
if (data[i][m] == data[j][m]) {
if (data[k][m] != data[i][m]) errors++;
if (data[k][m] != data[j][m]) errors++;
}
else {
if (data[k][m] == data[i][m]) errors++;
if (data[k][m] == data[j][m]) errors++;
}
}
if (errors == 0) /* no errors means is a set */
sets++; /* increment number of sets */
}
return sets;
}
--
I did some more experimenting. With the enclosed C program, I looked at many
randomly generated collections. In an earlier version of this program I
got one collection of 20 from a series of 100 trials. The rest were
collections
ranging in size from 16 to 19. Unfortunately, in an attempt to make this
program more readable and more general, I changed the algorithm slightly and
I haven't been able to achieve 20 since then. I can't remember enough about
my changes to be able to get back to the previous version. In the most recent
1000 trials all of the maximaml collections range in size from 16 to 18.
I think that this experiment has shed very little light on what is the
global maximum, since the search space is many orders of magnitude larger
than what can be tried in a reasonable amount of time through random
searching.
I assume that Mr. Ring found his collection of 20 by hand. This indicates
that an intelligent search may be more fruitful than a purely random one.
------------------ Program enclosed -------------
int n;
int data[81][4];
main()
{
int i;
for (i=0; i<1000; i++) { /* Do 1000 independent trials */
printf ("Trial %d:\n", i);
try();
}
}
try()
{
int i;
int x, y, z, w;
n = 0; /* set collection size to zero */
for (i=0; i<100; i++) { /* try 100 random combos */
x = 1 + rand()%3;
y = 1 + rand()%3;
z = 1 + rand()%3;
w = 1 + rand()%3;
check (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++)
check (x, y, z, w);
printf (" collection size=%d\n", n);
}
int check(x, y, z, w) /* check whether a new combo can be added */
int x, y, z, w;
{
int i,j,k,m;
int errors, sets;
for (i=0; i<n; i++) /* check for pre-existing combos */
if (x==data[i][0] &&
y==data[i][1] &&
z==data[i][2] &&
w==data[i][3] ) {
return -1; /* discard pre-existing*/
}
data[n][0] = x; /* make this the nth combo */
data[n][1] = y;
data[n][2] = z;
data[n][3] = w;
sets = 0; /* start counting sets */
for (i=0; i<=n; i++) /* look for sets */
for (j=i+1; j<=n; j++)
for (k=j+1; k<=n; k++) {
errors = 0;
for (m=0; m<4; m++) {
if (data[i][m] == data[j][m]) {
if (data[k][m] != data[i][m]) errors++;
if (data[k][m] != data[j][m]) errors++;
}
else {
if (data[k][m] == data[i][m]) errors++;
if (data[k][m] == data[j][m]) errors++;
}
}
if (errors == 0) /* no errors means is a set */
sets++; /* increment number of sets */
}
if (sets == 0) {
n++; /* increment collection size */
printf ("%d %d %d %d\n", x, y, z, w);
}
return sets;
}
------------------ end of enclosed program -------------
-- Gene
--
Gene Miller Multimedia Communications
NYNEX Science & Technology Phone: 914 644 2834
500 Westchester Avenue Fax: 914 997 2997, 914 644 2260
White Plains, NY 10604 Email: gene@nynexst.com
==> 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 <stdio.h>
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<rows[8]; row+=3 ) {
s = board[row[0]] + board[row[1]] + board[row[2]];
if ( s == 3 )
return ++won;
if ( s == 12 )
return ++lost;
}
return 0;
}
nextperm(c, n)
int c[], n;
{
int i = n-2, j=n-1, t;
while ( i >= 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 <v>; 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 <i*v> 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 3<chi(2)<8. Proves that chi(n) is finite for all n.
[6] P. Erd\"os, ``Problems and Results in Combinatorial Geometry,''
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 1-11.
States that 3<chi(n)<8 and ``I am almost sure that chi(2)>4.''
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<chi(2)<8. Calls the
graph in [3] the Moser graph. Quotes the result of Frankl and
Wilson [8] that chi(n) grows exponentially in n settling an
earlier conjecture of Erd\"os (I don't know the reference for
this). The best available bounds for this are
(1+ o(1)) (1.2)^n \le chi(n) \le (3+ o(1))^n.
[9] P. Frankl and R.M. Wilson, ``Intersection Theorems with Geometric
Consequences,'' Combinatorica #1 (1981), p. 357-368.
[10] H. Hadwiger, H. Debrunner, and V.L. Klee, ``Combinatorial
Geometry in the Plane,'' Holt, Rinehart & Winston, New York
(English edition, 1964).
[11] D.R. Woodall, ``Distances Realized by Sets Covering the Plane,''
Journal of Combinatorial Theory (A) #14 (1973), p. 187-200.
Among other things, shows that rational points in the plane can
be two colored.
[12] L. A. Sz\'ekely, ``Measurable Chromatic Number of Geometric
Graphs and Sets without some Distances in Euclidean Space,''
Combinatorica #4 (1984), p.213-218.
Considers \chi_m(R^2), the measurable chromatic number,
where sets of one color must be Lebesgue measurable.
He conjectures that \chi_m(R^2) is not equal to
\chi(R^2) (if the Axiom of Choice is false).
[13] Martin Gardner, ``Scientific American,'' October 1960, p. 160.
[14] Martin Gardner, ``Wheels, Life and other Mathematical Amusements,''
W.H. Freeman and Co., New York 1983, pages 195-196.
This occurs in a chapter on mathematical problems including
the 3x+1 problem. I think that his references are wrong, including
attributing the problem to Erd\"os and claiming that Charles Trigg
had original solutions in ``Problem 133,'' Crux Mathematicorum,
Vol. 2, 1976, pages 144-150.
Q.E.D.
\subproblem {(b)}
What if "three" is replaced by "nine"?
In this case, there does not necessarily exist two points of the same
color exactly one inch apart; this can be demonstrated by considering
a tessellation of the plane by a $3\times 3$ checkboard with side $2$,
with each component square a different color (color of boundary points
chosen in an obvious manner).
Q.E.D.
The length of the side of the checkerboard is not critical (the reader
my enjoy showing that $3/2 <$ side $< 3\sqrt{2}/2$ works).
\problem {A-5:}
Prove that there exists a {\it 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$.
\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'<e$, then $(n-e') - e' \sqrt{3} > (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