1669 views

Skip to first unread message

Aug 18, 1993, 2:04:18 AM8/18/93

to

Archive-name: puzzles/archive/Instructions

Last-modified: 17 Aug 1993

Version: 4EMAIL

Last-modified: 17 Aug 1993

Version: 4

==> Instructions <==

Instructions for Accessing rec.puzzles Archive

INTRODUCTION

Below is a list of puzzles, categorized by subject area. Each puzzle

includes a solution, compiled from various sources, which is supposed

to be definitive.

To request a puzzle, send a message to archive...@questrel.com like:

return_address your_name@your_site.your_domain

send requested_puzzle_name

For example, if your net address is "mic...@disneyland.com", to request

"decision/allais.p", send the message:

return_address mic...@disneyland.com

send allais

To request multiple puzzles, use several "send" lines in a message.

Please refrain from requesting the entire archive via email. Use FTP.

FTP

The archive has been posted to news.answers and rec.answers, which are

archived in the periodic posting archive on rtfm.mit.edu in the

anonymous ftp directory /pub/usenet.

Other archives are:

ftp.cs.ruu.nl [131.211.80.17] in the anonymous ftp

directory /pub/NEWS.ANSWERS (also accessible via mail

server requests to mail-...@cs.ruu.nl)

cnam.cnam.fr [192.33.159.6] in the anonymous ftp directory /pub/FAQ

ftp.uu.net [137.39.1.9 or 192.48.96.9] in the anonymous ftp

directory /usenet

ftp.win.tue.nl [131.155.70.100] in the anonymous ftp directory

/pub/usenet/news.answers

grasp1.univ-lyon1.fr [134.214.100.25] in the anonymous ftp

directory /pub/faq (also accessible via mail server

requests to list...@grasp1.univ-lyon1.fr), which is

best used by EASInet sites and sites in France that do

not have better connectivity to cnam.cnam.fr (e.g.

Lyon, Grenoble)

Note that the periodic posting archives on rtfm.mit.edu are also

accessible via Prospero and WAIS (the database name is "usenet" on port

210).

CREDIT

The archive is NOT the original work of the editor (just in case you were

wondering :^).

In keeping with the general net practice on FAQ's, I do not as a rule assign

credit for solutions. There are many reasons for this:

1. The archive is about the answers to the questions, not about assigning

credit.

2. Many people, in providing free answers to the net, do not have the time

to cite their sources.

3. I cut and paste freely from several people's solutions in most cases

to come up with as complete an answer as possible.

4. I use sources other than postings.

5. I am neither qualified nor motivated to assign credit.

However, I do whenever possible put bibliographies in archive entries, and

I see the inclusion of the net addresses of interested parties as a

logical extension of this practice. In particular, if you wrote a

program to solve a problem and posted the source code of the program,

you are presumed to be interested in corresponding with others about

the problem. So, please let me know the entries you would like to be

listed in and I will be happy to oblige.

Address corrections or comments to archive...@questrel.com.

INDEX

==> bicycle (analysis) <==

A boy, a girl and a dog go for a 10 mile walk. The boy and girl can

==> boy.girl.dog (analysis) <==

A boy, a girl and a dog are standing together on a long, straight road.

==> bugs (analysis) <==

Four bugs are placed at the corners of a square. Each bug walks always

==> c.infinity (analysis) <==

What function is zero at zero, strictly positive elsewhere, infinitely

==> cache (analysis) <==

Cache and Ferry (How far can a truck go in a desert?)

==> calculate.pi (analysis) <==

How can I calculate many digits of pi?

==> cats.and.rats (analysis) <==

If 6 cats can kill 6 rats in 6 minutes, how many cats does it take to

==> dog (analysis) <==

A body of soldiers form a 50m-by-50m square ABCD on the parade ground.

==> e.and.pi (analysis) <==

Without finding their numerical values, which is greater, e^(pi) or (pi)^e?

==> functional/distributed (analysis) <==

Find all f: R -> R, f not identically zero, such that

==> functional/linear (analysis) <==

Suppose f is non-decreasing with

==> integral (analysis) <==

If f is integrable on (0,inf) and differentiable at 0, and a > 0, and:

==> irrational.stamp (analysis) <==

You have an ink stamp which is so amazingly precise that, when inked

==> minimum.time (analysis) <==

N people can walk or drive in a two-seater to go from city A to city B. What

==> particle (analysis) <==

What is the longest time that a particle can take in travelling between two

==> period (analysis) <==

What is the least possible integral period of the sum of functions

==> rubberband (analysis) <==

A bug walks down a rubber band which is attached to a wall at one end and a car

==> sequence (analysis) <==

Show that in the sequence: x, 2x, 3x, .... (n-1)x (x can be any real number)

==> snow (analysis) <==

Snow starts falling before noon on a cold December day. At noon a

==> tower (analysis) <==

R = N ^ (N ^ (N ^ ...)). What is the maximum N>0 that will yield a finite R?

==> 7-11 (arithmetic/part1) <==

A customer at a 7-11 store selected four items to buy, and was told

==> arithmetic.progression (arithmetic/part1) <==

Is there an arithmetic progression of 20 or more primes?

==> clock/day.of.week (arithmetic/part1) <==

It's restful sitting in Tom's cosy den, talking quietly and sipping

==> clock/palindromic (arithmetic/part1) <==

How many times per day does a digital clock display a palindromic number?

==> clock/reversible (arithmetic/part1) <==

How many times per day can the hour and minute hands on an analog clock switch

==> clock/right.angle (arithmetic/part1) <==

How many times per day do the hour and minute hands of a clock form a

==> clock/thirds (arithmetic/part1) <==

Do the 3 hands on a clock ever divide the face of the clock into 3

==> consecutive.composites (arithmetic/part1) <==

Are there 10,000 consecutive non-prime numbers?

==> consecutive.product (arithmetic/part1) <==

Prove that the product of three or more consecutive positive integers cannot

==> consecutive.sums (arithmetic/part1) <==

Find all series of consecutive positive integers whose sum is exactly 10,000.

==> conway (arithmetic/part1) <==

Describe the sequence a(1)=a(2)=1, a(n) = a(a(n-1)) + a(n-a(n-1)) for n>2.

==> digits/6.and.7 (arithmetic/part1) <==

Does every number which is not divisible by 5 have a multiple whose

==> digits/all.ones (arithmetic/part1) <==

Prove that some multiple of any integer ending in 3 contains all 1s.

==> digits/arabian (arithmetic/part1) <==

What is the Arabian Nights factorial, the number x such that x! has 1001

==> digits/circular (arithmetic/part1) <==

What 6 digit number, with 6 different digits, when multiplied by all integers

==> digits/divisible (arithmetic/part1) <==

Find the least number using 0-9 exactly once that is evenly divisible by each

==> digits/equations/123456789 (arithmetic/part1) <==

In how many ways can "." be replaced with "+", "-", or "" (concatenate) in

==> digits/equations/1992 (arithmetic/part1) <==

1 = -1+9-9+2. Extend this list to 2 through 100 on the left side of

==> digits/equations/24 (arithmetic/part1) <==

Form an expression that evaluates to 24 that contains two 3's, two 7's,

==> digits/equations/383 (arithmetic/part1) <==

Make 383 out of 1,2,25,50,75,100 using +,-,*,/.

==> digits/equations/find (arithmetic/part1) <==

Write a program for finding expressions built out of given numbers and using

==> digits/extreme.products (arithmetic/part1) <==

What are the extremal products of three three-digit numbers using digits 1-9?

==> digits/labels (arithmetic/part1) <==

You have an arbitrary number of model kits (which you assemble for

==> digits/least.significant/factorial (arithmetic/part1) <==

What is the least significant non-zero digit in the decimal expansion of n!?

==> digits/least.significant/tower.of.power (arithmetic/part1) <==

What are the least significant digits of 9^(8^(7^(6^(5^(4^(3^(2^1))))))) ?

==> digits/most.significant/googol (arithmetic/part1) <==

What digits does googol! start with?

==> digits/most.significant/powers (arithmetic/part1) <==

What is the probability that 2^N begins with the digits 603245?

==> digits/nine.digits (arithmetic/part1) <==

Form a number using 0-9 once with its first n digits divisible by n.

==> digits/palindrome (arithmetic/part1) <==

Does the series formed by adding a number to its reversal always end in

==> digits/palintiples (arithmetic/part1) <==

Find all numbers that are multiples of their reversals.

==> digits/power.two (arithmetic/part1) <==

Prove that for any 9-digit number (base 10) there is an integral power

==> digits/prime/101 (arithmetic/part1) <==

How many primes are in the sequence 101, 10101, 1010101, ...?

==> digits/prime/all.prefix (arithmetic/part1) <==

What is the longest prime whose every proper prefix is a prime?

==> digits/prime/change.one (arithmetic/part1) <==

What is the smallest number that cannot be made prime by changing a single

==> digits/prime/prefix.one (arithmetic/part1) <==

2 is prime, but 12, 22, ..., 92 are not. Similarly, 5 is prime

==> digits/reverse (arithmetic/part1) <==

Is there an integer that has its digits reversed after dividing it by 2?

==> digits/rotate (arithmetic/part1) <==

Find integers where multiplying them by single digits rotates their digits

==> digits/sesqui (arithmetic/part1) <==

Find the least number where moving the first digit to the end multiplies by 1.5.

==> digits/squares/change.leading (arithmetic/part1) <==

What squares remain squares when their leading digits are incremented?

==> digits/squares/length.22 (arithmetic/part1) <==

Is it possible to form two numbers A and B from 22 digits such that

==> digits/squares/length.9 (arithmetic/part1) <==

Is it possible to make a number and its square, using the digits from 1

==> digits/squares/three.digits (arithmetic/part2) <==

What squares consist entirely of three digits (e.g., 1, 4, and 9)?

==> digits/squares/twin (arithmetic/part2) <==

Let a twin be a number formed by writing the same number twice,

==> digits/sum.of.digits (arithmetic/part2) <==

Find sod ( sod ( sod (4444 ^ 4444 ) ) ).

==> digits/zeros/million (arithmetic/part2) <==

How many zeros occur in the numbers from 1 to 1,000,000?

==> digits/zeros/trailing (arithmetic/part2) <==

How many trailing zeros are in the decimal expansion of n!?

==> magic.squares (arithmetic/part2) <==

Are there large squares, containing only consecutive integers, all of whose

==> pell (arithmetic/part2) <==

Find integer solutions to x^2 - 92y^2 = 1.

==> subset (arithmetic/part2) <==

Prove that all sets of n integers contain a subset whose sum is divisible by n.

==> sum.of.cubes (arithmetic/part2) <==

Find two fractions whose cubes total 6.

==> sums.of.powers (arithmetic/part2) <==

Partition 1,2,3,...,16 into two equal sets, such that the sums of the

==> tests.for.divisibility/eleven (arithmetic/part2) <==

What is the test to see if a number is divisible by eleven?

==> tests.for.divisibility/nine (arithmetic/part2) <==

What is the test to see if a number is divisible by nine?

==> tests.for.divisibility/seven (arithmetic/part2) <==

What is the test to see if a number is divisible by seven?

==> tests.for.divisibility/three (arithmetic/part2) <==

What is the test to see if a number is divisible by three?

==> alphabet.blocks (combinatorics) <==

What is the minimum number of dice painted with one letter on all six sides

==> coinage/combinations (combinatorics) <==

Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many

==> coinage/dimes (combinatorics) <==

"Dad wants one-cent, two-cent, three-cent, five-cent, and ten-cent

==> coinage/impossible (combinatorics) <==

What is the smallest number of coins that you can't make a dollar with?

==> color (combinatorics) <==

An urn contains n balls of different colors. Randomly select a pair, repaint

==> full (combinatorics) <==

Consider a string that contains all substrings of length n. For example,

==> gossip (combinatorics) <==

n people each know a different piece of gossip. They can telephone each other

==> grid.dissection (combinatorics) <==

How many (possibly overlapping) squares are in an mxn grid? Assume that all

==> permutation (combinatorics) <==

Compute the nth permutation of k numbers (or objects).

==> subsets (combinatorics) <==

Out of the set of integers 1,...,100 you are given ten different

==> transitions (combinatorics) <==

How many n-bit binary strings (0/1) have exactly k transitions

==> contests/games.magazine (competition/part1) <==

What are the best answers to various contests run by _Games_ magazine?

==> contests/national.puzzle/npc.1993 (competition/part1) <==

What are the solutions to the Games magazine 1993 National Puzzle Contest?

==> games/bridge (competition/part1) <==

Are there any programs for solving double-dummy Bridge?

==> games/chess/knight.control (competition/part1) <==

How many knights does it take to attack or control the board?

==> games/chess/knight.most (competition/part1) <==

What is the maximum number of knights that can be put on n x n chessboard

==> games/chess/knight.tour (competition/part1) <==

For what size boards are knight tours possible?

==> games/chess/mutual.stalemate (competition/part1) <==

What's the minimal number of pieces in a legal mutual stalemate?

==> games/chess/queen.control (competition/part1) <==

How many queens does it take to attack or control the board?

==> games/chess/queen.most (competition/part1) <==

How many non-mutually-attacking queens can be placed on various sized boards?

==> games/chess/queens (competition/part1) <==

How many ways can eight queens be placed so that they control the board?

==> games/chess/rook.paths (competition/part1) <==

How many non-overlapping paths can a rook take from one corner to the opposite

==> games/chess/size.of.game.tree (competition/part1) <==

How many different positions are there in the game tree of chess?

==> games/cigarettes (competition/part1) <==

The game of cigarettes is played as follows:

==> games/connect.four (competition/part1) <==

Is there a winning strategy for Connect Four?

==> games/craps (competition/part1) <==

What are the odds in craps?

==> games/crosswords (competition/part1) <==

Are there programs to make crosswords? What are the rules for cluing cryptic

==> games/cube (competition/part2) <==

What are some games involving cubes?

==> games/go-moku (competition/part2) <==

For a game of k in a row on an n x n board, for what values of k and n is

==> games/hi-q (competition/part2) <==

What is the quickest solution of the game Hi-Q (also called Solitaire)?

==> games/jeopardy (competition/part2) <==

What are the highest, lowest, and most different scores contestants

==> games/nim (competition/part2) <==

Place 10 piles of 10 $1 bills in a row. A valid move is to reduce

==> games/online/online.scrabble (competition/part2) <==

How can I play Scrabble online on the Internet?

==> games/online/unlimited.adventures (competition/part2) <==

Where can I find information about unlimited adventures?

==> games/othello (competition/part2) <==

How good are computers at Othello?

==> games/pc/best (competition/part2) <==

What are the best PC games?

==> games/pc/reviews (competition/part2) <==

Are reviews of PC games available online?

==> games/pc/solutions (competition/part2) <==

What are the solutions to various popular PC games?

==> games/poker.face.up (competition/part2) <==

In Face-Up Poker, two players each select five cards from a face-up deck,

==> games/risk (competition/part2) <==

What are the odds when tossing dice in Risk?

==> games/rubiks/rubiks.clock (competition/part2) <==

How do you quickly solve Rubik's clock?

==> games/rubiks/rubiks.cube (competition/part3) <==

What is known about bounds on solving Rubik's cube?

==> games/rubiks/rubiks.magic (competition/part3) <==

How do you solve Rubik's Magic?

==> games/scrabble (competition/part3) <==

What are some exceptional Scrabble Brand Crossword Game (TM) games?

==> games/set (competition/part3) <==

What is the size of the largest collection of cards from which NO "set"

==> games/soma (competition/part3) <==

What is the solution to Soma Cubes?

==> games/square-1 (competition/part3) <==

Does anyone have any hints on how to solve the Square-1 puzzle?

==> games/think.and.jump (competition/part3) <==

THINK & JUMP: FIRST THINK, THEN JUMP UNTIL YOU

==> games/tictactoe (competition/part3) <==

In random tic-tac-toe, what is the probability that the first mover wins?

==> tests/analogies/long (competition/part3) <==

1. Host : Guest :: Cynophobia : ?

==> tests/analogies/pomfrit (competition/part3) <==

1. NATURAL: ARTIFICIAL :: ANKYLOSIS: ?

==> tests/analogies/quest (competition/part3) <==

1. Mother: Maternal :: Stepmother: ?

==> tests/math/putnam/putnam.1967 (competition/part3) <==

==> tests/math/putnam/putnam.1987 (competition/part4) <==

WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

==> tests/math/putnam/putnam.1988 (competition/part4) <==

Problem A-1: Let R be the region consisting of the points (x,y) of the

==> tests/math/putnam/putnam.1990 (competition/part4) <==

Problem A-1

==> tests/math/putnam/putnam.1992 (competition/part5) <==

Problem A1

==> Beale (cryptology) <==

What are the Beale ciphers?

==> Feynman (cryptology) <==

What are the Feynman ciphers?

==> Voynich (cryptology) <==

What are the Voynich ciphers?

==> swiss.colony (cryptology) <==

What are the 1987 Swiss Colony ciphers?

==> vcrplus (cryptology) <==

What is the code used by VCR+?

==> allais (decision) <==

The Allais Paradox involves the choice between two alternatives:

==> division (decision) <==

N-Person Fair Division

==> dowry (decision) <==

Sultan's Dowry

==> envelope (decision) <==

Someone has prepared two envelopes containing money. One contains twice as

==> exchange (decision) <==

At one time, the Canadian and US dollars were discounted by 10 cents on

==> high.or.low (decision) <==

I pick two numbers, randomly, and tell you one of them. You are supposed

==> monty.hall (decision) <==

You are a participant on "Let's Make a Deal." Monty Hall shows you

==> newcomb (decision) <==

Newcomb's Problem

==> prisoners (decision) <==

Three prisoners on death row are told that one of them has been chosen

==> red (decision) <==

I show you a shuffled deck of standard playing cards, one card at a

==> rotating.table (decision) <==

Four glasses are placed upside down in the four corners of a square

==> stpetersburg (decision) <==

What should you be willing to pay to play a game in which the payoff is

==> truel (decision) <==

A, B, and C are to fight a three-cornered pistol duel. All know that

==> K3,3 (geometry/part1) <==

Can three houses be connected to three utilities without the pipes crossing?

==> bear (geometry/part1) <==

If a hunter goes out his front door, goes 50 miles south, then goes 50

==> bisector (geometry/part1) <==

Prove if two angle bisectors of a triangle are equal, then the triangle is

==> calendar (geometry/part1) <==

Build a calendar from two sets of cubes. On the first set, spell the

==> circles.and.triangles (geometry/part1) <==

Find the radius of the inscribed and circumscribed circles for a triangle.

==> coloring/cheese.cube (geometry/part1) <==

A cube of cheese is divided into 27 subcubes. A mouse starts at one

==> coloring/triominoes (geometry/part1) <==

There is a chess board (of course with 64 squares). You are given 21

==> construction/4.triangles.6.lines (geometry/part1) <==

Can you construct 4 equilateral triangles with 6 toothpicks?

==> construction/5.lines.with.4.points (geometry/part1) <==

Arrange 10 points so that they form 5 rows of 4 each.

==> construction/square.with.compass (geometry/part1) <==

Construct a square with only a compass and a straight edge.

==> corner (geometry/part1) <==

A hallway of width A turns through 90 degrees into a hallway of width

==> cover.earth (geometry/part1) <==

A thin membrane covers the surface of the (spherical) earth. One

==> cycle.polynomial (geometry/part1) <==

What are the cycle polynomials for the Platonic solids?

==> dissections/disk (geometry/part1) <==

Can a disk be cut into similar pieces without point symmetry about the

==> dissections/hexagon (geometry/part1) <==

Divide the hexagon into:

==> dissections/largest.circle (geometry/part1) <==

What is the largest circle that can be assembled from two semicircles cut from

==> dissections/square.70 (geometry/part1) <==

Since 1^2 + 2^2 + 3^2 + ... + 24^2 = 70^2, can a 70x70 square be dissected into

==> dissections/square.five (geometry/part1) <==

Can you dissect a square into 5 parts of equal area with just a straight edge?

==> dissections/tesseract (geometry/part1) <==

If you suspend a cube by one corner and slice it in half with a

==> duck.and.fox (geometry/part1) <==

A duck is swimming about in a circular pond. A ravenous fox (who cannot

==> earth.band (geometry/part1) <==

How much will a band around the equator rise above the surface if it is

==> fence (geometry/part1) <==

A farmer wishes to enclose the maximum possible area with 100 meters of fence.

==> ham.sandwich (geometry/part1) <==

Consider a ham sandwich, consisting of two pieces of bread and one of

==> hike (geometry/part1) <==

You are hiking in a half-planar woods, exactly 1 mile from the edge,

==> hole.in.sphere (geometry/part1) <==

Old Boniface he took his cheer,

==> hypercube (geometry/part1) <==

How many vertices, edges, faces, etc. does a hypercube have?

==> kissing.number (geometry/part1) <==

How many n-dimensional unit spheres can be packed around one unit sphere?

==> konigsberg (geometry/part1) <==

Can you draw a line through each edge on the diagram below without crossing

==> ladders (geometry/part1) <==

Two ladders form a rough X in an alley. The ladders are 11 and 13 meters

==> lattice/area (geometry/part1) <==

Prove that the area of a triangle formed by three lattice points is integer/2.

==> lattice/equilateral (geometry/part1) <==

Can an equlateral triangle have vertices at integer lattice points?

==> manhole.cover (geometry/part1) <==

Why is a manhole cover round?

==> pentomino (geometry/part1) <==

Arrange pentominos in 3x20, 4x15, 5x12, 6x10, 2x3x10, 2x5x6 and 3x4x5 forms.

==> points.in.sphere (geometry/part1) <==

What is the expected distance between two random points inside a sphere?

==> points.on.sphere (geometry/part1) <==

What are the odds that n random points on a sphere lie in the same hemisphere?

==> revolutions (geometry/part1) <==

A circle with radius 1 rolls without slipping once around a circle with radius

==> rotation (geometry/part1) <==

What is the smallest rotation that returns an object to its original state?

==> shephard.piano (geometry/part1) <==

What's the maximum area shape that will fit around a right-angle corner?

==> smuggler (geometry/part1) <==

Somewhere on the high sees smuggler S is attempting, without much

==> spiral (geometry/part1) <==

How far must one travel to reach the North Pole if one starts from the

==> table.in.corner (geometry/part1) <==

Put a round table into a (perpendicular) corner so that the table top

==> tetrahedron (geometry/part1) <==

Suppose you have a sphere of radius R and you have four planes that are

==> tiling/count.1x2 (geometry/part1) <==

Count the ways to tile an MxN rectangle with 1x2 dominos.

==> tiling/rational.sides (geometry/part1) <==

A rectangular region R is divided into rectangular areas. Show that if

==> tiling/rectangles.with.squares (geometry/part2) <==

Given two sorts of squares, (axa) and (bxb), what rectangles can be tiled?

==> tiling/scaling (geometry/part2) <==

A given rectangle can be entirely covered (i.e. concealed) by an

==> tiling/seven.cubes (geometry/part2) <==

Consider 7 cubes of equal size arranged as follows. Place 5 cubes so

==> topology/fixed.point (geometry/part2) <==

A man hikes up a mountain, and starts hiking at 2:00 in the afternoon

==> touching.blocks (geometry/part2) <==

Can six 1x2x4 blocks be arranged so that each block touches n others, for all n?

==> trigonometry/euclidean.numbers (geometry/part2) <==

For what numbers x is sin(x) expressible using only integers, +, -, *, / and

==> trigonometry/inequality (geometry/part2) <==

Show that (sin x)^(sin x) < (cos x)^(cos x) when 0 < x < pi/4.

==> group.01 (group) <==

AEFHIKLMNTVWXYZ BCDGJOPQRSU

==> group.01a (group) <==

147 0235689

==> group.02 (group) <==

ABEHIKMNOTXZ CDFGJLPQRSUVWY

==> group.03 (group) <==

BEJQXYZ DFGHLPRU KSTV CO AIW MN

==> group.04 (group) <==

BDO P ACGIJLMNQRSUVWZ EFTY HKX

==> group.05 (group) <==

CEFGHIJKLMNSTUVWXYZ ADOPQR B

==> group.06 (group) <==

BCEGKMQSW DFHIJLNOPRTUVXYZ

==> group.07 (group) <==

CDEFLOPTZ ABGHIJKMNQRSUVWXY

==> group.08 (group) <==

COS ABDEFGHIJKLMNPQRTUVWXYZ

==> group.09 (group) <==

CDILMVX ABEFGHJKNOPQRSTUWYZ

==> group.10 (group) <==

AHIMOTUVWXY BCDEFGJKLNPQRSZ

==> group.11 (group) <==

BCDIJLMNOPQRSUVWZ AEFGHKTXY

==> group.12 (group) <==

COPSUVWXZ ABDEFGHIJKLMNQRTY

==> group.13 (group) <==

BCDEHIKOX AFGJLMNPQRSTUVWYZ

==> group.14 (group) <==

EHIS MOT ABCDFGJKLNPQRUVWXYZ

==> group.15 (group) <==

HIOX ABCDEFGJKLMNPQRSTUVWYZ

==> group.16 (group) <==

IJ ABCDEFGHKLMNOPQRSTUVWXYZ

==> group.17 (group) <==

J BDFHIKLT GPQY ACEMNORSUVWXZ

==> handshake (induction) <==

A married couple organizes a party. They only invite other married

==> hanoi (induction) <==

Is there an algorithm for solving the Hanoi tower puzzle for any number

==> n-sphere (induction) <==

With what odds do three random points on an n-sphere form an acute triangle?

==> paradox (induction) <==

Is there a non-trivial property that holds for the first 10,000 positive

==> party (induction) <==

You're at a party. Any two (different) people at the party have exactly one

==> roll (induction) <==

An ordinary die is thrown until the running total of the throws first

==> takeover (induction) <==

After graduating from college, you have taken an important managing position

==> close.antonyms (language/part1) <==

What words are similar to their antonyms in other langauges?

==> dutch/dutch.record (language/part1) <==

What are some Dutch words with unusual properties?

==> english/equations (language/part1) <==

1 = E. on a C.

==> english/etymology/acronym (language/part1) <==

What acronyms have become common words or are otherwise interesting?

==> english/etymology/fossil (language/part1) <==

What are some examples of idioms that include obsolete words?

==> english/etymology/portmanteau (language/part1) <==

What are some words formed by combining together parts of other words?

==> english/frequency (language/part1) <==

In the English language, what are the most frequently appearing:

==> english/idioms (language/part1) <==

List some idioms that say the opposite of what they mean.

==> english/less.ness (language/part1) <==

Find a word that forms two other words, unrelated in meaning, when "less"

==> english/letter.rebus (language/part1) <==

Define the letters of the alphabet using self-referential common phrases (e.g.,

==> english/malaprop (language/part1) <==

List some phrases with the same meaning that differ by one sound.

==> english/piglatin (language/part1) <==

What words in pig latin also are words?

==> english/pleonasm (language/part1) <==

What are some redundant terms that occur frequently (like "ABM missile")?

==> english/plurals/collision (language/part1) <==

Two words, spelled and pronounced differently, have plurals spelled

==> english/plurals/doubtful.number (language/part1) <==

A little word of doubtful number,

==> english/plurals/drop.terminal (language/part1) <==

What words have their plurals formed by dropping the final letter?

==> english/plurals/endings (language/part1) <==

List a plural ending with each letter of the alphabet.

==> english/plurals/man (language/part1) <==

Words ending with "man" make their plurals by adding "s".

==> english/plurals/switch.first (language/part1) <==

What plural is formed by switching the first two letters?

==> english/potable.color (language/part1) <==

Find words that are both beverages and colors.

==> english/pronunciation/autonym (language/part1) <==

What is the longest word whose phonetic and normal spellings are the same?

==> english/pronunciation/homograph/different.pronunciation (language/part1) <==

What sequence of letters has the most different pronunciations?

==> english/pronunciation/homograph/homographs (language/part1) <==

List some homographs (words spelled the same but pronounced differently)

==> english/pronunciation/homophone/homophones.alphabet (language/part1) <==

Homophones can be confusing when used to exemplify a letter. For example,

==> english/pronunciation/homophone/homophones.letter (language/part1) <==

For each letter, list homophones that differ by that letter.

==> english/pronunciation/homophone/homophones.most (language/part1) <==

What words have four or more spellings that sound alike?

==> english/pronunciation/homophone/trivial (language/part2) <==

Consider the free non-abelian group on the twenty-six letters of the

==> english/pronunciation/oronym (language/part2) <==

List some oronyms (phrases or sentences that can be read in two ways

==> english/pronunciation/phonetic.letters (language/part2) <==

What does "FUNEX" mean?

==> english/pronunciation/rhyme (language/part2) <==

What English words are hard to rhyme?

==> english/pronunciation/silent.letter (language/part2) <==

For each letter, what word contains that letter silent?

==> english/pronunciation/silent.most (language/part2) <==

What word has the most silent letters in a row?

==> english/pronunciation/syllable (language/part2) <==

What words have an exceptional number of letters per syllable?

==> english/pronunciation/telegrams (language/part2) <==

Since telegrams cost by the word, phonetically similar messages can be cheaper.

==> english/puns (language/part2) <==

Where can I find a collection of puns?

==> english/rare.trigraphs (language/part2) <==

What trigraphs (three-letter combinations) occur in only one word?

==> english/self.ref/self.ref.letters (language/part2) <==

Construct a true sentence of the form: "This sentence contains _ a's, _ b's,

==> english/self.ref/self.ref.numbers (language/part2) <==

What true sentence has the form: "There are _ 0's, _ 1's, _ 2's, ...,

==> english/self.ref/self.ref.words (language/part2) <==

What sentence describes its own word, syllable and letter count?

==> english/sentences/behead (language/part2) <==

Is there a sentence that remains a sentence when all its words are beheaded?

==> english/sentences/charades (language/part2) <==

A ....... surgeon was ....... to operate because he had .......

==> english/sentences/emphasis (language/part2) <==

List some sentences that change meaning when the emphasis is moved.

==> english/sentences/pangram (language/part2) <==

A "pangram" is a sentence containing all 26 letters.

==> english/sentences/repeated.words (language/part2) <==

What is a sentence with the same word several times repeated? Do not use

==> english/sentences/sentence (language/part2) <==

Find a sentence with words beginning with the letters of the alphabet, in order.

==> english/sentences/snowball (language/part2) <==

Construct the longest coherent sentence you can such that the nth word

==> english/sentences/weird (language/part2) <==

Make a sentence containing only words that violate the "i before e" rule.

==> english/sentences/word.boundaries (language/part2) <==

List some sentences that can be radically altered by changing word boundaries

==> english/spelling/gry (language/part2) <==

Find three completely different words ending in "gry."

==> english/spelling/j.ending (language/part2) <==

What words and names end in j?

==> english/spelling/lipograms (language/part2) <==

What books have been written without specific letters, vowels, etc.?

==> english/spelling/longest (language/part2) <==

What is the longest word in the English language?

==> english/spelling/most (language/part2) <==

What word has the most variant spellings?

==> english/spelling/near.palindrome (language/part2) <==

What are some long near palindromes, i.e., words that except for one

==> english/spelling/operations.on.words/deletion (language/part2) <==

What exceptional words turn into other words by deletion of letters?

==> english/spelling/operations.on.words/insertion.and.deletion (language/part2) <==

What exceptional words turn into other words by both insertion and

==> english/spelling/operations.on.words/insertion (language/part2) <==

What exceptional words turn into other words by insertion of letters?

==> english/spelling/operations.on.words/movement (language/part2) <==

What exceptional words turn into other words by movement of letters?

==> english/spelling/operations.on.words/substitution (language/part2) <==

What exceptional words turn into other words by substitution of letters?

==> english/spelling/operations.on.words/transposition (language/part3) <==

What exceptional words turn into other words by transposition of letters?

==> english/spelling/operations.on.words/words.within.words (language/part3) <==

What exceptional words contain other words?

==> english/spelling/palindromes (language/part3) <==

What are some long palindromes?

==> english/spelling/sets.of.words/ladder (language/part3) <==

Find the shortest word ladders stretching between the following pairs:

==> english/spelling/sets.of.words/nots.and.crosses (language/part3) <==

What is the most number of letters that can be fit into a three by three grid

==> english/spelling/sets.of.words/perfect.ladder (language/part3) <==

A "perfect" ladder comprises five-letter words where every letter is

==> english/spelling/sets.of.words/squares (language/part3) <==

What are some exceptional word squares (square crosswords with no blanks)?

==> english/spelling/sets.of.words/variogram (language/part3) <==

What is the largest known variogram (word square where repeated letters count

==> english/spelling/sets.of.words/word.torture (language/part3) <==

What is the longest word all of whose contiguous subsequences are words?

==> english/spelling/single.words (language/part3) <==

What words have exceptional lengths, patterns, etc.?

==> english/spoonerisms (language/part3) <==

List some exceptional spoonerisms.

==> english/synonyms/ambiguous (language/part3) <==

What word in the English language is the most ambiguous?

==> english/synonyms/antonym (language/part3) <==

What words, when a single letter is added, reverse their meanings?

==> english/synonyms/contradictory.proverbs (language/part3) <==

What are some proverbs that contradict one another?

==> english/synonyms/contranym (language/part3) <==

What words are their own antonym?

==> english/synonyms/double.synonyms (language/part3) <==

What words have two different synonymous meanings?

==> finnish/finnish.plural (language/part3) <==

What Finnish word is the anagram of its plural?

==> finnish/finnish.record (language/part4) <==

What are some Finnish words with unusual properties?

==> french/french.palindromes (language/part4) <==

List some French palindromes.

==> french/french.record (language/part4) <==

What are some French words with unusual properties?

==> german/german.palindromes (language/part4) <==

List some German palindromes.

==> german/german.record (language/part4) <==

What are some German words with unusual properties?

==> italian/italian.record (language/part5) <==

What are some Italian words with unusual properties?

==> multi.palindromes (language/part5) <==

List some multi-lingual palindromes.

==> norwegian/norwegian.record (language/part5) <==

What are some Norwegian words with unusual properties?

==> repeated.word (language/part5) <==

In any language, construct a sentence by repeating one word four times.

==> swedish/swedish.record (language/part5) <==

What are some Swedish words with unusual properties?

==> synonymous.reversals (language/part5) <==

What words are synonymous with their reversals in other langauges?

==> vowels.repeated (language/part5) <==

In any language, what word contains the same vowel repeated four times in a row?

==> 29 (logic/part1) <==

Three people check into a hotel. They pay $30 to the manager and go

==> ages (logic/part1) <==

1) Ten years from now Tim will be twice as old as Jane was when Mary was

==> attribute (logic/part1) <==

All the items in the first list share a particular attribute. The second

==> bookworm (logic/part1) <==

A bookworm eats from the first page of an encyclopedia to the last

==> boxes (logic/part1) <==

Which Box Contains the Gold?

==> camel (logic/part1) <==

An Arab sheikh tells his two sons to race their camels to a distant

==> centrifuge (logic/part1) <==

You are a biochemist, working with a 12-slot centrifuge. This is a gadget

==> chain (logic/part1) <==

What is the least number of links you can cut in a chain of 21 links to be able

==> children (logic/part1) <==

A man walks into a bar, orders a drink, and starts chatting with the

==> condoms (logic/part1) <==

How can a man have mutually safe sex with three women with only two condoms?

==> dell (logic/part1) <==

How can I solve logic puzzles (e.g., as published by Dell) automatically?

==> elimination (logic/part1) <==

97 baseball teams participate in an annual state tournament.

==> flip (logic/part1) <==

How can a toss be called over the phone (without requiring trust)?

==> flowers (logic/part1) <==

How many flowers do I have if all of them are roses except two, all of

==> friends (logic/part1) <==

Any group of 6 or more contains either 3 mutual friends or 3 mutual strangers.

==> hofstadter (logic/part1) <==

In first-order logic, find a predicate P(x) which means "x is a power of 10."

==> hundred (logic/part1) <==

A sheet of paper has statements numbered from 1 to 100. Statement n says

==> inverter (logic/part1) <==

Can a digital logic circuit with two inverters invert N independent inputs?

==> josephine (logic/part1) <==

The recent expedition to the lost city of Atlantis discovered scrolls

==> locks.and.boxes (logic/part1) <==

You want to send a valuable object to a friend. You have a box which

==> min.max (logic/part1) <==

In a rectangular array of people, which will be taller, the tallest of the

==> mixing (logic/part1) <==

Start with a half cup of tea and a half cup of coffee. Take one tablespoon

==> monty.52 (logic/part1) <==

Monty and Waldo play a game with N closed boxes. Monty hides a

==> number (logic/part1) <==

Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce

==> riddle (logic/part2) <==

Who makes it, has no need of it. Who buys it, has no use for it. Who

==> river.crossing (logic/part2) <==

Three humans, one big monkey and two small monkeys are to cross a river:

==> ropes (logic/part2) <==

Two fifty foot ropes are suspended from a forty foot ceiling, about

==> same.street (logic/part2) <==

Sally and Sue have a strong desire to date Sam. They all live on the

==> self.ref (logic/part2) <==

Find a number ABCDEFGHIJ such that A is the count of how many 0's are in the

==> situation.puzzles (logic/part3) <==

Jed's List of Situation Puzzles

==> smullyan/black.hat (logic/part4) <==

Three logicians, A, B, and C, are wearing hats, which they know are either

==> smullyan/fork.three.men (logic/part4) <==

Three men stand at a fork in the road. One fork leads to Someplaceorother;

==> smullyan/fork.two.men (logic/part4) <==

Two men stand at a fork in the road. One fork leads to Someplaceorother; the

==> smullyan/integers (logic/part4) <==

Two logicians place cards on their foreheads so that what is written on the

==> smullyan/painted.heads (logic/part4) <==

While three logicians were sleeping under a tree, a malicious child painted

==> smullyan/priest (logic/part5) <==

In a small town there are N married couples in which one of the pair

==> smullyan/stamps (logic/part5) <==

The moderator takes a set of 8 stamps, 4 red and 4 green, known to the

==> supertasks (logic/part5) <==

You have an empty urn, and an infinite number of labeled balls. Each

==> timezone (logic/part5) <==

Two people are talking long distance on the phone; one is in an East-

==> unexpected (logic/part5) <==

Swedish civil defense authorities announced that a civil defense drill would

==> verger (logic/part5) <==

A very bright and sunny Day

==> weighing/balance (logic/part5) <==

You are given 12 identical-looking coins, one of which is counterfeit

==> weighing/box (logic/part5) <==

You have ten boxes; each contains nine balls. The balls in one box

==> weighing/find.median (logic/part5) <==

What is the least number of pairwise comparisons needed to find the median of

==> weighing/gummy.bears (logic/part5) <==

Real gummy drop bears have a mass of 10 grams, while imitation gummy

==> weighing/optimal.weights (logic/part5) <==

What is the smallest set of weights that allow you to weigh on a

==> weighing/weighings (logic/part5) <==

Some of the supervisors of Scandalvania's n mints are producing bogus coins.

==> zoo (logic/part5) <==

I took some nephews and nieces to the Zoo, and we halted at a cage marked

==> balloon (physics) <==

A helium-filled balloon is tied to the floor of a car that makes a

==> brick (physics) <==

What is the maximum overhang you can create with an infinite supply of bricks?

==> bubbles (physics) <==

In a universe with the same physical laws, but which is mostly water

==> cannonball (physics) <==

A person in a boat drops a cannonball overboard; does the water level change?

==> magnets (physics) <==

You have two bars of iron. One is magnetized along its length, the

==> milk.and.coffee (physics) <==

You are just served a hot cup of coffee and want it to be as hot as

==> mirror (physics) <==

Why does a mirror appear to invert the left-right directions, but not up-down?

==> monkey (physics) <==

Hanging over a pulley there is a rope, with a weight at one end.

==> pole.in.barn (physics) <==

Accelerate a pole of length l to a constant speed of 90% of the speed of

==> resistors (physics) <==

What is the resistance between various pairs of vertices on a lattice

==> sail (physics) <==

A sailor is in a sailboat on a river. The current is 3 knots with respect

==> shoot.sun (physics) <==

If you are standing at the equator at sunrise, where must you point a laser

==> skid (physics) <==

What is the fastest way to make a 90 degree turn on a slippery road?

==> spheres (physics) <==

Two spheres are the same size and weight, but one is hollow. They are

==> wind (physics) <==

Is a round-trip by airplane longer or shorter if there is wind blowing?

==> pickover.01 (pickover/part1) <==

Title: Cliff Puzzle 1: Can you beat the numbers game?

==> pickover.02 (pickover/part1) <==

Title: Cliff Puzzle 2: Grid of the Gods

==> pickover.03 (pickover/part1) <==

Title: Cliff Puzzle 3: Too many 3's

==> pickover.04 (pickover/part1) <==

Title: Cliff Puzzle 4: Time in a Bottle

==> pickover.05 (pickover/part1) <==

Title: Cliff Puzzle 5: Mystery Sequence

==> pickover.06 (pickover/part1) <==

Title: Cliff Puzzle 6: Star Chambers

==> pickover.07 (pickover/part2) <==

Title: Cliff Puzzle 7: 3x3 Recursion

==> pickover.08 (pickover/part2) <==

Title: Cliff Puzzle 8: Squares and Squares and Squares ....

==> pickover.09 (pickover/part2) <==

Title: Cliff Puzzle 9: 3-Atoms and Growth

==> pickover.10 (pickover/part2) <==

Title: Cliff Puzzle 10: The Ark Series

==> pickover.11 (pickover/part2) <==

Title: Cliff Puzzle 11: The Leviathan Number

==> pickover.12 (pickover/part3) <==

Title: Cliff Puzzle 12: Slides in Hell

==> pickover.13 (pickover/part3) <==

Title: Cliff Puzzle 13: Ladders to Heaven

==> pickover.14 (pickover/part3) <==

Title: Cliff Puzzle 14: Geography Genuflection

==> pickover.15 (pickover/part3) <==

Title: Cliff Puzzle 15: Cherries in Wine Glasses

==> pickover.16 (pickover/part3) <==

Title: Cliff Puzzle 16: Undulating Squares

==> pickover.17 (pickover/part3) <==

Title: Cliff Puzzle 17: Weird Recursive Sequence

==> pickover.18 (pickover/part3) <==

Title: Cliff Puzzle 18: Difficult Nested Roots

==> amoeba (probability) <==

A jar begins with one amoeba. Every minute, every amoeba

==> apriori (probability) <==

An urn contains one hundred white and black balls. You sample one hundred

==> bayes (probability) <==

One urn contains black marbles, and the other contains white or black

==> birthday/line (probability) <==

At a movie theater, the manager announces that they will give a free ticket

==> birthday/same.day (probability) <==

How many people must be at a party before you have even odds or better

==> cab (probability) <==

A cab was involved in a hit and run accident at night. Two cab companies,

==> coupon (probability) <==

There is a free gift in my breakfast cereal. The manufacturers say that

==> darts (probability) <==

Peter throws two darts at a dartboard, aiming for the center. The

==> derangement (probability) <==

12 men leave their hats with the hat check. If the hats are randomly

==> family (probability) <==

Suppose that it is equally likely for a pregnancy to deliver

==> flips/once.in.run (probability) <==

What are the odds that a run of one H or T (i.e., THT or HTH) will occur

==> flips/twice.in.run (probability) <==

What is the probability in n flips of a fair coin that there will be two

==> flips/unfair (probability) <==

Generate even odds from an unfair coin. For example, if you

==> flips/waiting.time (probability) <==

Compute the expected waiting time for a sequence of coin flips, or the

==> flush (probability) <==

Which set contains proportionately more flushes than the set of all

==> hospital (probability) <==

A town has two hospitals, one big and one small. Every day the big

==> icos (probability) <==

The "house" rolls two 20-sided dice and the "player" rolls one

==> intervals (probability) <==

Given two random points x and y on the interval 0..1, what is the average

==> killers.and.pacifists (probability) <==

You enter a town that has K killers and P pacifists. When a

==> leading.digit (probability) <==

What is the probability that the ratio of two random reals starts with a 1?

==> lights (probability) <==

Waldo and Basil are exactly m blocks west and n blocks north from

==> lottery (probability) <==

There n tickets in the lottery, k winners and m allowing you to pick another

==> oldest.girl (probability) <==

You meet a stranger on the street, and ask how many children he has. He

==> particle.in.box (probability) <==

A particle is bouncing randomly in a two-dimensional box. How far does it

==> pi (probability) <==

Are the digits of pi random (i.e., can you make money betting on them)?

==> random.walk (probability) <==

Waldo has lost his car keys! He's not using a very efficient search;

==> reactor (probability) <==

There is a reactor in which a reaction is to take place. This reaction

==> roulette (probability) <==

You are in a game of Russian roulette, but this time the gun (a 6

==> transitivity (probability) <==

Can you number dice so that die A beats die B beats die C beats die A?

==> icecubes (real-life) <==

You have an old-fashioned refrigerator with a small freezer compartment

==> microwave (real-life) <==

Every morning when I warm my milk for breakfast, I put one cup of milk

==> books/bloopers (references) <==

What are some errors made in puzzle books?

==> books/masquerade (references) <==

What is the solution to _Masquerade_ by Kit Williams?

==> books/maze (references) <==

What is the solution to _Maze_ by Christopher Manson?

==> books/treasure (references) <==

What is the solution to _Treasure_ by Dr. Crypton?

==> books/unnamed (references) <==

What is the solution to the unnamed book by Kit Williams?

==> faq (references) <==

Where should I look if I can't find the answer here?

==> magazines (references) <==

What magazines and journals contain puzzles?

==> organizations (references) <==

What organizations exist for puzzle lovers?

==> series.00 (series) <==

Are "complete this series" problems well defined?

==> series.01 (series) <==

M, N, B, D, P ?

==> series.02 (series) <==

H, H, L, B, B, C, N, O, F ?

==> series.03 (series) <==

W, A, J, M, M, A, J?

==> series.03a (series) <==

G, J, T, J, J, J, A, M, W, J, J, Z, M, F, J, ?

==> series.03b (series) <==

A, J, B, C, G, T, C, V, J, T, D, F, K, B, H, ?

==> series.03c (series) <==

M, A, M, D, E, L, R, H, ?

==> series.04 (series) <==

A, E, H, I, K, L, ?

==> series.05 (series) <==

A B C D E F G H?

==> series.06 (series) <==

Z, O, T, T, F, F, S, S, E, N?

==> series.06a (series) <==

F, S, T, F, F, S, ?

==> series.07 (series) <==

1, 1 1, 2 1, 1 2 1 1, ...

==> series.08a (series) <==

G, L, M, B, C, L, M, C, F, S, ?

==> series.08b (series) <==

A, V, R, R, C, C, L, L, L, E, ?

==> series.09a (series) <==

S, M, S, S, S, C, P, P, P, ?

==> series.09b (series) <==

M, S, C, P, P, P, S, S, S, ?

==> series.10 (series) <==

D, P, N, G, C, M, M, S, ?

==> series.11 (series) <==

R O Y G B ?

==> series.12 (series) <==

A, T, G, C, L, ?

==> series.13 (series) <==

M, V, E, M, J, S, ?

==> series.14 (series) <==

A, B, D, O, P, ?

==> series.14a (series) <==

A, B, D, E, G, O, P, ?

==> series.15 (series) <==

A, E, F, H, I, ?

==> series.16 (series) <==

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y?

==> series.17 (series) <==

T, P, O, F, O, F, N, T, S, F, T, F, E, N, S, N?

==> series.18 (series) <==

10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, ___ , 100, 121, 10000

==> series.19 (series) <==

0 01 01011 0101101011011 0101101011011010110101101101011011 etc.

==> series.20 (series) <==

1 2 5 16 64 312 1812 12288

==> series.21 (series) <==

5, 6, 5, 6, 5, 5, 7, 5, ?

==> series.22 (series) <==

3 1 1 0 3 7 5 5 2 ?

==> series.23 (series) <==

22 22 30 13 13 16 16 28 28 11 ?

==> series.24 (series) <==

What is the next letter in the sequence: W, I, T, N, L, I, T?

==> series.25 (series) <==

1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 ?

==> series.26 (series) <==

1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 ?

==> series.27 (series) <==

0 1 1 2 1 2 1 3 2 2 1 3 1 2 2 4 1 3 1 3 2 2 1 4 2 ?

==> series.28 (series) <==

0 2 3 4 5 5 7 6 6 7 11 7 13 9 8 8 17 8 19 9 10 13 23 9 10 ?

==> series.29 (series) <==

1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 ?

==> series.30 (series) <==

I I T Y W I M W Y B M A D

==> series.31 (series) <==

6 2 5 5 4 5 6 3 7

==> series.32 (series) <==

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1

==> series.33 (series) <==

2 12 360 75600

==> series.34 (series) <==

3 5 4 4 3 5 5 4 3

==> series.35 (series) <==

1 2 3 2 1 2 3 4 2 1 2 3 4 2 2 3

==> series.36 (series) <==

ETIANMSURWDKGO

==> series.37 (series) <==

10^3 10^9 10^27 10^2 0 4 8 3

==> area.codes (trivia) <==

When looking at a map of the distribution of telephone area codes for

==> body.parts (trivia) <==

Name ten body parts that are spelled with three letters. No slang words.

==> coincidence (trivia) <==

Name some amazing coincidences.

==> eskimo.snow (trivia) <==

How many words do the Eskimo have for snow?

==> federal.reserve (trivia) <==

What is the pattern to this list:

==> jokes.self-referential (trivia) <==

What are some self-referential jokes?

==> memory.tricks (trivia) <==

When asked to name a color, many people answer "red." What are some other

==> quotations (trivia) <==

Where can I find the source for a quotation?

Aug 18, 1993, 2:04:29 AM8/18/93

to

Archive-name: puzzles/archive/arithmetic/part2

Last-modified: 17 Aug 1993

Version: 4

Last-modified: 17 Aug 1993

Version: 4

==> arithmetic/digits/squares/three.digits.p <==

What squares consist entirely of three digits (e.g., 1, 4, and 9)?

==> arithmetic/digits/squares/three.digits.s <==

The full set of solutions up to 10**12 is

1 -> 1

2 -> 4

3 -> 9

7 -> 49

12 -> 144

21 -> 441

38 -> 1444

107 -> 11449

212 -> 44944

31488 -> 9914 94144

70107 -> 49149 91449

3 87288 -> 14 99919 94944

956 10729 -> 9 14141 14499 11441

4466 53271 -> 199 49914 44949 99441

31487 17107 -> 9914 41941 99144 49449

2 10810 79479 -> 4 44411 91199 99149 11441

If the algorithm is used in the form I presented it before, generating

the whole set P_n before starting on P_{n+1}, the store requirements

begin to become embarassing. For n>8 I switched to a depth-first

strategy, generating all the elements in P_i (i=9..12) congruent to

a particular x in P_8 for each x in turn. This means the solutions

don't come out in any particular order, of course. CPU time was 16.2

seconds (IBM 3084).

In article <1990Feb6.0...@sun.soe.clarkson.edu>, Steven

Stadnicki suggests alternate triples of digits, in particular {1,4,6}

(with many solutions) and {2,4,8} (with few). I ran my program on

these as well, up to 10**12 again:

1 -> 1

2 -> 4

4 -> 16

8 -> 64

12 -> 144

21 -> 441

38 -> 1444

108 -> 11664

119 -> 14161

121 -> 14641

129 -> 16641

204 -> 41616

408 -> 1 66464

804 -> 6 46416

2538 -> 64 41444

3408 -> 116 14464

6642 -> 441 16164

12908 -> 1666 16464

25771 -> 6641 44441

78196 -> 61146 14416

81619 -> 66616 61161

3 33858 -> 11 14611 64164

2040 00408 -> 41 61616 64641 66464

6681 64962 -> 446 44441 64444 61444

8131 18358 -> 661 16146 41166 16164

40182 85038 -> 16146 61464 66146 61444 (Steven's last soln.)

1 20068 50738 -> 1 44164 46464 46111 44644

1 26941 38988 -> 1 61141 16464 66616 64144

1 27069 43631 -> 1 61466 41644 14114 64161

4 01822 24262 -> 16 14611 14664 16614 44644

4 05784 63021 -> 16 46611 66114 66644 46441

78 51539 12392 -> 6164 66666 14446 44111 61664

and

2 -> 4

22 -> 484

168 -> 28224

478 -> 2 28484

2878 -> 82 82884 (Steven's last soln.)

2109 12978 -> 44 48428 42888 28484

(so the answer to Steven's "Are there any more at all?" is "Yes".)

The CPU times were 42.9 seconds for {1,4,6}, 18.7 for {2,4,8}. This

corresponds to an interesting point: the abundance of solutions for

{1,4,6} is associated with abnormally large sets P_n (|P_8| = 16088

for {1,4,6} compared to |P_8| = 5904 for {1,4,9}) but the deficiency

of solutions for {2,4,8} is *not* associated with small P_n's (|P_8|

= 6816 for {2,4,8}). Can anyone wave a hand convincingly to explain

why the solutions for {2,4,8} are so sparse?

I suspect we are now getting to the point where an improved algorithm

is called for. The time to determine all the n-digit solutions (i.e.

2n-digit squares) using this last-significant-digit-first is essentially

constant * 3**n. Dean Hickerson in <90036.1...@PSUVM.BITNET>, and

Ilan Vardi in <1990Feb5.2...@Neon.Stanford.EDU>, suggest using

a most-significant-digit-first strategy, based on the fact that the

first n digits of the square determine the (integral) square root; this

also has a running time constant * 3**n. Can one attack both ends at

once and do better?

Chris Thompson

JANET: ce...@uk.ac.cam.phx

Internet: cet1%phx.ca...@nsfnet-relay.ac.uk

Hey guys, what about

648070211589107021 ^ 2 = 419994999149149944149149944191494441

This was found by David Applegate and myself (about 5 minutes on a DEC 3100,

program in C).

This is the largest square less than 10^42 with the 149-property; checking

took a bit more than an hour of CPU time.

As somebody suggested, we used a combined most-significant/least-significant

digits attack. First we make a table of p-digit prefixes (most significant

p digits) that could begin a root whose square has the 149 property in its

first p digits. We organize this table into buckets by the least

significant q digits of the prefixes. Then we enumerate the s digit

suffixes whose squares have the 149 property in their last s digits. For

each such suffix, we look in the table for those prefixes whose last q

digits match the first q of the suffix. For each match, we consider the p +

s - q digit number formed by overlapping the prefix and the suffix by q

digits. The squares of these overlap numbers must contain all the squares

with the 149 property.

The time expended is O(3^p) to generate the prefix table, O(3^s) to

enumerate the suffixes, and O(3^(p+s) / 10^q) to check the overlaps (being

very rough and ignoring the polynomial factors) By judiciously chosing p, q,

and s, we can fix things so that each bucket of the table has around O(1)

entries: set q = p log10(3). Setting p = s, we end up looking for squares

whose roots have n = 2 - log10(3) digits, with an algorithm that takes time

O( 3 ^ [n / (2 - log10(3)]) ), roughly time O(3^[.66n]). Compared to the

O(3^n) performance of either single-ended algorithm, this lets us check 50%

more digits in the same amount of time (ignoring polynomial factors). Of

course, the space cost of the combined-ends method is high.

-- Guy and Dave

--

Guy Jacobson School of Computer Science

Carnegie Mellon arpanet : g...@cs.cmu.edu

Pittsburgh, PA 15213 csnet : Guy.Jacobson%a.cs.cmu.edu@csnet-relay

(412) 268-3056 uucp : ...!{seismo, ucbvax, harvard}!cs.cmu.edu!guy

Here is an algorithm which takes O(sqrt(n)log(n)) steps to find all perfect

squares < n whose only digits are 1, 4 and 9.

This doesn't sound too great *but* it doesn't use a lot of memory and only

requires addition and <. Also, the actual run time will depend on where the

first non-{1,4,9} digit appears in each square.

set n = 1

set odd = 1

while(n < MAXVAL)

{

if(all digits of n are in {1,4,9})

{

print n

}

add 2 to odd

add odd to n

}

This works because (X+1)^2 - x^2 = 2x+1.

That is, if you start with 0 and add successive odd

numbers to it you get 0+1=1, 1+3=4, 4+5=9, 9+7=16 etc.

I've started the algorithm at 1 for convenience.

The "O" value comes from looking at at most all digits

(log(n)) of all perfect squares < n (sqrt(n) of them)

at most a constant number of times.

I didn't save the articles with algorithms claiming to be

O(3^log(n)) so I don't know if their calculations needed

to (or did) account for multiplication or sqrt() of large

numbers. O(3^log(n)) sounds reasonable so I'm going to

assume they did unless I hear otherwise.

Any comments? Please email if you just want to refresh my memory

on the other algorithms.

Andrew Charles

ac...@ihuxy.ATT.COMM

==> arithmetic/digits/squares/twin.p <==

Let a twin be a number formed by writing the same number twice,

for instance, 81708170 or 132132. What is the smallest square twin?

==> arithmetic/digits/squares/twin.s <==

1322314049613223140496 = 36363636364 ^ 2.

The key to solving this puzzle is looking at the basic form of these

"twin" numbers, which is some number k = 1 + 10^n multiplied by some number

10^(n-1) <= a < 10^n. If ak is a perfect square, k must have some

repeated factor, since a<k. Searching the possible values of k for one

with a repeated factor eventually turns up the number 1 + 10^11 = 11^2

* 826446281. So, we set a=826446281 and ak = 9090909091^2 =

82644628100826446281, but this needs leading zeros to fit the pattern.

So, we multiply by a suitable small square (in this case 16) to get the

above answer.

==> arithmetic/digits/sum.of.digits.p <==

Find sod ( sod ( sod (4444 ^ 4444 ) ) ).

==> arithmetic/digits/sum.of.digits.s <==

let X = 4444^4444

sod(X) <= 9 * (# of digits) < 145900

sod(sod(X)) <= sod(99999) = 45

sod(sod(sod(X))) <= sod(39) = 12

but sod(sod(sod(X))) = 7 (mod 9)

thus sod(sod(sod(X))) = 7

==> arithmetic/digits/zeros/million.p <==

How many zeros occur in the numbers from 1 to 1,000,000?

==> arithmetic/digits/zeros/million.s <==

In the numbers from 10^(n-1) through 10^n - 1, there are 9 * 10^(n-1)

numbers of n digits each, so 9(n-1)10^(n-1) non-leading digits, of

which one tenth, or 9(n-1)10^(n-2), are zeroes. When we change the

range to 10^(n-1) + 1 through 10^n, we remove 10^(n-1) and put in

10^n, gaining one zero, so

p(n) = p(n-1) + 9(n-1)10^(n-2) + 1 with p(1)=1.

Solving the recurrence yields the closed form

p(n) = n(10^(n-1)+1) - (10^n-1)/9.

For n=6, there are 488,895 zeroes, 600,001 ones, and 600,000 of all other

digits.

==> arithmetic/digits/zeros/trailing.p <==

How many trailing zeros are in the decimal expansion of n!?

==> arithmetic/digits/zeros/trailing.s <==

The general answer to the question

"what power of p divides x!" where p is prime

is (x-d)/(p-1) where d is the sum of the digits of (x written in base p).

So where p=5, 10 is written as 20 and is divisible by 5^2 (2 = (10-2)/4);

x to base 10: 100 1000 10000 100000 1000000

x to base 5: 400 13000 310000 11200000 224000000

d : 4 4 4 4 8

trailing 0s in x! 24 249 2499 24999 249998

==> arithmetic/magic.squares.p <==

Are there large squares, containing only consecutive integers, all of whose

rows, columns and diagonals have the same sum? How about cubes?

==> arithmetic/magic.squares.s <==

These are called magic squares. A magic square of order n (integers

from 1 to n*n) has only one possible sum: (n*n+1)*n/2.

Odd and even order squares must be constructed by different approaches.

For odd orders, the most common algorithm is a recursive scheme

devised by de la Loubere about 300 years ago. For even orders, one

procedure is the Devedec algorithm, which treats even orders not

divisible by 4 slightly differently from those which are divisible by

4 (doubly even).

For squares with odd-length sides, the following algorithm builds a magic

square:

Put 1 in the middle box in the upper row. From then on, if it's

possible to put the next number one box diagonally up and to the right

(wrapping around if the edge of the grid is reached), do so, otherwise,

put it directly below the last one.

17 24 1 8 15

23 5 7 14 16

4 6 13 20 22

10 12 19 21 3

11 18 25 2 9

...or even

47 58 69 80 1 12 23 34 45

57 68 79 9 11 22 33 44 46

67 78 8 10 21 32 43 54 56

77 7 18 20 31 42 53 55 66

6 17 19 30 41 52 63 65 76

16 27 29 40 51 62 64 75 5

26 28 39 50 61 72 74 4 15

36 38 49 60 71 73 3 14 25

37 48 59 70 81 2 13 24 35

See archive entry knight.tour for magic squares that are knight's tours.

To get a 4x4 square, write the numbers in order across each row, filling

the square...

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

then use the following pattern as a mask:

. X X .

X . . X

X . . X

. X X .

Everywhere there is an X, complement the number (subtract it from

n*n+1). For the 4x4 you get:

1 15 14 4

12 6 7 9

8 10 11 5

13 3 2 16

For n even (n>4):

Make an initial magic square by writing an n/2 magic square four times

(the same one each time). Now, although this square adds up right we

have the numbers 1 to n*n/4 written four times each. To fix this,

simply add to it n*n/4 times one of the following magic squares:

if n/2 is odd (example: n/2=7),

3 3 3 0 0 0 0 2 2 2 2 2 1 1 (there are int(n/4) 3s, int(n/4-1) 1s on each

3 3 3 0 0 0 0 2 2 2 2 2 1 1 row)

3 3 3 0 0 0 0 2 2 2 2 2 1 1

0 3 3 3 0 0 0 2 2 2 2 2 1 1 (this is row int(n/4)+1. It starts with just

3 3 3 0 0 0 0 2 2 2 2 2 1 1 the one 0)

3 3 3 0 0 0 0 2 2 2 2 2 1 1

3 3 3 0 0 0 0 2 2 2 2 2 1 1

0 0 0 3 3 3 3 1 1 1 1 1 2 2 (the lower half is the same as the upper half

0 0 0 3 3 3 3 1 1 1 1 1 2 2 with 3<->0 and 1<->2 swapped. This guarantees

0 0 0 3 3 3 3 1 1 1 1 1 2 2 that each number 1-n*n will appear in the

3 0 0 0 3 3 3 1 1 1 1 1 2 2 completed square)

0 0 0 3 3 3 3 1 1 1 1 1 2 2

0 0 0 3 3 3 3 1 1 1 1 1 2 2

0 0 0 3 3 3 3 1 1 1 1 1 2 2

if n/2 is even (example: n/2=4),

0 0 3 3 2 2 1 1 (there are n/4 of each number on each row)

0 0 3 3 2 2 1 1

0 0 3 3 2 2 1 1

0 0 3 3 2 2 1 1

3 3 0 0 1 1 2 2

3 3 0 0 1 1 2 2

3 3 0 0 1 1 2 2

3 3 0 0 1 1 2 2

References:

"Magic Squares and Cubes"

W.S. Andrews

The Open Court Publishing Co.

Chicago, 1908

"Mathematical Recreations"

M. Kraitchik

Dover

New York, 1953

==> arithmetic/pell.p <==

Find integer solutions to x^2 - 92y^2 = 1.

==> arithmetic/pell.s <==

x=1 y=0

x=1151 y=120

x=2649601 y=276240

etc.

Each successive solution is about 2300 times the previous

solution; they are every 8th partial fraction (x=numerator,

y=denominator) of the continued fraction for sqrt(92) =

[9, 1,1,2,4,2,1,1,18, 1,1,2,4,2,1,1,18, 1,1,2,4,2,1,1,18, ...]

Once you have the smallest positive solution (x1,y1) you

don't need to "search" for the rest. You can obtain the nth positive

solution (xn,yn) by the formula

(x1 + y1 sqrt(92))^n = xn + yn sqrt(92).

See Niven & Zuckerman's An Introduction to the Theory of Numbers.

Look in the index under Pell's equation.

==> arithmetic/subset.p <==

Prove that all sets of n integers contain a subset whose sum is divisible by n.

==> arithmetic/subset.s <==

Consider the set of remainders of the partial sums a(1) + ... + a(i).

Since there are n such sums, either one has remainder zero (and we're

thru) or 2 coincide, say the i'th and j'th. In this case, a(i+1) +

... + a(j) is divisible by n. (note this is a stronger result since

the subsequence constructed is of *adjacent* terms.) Consider a(1)

(mod n), a(1)+a(2) (mod n), ..., a(1)+...+a(n) (mod n). Either at

some point we have a(1)+...+a(m) = 0 (mod n) or else by the pigeonhole

principle some value (mod n) will have been duplicated. We win either

way.

==> arithmetic/sum.of.cubes.p <==

Find two fractions whose cubes total 6.

==> arithmetic/sum.of.cubes.s <==

Restated:

Find X, Y, minimum Z (all positive integers) where

(X/Z)^3 + (Y/Z)^3 = 6

Again, a generalized solution would be nice.

You are asking for the smallest z s.t. x^3 + y^3 = 6*z^3 and x,y,z in Z+.

In general, questions like these are extremely difficult; if you're

interested take a look at books covering Diophantine equations

(especially Baker's work on effective methods of computing solutions).

Dudeney mentions this problem in connection with #20 in _The Canterbury

Puzzles_; the smallest answer is (17/21)^3 + (37/21)^3 = 6.

For the interest of the readers of this group I'll quote:

"Given a known case for the expression of a number as the sum or

difference of two cubes, we can, by formula, derive from it an infinite

number of other cases alternately positive and negative. Thus Fermat,

starting from the known case 1^3 + 2^3 = 9 (which we will call a

fundamental case), first obtained a negative solution in bigger

figures, and from this his positive solution in bigger figures still.

But there is an infinite number of fundamentals, and I found by trial

a negative fundamental solution in smaller figures than his derived

negative solution, from which I obtained the result shown above. That

is the simple explanation."

In the above paragraph Dudeney is explaining how he derived (*by hand*)

that (415280564497/348671682660)^3 + (676702467503/348671682660)^3 = 9.

He continues:

"We can say of any number up to 100 whether it is possible or not to

express it as the sum of two cubes, except 66. Students should read

the Introduction to Lucas's _Theorie des Nombres_, p. xxx."

"Some years ago I published a solution for the case 6 = (17/21)^3 +

(37/21)^3, of which Legendre gave at some length a 'proof' of

impossibility; but I have since found that Lucas anticipated me in

a communication to Sylvester."

==> arithmetic/sums.of.powers.p <==

Partition 1,2,3,...,16 into two equal sets, such that the sums of the

numbers in each set are equal, as are the sums of their squares and cubes.

==> arithmetic/sums.of.powers.s <==

The solution is A = {1,4,6,7,10,11,13,16}

B = {2,3,5,8,9,12,14,15}

Let X+k be a set formed by adding k to all elements of X.

Then A+k and B+k have the property of satisfying i,ii and iii.

That means, any 16 numbers in A.P can be partioned in such a way to

satisfy i,ii and iii.

How do we arrive at the above solution without using a computer?

By the preceding discussion,

A1 = A-1 = {0,3,5,6,9,10,12,15}

B1 = B-1 = {1,2,4,7,8,11,13,14}

have the property of satisfying i,ii and iii.

Notice that all numbers of A1 have even number of 1's in binary and

all numbers of B1 have odd number of 1's in binary. Essentially the

above partition is a partition based on parity.

Observation:

Partition of (n+1) bit numbers based on parity into two

groups A and B (each consisting of 2^n elements) satisfies

sum of kth powers of elements of A = sum of kth powers of elements of B

for k=1,2,...,n. (The above puzzle is a special case n=3).

The above observation also holds for any radix. In radix r we will have

r groups.

Infact,

Any r^(n+1) terms in A.P can be partitioned into r groups (each of

r^n elements) such that sum of kth powers of all r groups is same (k=1,2,...,n)

Finding such groups with minimal number of elements (less than r^n) appears to

be more difficult!

ALL THIS APPEARS TO BE INTERESTING. IS IT A CONSEQUENCE OF A SIMPLE THEOREM OF

NUMBER THEORY? HOW DO I PROVE THIS?

Thanks in advance for any clues,

-- ram...@svl.cdc.com (Mr. Ramana (Indian analyst))

==> arithmetic/tests.for.divisibility/eleven.p <==

What is the test to see if a number is divisible by eleven?

==> arithmetic/tests.for.divisibility/eleven.s <==

If the alternating sum of the digits is divisible by eleven, so is the number.

For example, 1639 leads to 9 - 3 + 6 - 1 = 11, so 1639 is divisible by 11.

Proof:

Every integer n can be expressed as

n = a1*(10^k) + a2*(10^k-1)+ .....+ a_k+1

where a1, a2, a3, ...a_k+1 are integers between 0 and 9.

10 is congruent to -1 mod(11).

Thus if (-1^k)*a1 + (-1^k-1)*a2 + ...+ (a_k+1) is congruent to 0mod(11) then

n is divisible by 11.

==> arithmetic/tests.for.divisibility/nine.p <==

What is the test to see if a number is divisible by nine?

==> arithmetic/tests.for.divisibility/nine.s <==

If the sum of the digits is divisible by nine, so is the number.

Proof:

Every integer n can be expressed as

n = a1*(10^k) + a2*(10^k-1)+ .....+ a_k+1

where a1, a2, a3, ...a_k+1 are integers between 0 and 9.

Note that 10 is congruent to 1 (mod 9). Thus 10^k is congruent to 1 (mod 9) for

every k >= 0.

Thus n is congruent to (a1+a2+a3+....+a_k+1) mod(9).

Hence (a1+a2+...+a_k+1) is divisible by 9 iff n is divisible by 9.

==> arithmetic/tests.for.divisibility/seven.p <==

What is the test to see if a number is divisible by seven?

==> arithmetic/tests.for.divisibility/seven.s <==

Take the last digit (n mod 10) and double it.

Take the rest of the digits (n div 10) and subtract the doubled last

digit from it.

The resulting number is divisible by 7 iff the original number

is divisible by 7.

Example: Take 53445

Subtract (53445 mod 10) * 2 from (53445 div 10)

- 5 * 2 + 5344

= 5334

533 - 2 * 4 = 525

52 - 5 * 2 = 42 which is divisible by 7

so 53445 is divisible by 7.

==> arithmetic/tests.for.divisibility/three.p <==

What is the test to see if a number is divisible by three?

==> arithmetic/tests.for.divisibility/three.s <==

A number is divisible by three iff the sum of its digits is divisible by three.

First, prove 10^N = 1 mod 3 for all integers N >= 0.

1 = 1 mod 3. 10 = 1 mod 3. 10^N = 10^(N-1) * 10 = 10^(N-1) mod 3.

QED by induction.

Now let D[0] be the units digit of N, D[1] the tens digit, etc.

Now N = Summation From k=0 to k=inf of D[k]*10^k.

Therefore N mod 3 = Summation from k=0 to k=inf of D[k] mod 3. QED

Aug 18, 1993, 2:04:32 AM8/18/93

to

Archive-name: puzzles/archive/combinatorics

Last-modified: 17 Aug 1993

Version: 4

Last-modified: 17 Aug 1993

Version: 4

==> combinatorics/alphabet.blocks.p <==

What is the minimum number of dice painted with one letter on all six sides

such that all permutations without repetitions of n letters can be formed

by placing n dice together in a line?

==> combinatorics/alphabet.blocks.s <==

n= 2 3 4 5 6

(8,4) (9,7) (9,3) (10,7) (11,7)

aijklm abcde? acdefg abcde? abkmuz

bijklm fghij? bhijkl fghij? bcpwy?

cnopqr klmno? cmnopq klmno? cdlnvz

dnopqr pqrst? dhnrvy pqrst? deqxu?

estuvw uvwxy? eiosvw uvwxy? efmowz

fstuvw afkpu? fjptwx afkpu? fgryv?

gxyz?? bglqv? gkquxy bglqv? ghnkx?

hxyz?? chmrwz lmrstu chmrwz hisuw?

dinsxz zab??? dinsxz ijoly?

ejotyz jatvx?

pqrstz

I think I can prove that there is no solution with 11 dice with 9

don't cares or with 10 dice, but I haven't checked all the details, so

I might have made a mistake. In any case, that leaves open the case

of 11 dice with 8 don't cares; my guess is that it is not possible.

-- John Rickard (jric...@eoe.co.uk)

==> combinatorics/coinage/combinations.p <==

Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many

ways are there to make change for a dollar?

==> combinatorics/coinage/combinations.s <==

292. The table is shown below:

Amount 00 05 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

Coins

.01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

.05 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

.10 1 2 4 6 9 12 16 20 25 30 36 42 49 56 64 72 81 90 100 110 121

.25 1 2 4 6 9 13 18 24 31 39 49 60 73 87 103 121 141 163 187 214 242

.50 1 2 4 6 9 13 18 24 31 39 49 62 77 93 112 134 159 187 218 253 292

The meaning of each entry is as follows:

If you wish to make change for 50 cents using only pennies, nickels and dimes,

go to the .10 row and the 50 column to obtain 36 ways to do this.

To calculate each entry, you start with the pennies. There is exactly one

way to make change for every amount. Then calculate the .05 row by adding

the number of ways to make change for the amount using pennies plus the number

of ways to make change for five cents less using nickels and pennies. This

continues on for all denominations of coins.

An example, to get change for 75 cents using all coins up to a .50, add the

number of ways to make change using only .25 and down (121) and the number of

ways to make change for 25 cents using coins up to .50 (13). This yields the

answer of 134.

==> combinatorics/coinage/dimes.p <==

"Dad wants one-cent, two-cent, three-cent, five-cent, and ten-cent

stamps. He said to get four each of two sorts and three each of the

others, but I've forgotten which. He gave me exactly enough to buy

them; just these dimes." How many stamps of each type does Dad want?

A dime is worth ten cents. -- J.A.H. Hunter

==> combinatorics/coinage/dimes.s <==

The easy way to solve this is to sell her three each, for

3x(1+2+3+5+10) = 63 cents. Two more stamps must be bought, and they

must make seven cents (since 17 is too much), so the fourth stamps are

a two and a five.

==> combinatorics/coinage/impossible.p <==

What is the smallest number of coins that you can't make a dollar with?

I.e., for what N does there not exist a set of N coins adding up to a dollar?

It is possible to make a dollar with 1 current U.S. coin (a Susan B. Anthony),

2 coins (2 fifty cent pieces), 3 coins (2 quarters and a fifty cent piece),

etc. It is not possible to make exactly a dollar with 101 coins.

==> combinatorics/coinage/impossible.s <==

The answer is 77:

a) 5c = 1 or 5;

b) 10c = 1 or 2 a's (1,2,6,10)

c) 25c = 1 or 2 b's + 1 a

d) 50c = 1 or 2 c's

e) $1 = 1 or 2 d's

total penny nickel dime quarter half

5 1 2 1 1

6 3 1 1 1

7 5 1 1

8 4 3 1

9 6 2 1

10 8 1 1

11 10 1

12 7 4 1

13 9 3 1

14 11 2 1

15 13 1 1

16 15 1

17 14 3

18 16 2

19 18 1

20 20

21 5 13 3

22 5 15 2

23 5 17 1

24 5 19

25 10 12 3

26 10 14 2

27 10 16 1

28 10 18

29 15 11 3

30 15 13 2

31 15 15 1

32 15 17

33 20 10 3

34 20 12 2

35 20 14 1

36 20 16

37 25 9 3

38 25 11 2

39 25 13 1

40 25 15

41 30 8 3

42 30 10 2

43 30 12 1

44 30 14

45 35 7 3

46 35 9 2

47 35 11 1

48 35 13

49 40 6 3

50 40 8 2

51 40 10 1

52 40 12

53 45 5 3

54 45 7 2

55 45 9 1

56 45 11

57 50 4 3

58 50 6 2

59 50 8 1

60 50 10

61 55 3 3

62 55 5 2

63 55 7 1

64 55 9

65 60 2 3

66 60 4 2

67 60 6 1

68 60 8

69 65 1 3

70 65 3 2

71 65 5 1

72 65 7

73 70 3

74 70 2 2

75 70 4 1

76 70 6

77 can't be done

78 75 1 2

79 75 3 1

80 75 5

81 can't be done

82 80 2

83 80 2 1

84 80 4

85 can't be done

86 can't be done

87 85 1 1

88 85 3

89 can't be done

90 can't be done

91 90 1

92 90 2

93-95 can't be done

96 95 1

97-99 can't be done

100 100

==> combinatorics/color.p <==

An urn contains n balls of different colors. Randomly select a pair, repaint

the first to match the second, and replace the pair in the urn. What is the

expected time until the balls are all the same color?

==> combinatorics/color.s <==

(n-1)^2.

If the color classes have sizes k1, k2, ..., km, then the expected number of

steps from here is (dropping the subscript on k):

2 k(k-1) (j-1) (k-j)

(n-1) - SUM ( ------ + SUM --------------- )

classes, 2 1<j<k (n-j)

class.size=k

The verification goes roughly as follows. Defining phi(k) as (k(k-1)/2 +

sum[j]...), we first show that phi(k+1) + phi(k-1) - 2*phi(k) = (n-1)/(n-k)

except when k=n; the k(k-1)/2 contributes 1, the term j=k contributes

(j-1)/(n-j)=(k-1)/(n-k), and the other summands j<k contribute nothing.

Then we say that the expected change in phi(k) on a given color class is

k*(n-k)/(n*(n-1)) times (phi(k+1) + phi(k-1) - 2*phi(k)), since with

probability k*(n-k)/(n*(n-1)) the class goes to size k+1 and with the same

probability it goes to size k-1. This expected change comes out to k/n.

Summing over the color classes (and remembering the minus sign), the

expected change in the "cost from here" on one step is -1, except when we're

already monochromatic, where the handy exception k=n kicks in.

One can rewrite the contribution from k as

(n-1) SUM (k-j)/(n-j)

0<j<k

which incorporates both the k(k-1)/2 and the previous sum over j.

That makes the proof a little cleaner.

==> combinatorics/full.p <==

Consider a string that contains all substrings of length n. For example,

for binary strings with n=2, a shortest string is 00110 -- it contains 00,

01, 10 and 11 as substrings. Find the shortest such strings for all n.

==> combinatorics/full.s <==

Knuth, Volume 2 Seminumerical Algorithms, section 3.2.2 discusses this problem.

He cites the following results:

Shortest length: m^n + n - 1, where m = number of symbols in the language.

Algorithms:

[Exercise 7, W. Mantel, 1897]

The binary sequence is the LSB of X computed by the MIX program:

LDA X

JANZ *+2

LDA A

ADD X

JNOV *+3

JAZ *+2

XOR A

STA X

[Exercise 10, M. H. Martin, 1934]

Set x[1] = x[2] = ... = x[n] = 0. Set x[i+1] = largest value < n such that

substring of n digits ending at x[i+1] does not occur earlier in string.

Terminate when this is not possible.

If we instead consider the strings as circular, we have a well known

problem whose solution is given by any hamiltonian cycle in the de

Bruijn (or Good) graph of dimension K. (Or equivalently an eulerian

circuit in the de Bruijn graph of dimension K-1) As a string of length

2^K is produced, it must be optimal, and any shortest sequence must be

an eulerian circuit in a dB graph.

The de Bruijn graph Tn has as its vertex set the binary n-strings.

Directed edges join n-strings that may be derived by deleting the left

most digit and appending a 0 or 1 to the right end. de Bruijn + van

Ardenne-Ehrenfest (in 1951) counted the number of eulerian circuits in

Tn. There are 2^(2^(n-1)-n) of them.

Some examples:

K=2 1100

K=3 11101000

K=4 1111001011010000

The solution to the above problem (non-circular strings) can be found

by duplicating the first K-1 digits of the solution string at the end

of the string. These are not the only solutions, but they

are of minimum length: 2^K + K-1.

We can obtain a lower bound for the optimal sequence for the general case as

follows:

Consider first the simpler case of breaking into an answer machine which

accepts d+1 digits, values 0 to n-1. We wish to find the minimal universal

code that will allow us access to any such answering machine.

Let us construct a digraph G = (V,E), where the n^d vertices are labelled

with a d sequence of digits. Notation: let [v_{i,1},v_{i,2},...,v_{i,d}]

denote the labelling on node v_i. An edge e = (v_i, v_j) is in E iff for k

in 1, ..., d-1: v_{i,k+1} = v_{j,k}, i.e., the last d-1 digits in the

labelling of the initial vertex of e is identical with the first d-1 digits

in the labelling of the terminal vertex of e. We associate with each edge a

value, t(e) = v_{j,d}, the last digit in the labelling of the terminal

vertex.

The intuition goes as follows: we are going to perform a Euler circuit of

the digraph, where the label on the current vertex gives the last d digits

in the output sequence so far. If we make a transition on edge e, we output

the tone/digit t(e) as the next output value, thus preserving the invariant

on the labelling.

How do we know that a Euler circuit exists? Simple: a connected digraph

has an Euler circuit iff for all vertices v: indegree(v) = outdegree(v).

This property is trivially true for this digraph.

So, in order to generate a universal code for the AM, we simply output 0^d

(to satisfy the precondition for being in vertex [0,...,0]), and perform an

Euler circuit starting at node [0,...,0].

Now, the total length of the universal sequence is just the number of edges

traversed in the Euler circuit plus the initial precondition sequence, or

n^d * n + d (number of vertices times the out-degree) or n^{d+1} + d. That

this is a minimal sequence is obvious.

Next, let us consider the machine AM' where the security code is of the form

[0...n-1]^d [0...m-1], i.e., d digits ranging from 0 to n-1, followed by a

terminal digit ranging from 0 to m-1, m < n.

We build a digraph G = (V, E) similar to the construction above, except for

the following: an edge e is in E iff t(e) in 0 to m-1. This digraph is

clearly non-Eulerian. In particular, there are two classes of vertices:

(1) v is of the form [0...n-1]^{d-1} [0...m-1] (``fat'' vertices)

and

(2) v is of the form [0...n-1]^{d-1} [m...n-1] (``thin'' vertices)

Observations: there are (n^{d-1} * m) fat vertices, and (n^{d-1} * (n-m))

thin vertices. All vertices have out-degree of m. Fat vertices have

in-degrees of n, and thin vertices have in-degrees of 0. Color all the

edges blue.

The question now becomes: can we put a bound on how many new (red) edges

must we add to G in order to make a blue edge covering path possible?

(Instead of thinking of edges being traversed multiple times in the blue

edge covering path, we allow multiple edges between vertices and allow each

edge to be traversed once.) Note that, in this procedure, we add edges only

if it is allowed (the vertex labelling constraint). We will first obtain a

lower bound on the length of a blue covering circuit, and then transform it

into a bound for arbitrary blue covering paths.

Clearly, we must add at least (n-m)*(n^{d-1}*m) edges incident from the fat

vertices. [ We need (n-m) new out-going edges for each of (n^{d-1}*m)

vertices to bring the out-degree up to the in-degree. ]

Let us partition our vertices into sets. Denote the range [0..m-1] by S,

the range [m..n-1] by L, and the range [0..n-1] by X.

Let S_0 = { v: v = [X^{d-1}S] }. S_0 is just the set of fat vertices.

Define in(S_0) = number of edges from vertices not in S to vertices in S.

Define out(S_0) in the corresponding fashion, and let excess(S_0) =

in(S_0)-out(S_0). Clearly, excess(S_0) = n^{d-1}m(n-m) from the argument

above. Generalizing the requirement for Eulerian digraphs, we see that we

must add excess(S_0) edges from S_0 if the blue edges connected to/within

S_0 are to be covered by some circuit (edges may not be travered multiple

times -- we add parallel edges to handle that case). In particular, edges

from S_0 will be incident on vertices of the form [X^{d-2}SX]. Furthermore,

they can not be [X^{d-2}SS] since that is a subset of S_0 and adding those

edges will not help excess(S_0). [Now, these edges may be needed if we are

to have a circuit, but we do not consider them since they do not help

excess(S_0).] So, we are forced to add excess(S_0) edges from S_0 to S_1 = {

v: v = [X^{d-2}SL] }. Color these newly added edges red.

Let us define in(S_1), out(S_1) and excess(S_1) as above for the modified

digraph, i.e., including the red excess(S_0) edges that we just added.

Clearly, in(S_1) = out(S_0) = n^{d-1}m(n-m), and out(S_1) = m*|S_1| =

m*n^{d-2}m(n-m), so excess(S_1) = n^{d-2}m(n-m)^2. Consider S_0 union S_1.

We must add excess(S_1) edges to S_0 union S_1 to make it possible for the

digraph to be covered by a circuit, and these edges must go from {S_0 union

S_1} to S_2 = { v: v = [X^{d-3}SL^2] } by a similar argument as before.

Repeating this partitioning process, eventually we get to S_{d-1} = { v: v =

[SL^{d-1}] }, where union of S_0 to S_{d-1} will need edges to S_d = { v: v

= [L^d] }, where this process terminates. Note that at this time,

excess(union of S_0 to S_{d-1}) = m(n-m)^d, but in(S_d) = 0 and out(S_d) =

m(n-m)^d, and the process terminates.

What have we shown? Adding up blue edges and the red edges gives us a lower

bound on the total number of edges in a blue-edges covering circuit (not

necessarily Eulerian) in the complete digraph. This comes out to be

n^{d+1}-(n-m)^{d+1} edges.

Next, we note that if we had an optimal path covering all the blue edges, we

can transform it into a circuit by adding d edges. So, a minimal path can

be no more than d edges shorter than the minimal circuit covering all blue

edges. [Otherwise, we add d extra edges to make it into a shorter circuit.]

So the shortest blue covering path through the digraph is at least

n^{d+1}-{n-m}^{d+1}-d. With an initial pre-condition sequence of length d

(to establish the transition invariant), the shortest universal answering

machine sequence is of length at least n^{d+1}-(n-m)^{d+1}.

While this has not been that constructive, it is easy to see that we can

achieve this bound. If we looked at the vertices in each of the S_i's, we

just add exactly the edges to S_{i+1} and no more. The resultant digraph

would be Eulerian, and to find the minimal path we need only start at the

vertex labelled [{n-1}^d], find the Euler circuit, and omit the last d edges

from the tour.

==> combinatorics/gossip.p <==

n people each know a different piece of gossip. They can telephone each other

and exchange all the information they know (so that after the call they both

know anything that either of them knew before the call). What is the smallest

number of calls needed so that everyone knows everything?

==> combinatorics/gossip.s <==

1 for n=2

3 for n=3

2n-4 for n>=4

This can be achieved as follows: choose four people (A, B, C, and D) as

the "core group". Each person outside the core group phones a member of

the core group (it doesn't matter which); this takes n-4 calls. Now the

core group makes 4 calls: A-B, C-D, A-C, and B-D. At this point, each

member of the core group knows everything. Now, each person outside the

core group calls anybody who knows everything; this again requires n-4

calls, for a total of 2n-4.

The solution to the "gossip problem" has been published several times:

1. R. Tidjeman, "On a telephone problem", Nieuw Arch. Wisk. 3

(1971), 188-192.

2. B. Baker and R. Shostak, "Gossips and telephones", Discrete

Math. 2 (1972), 191-193.

3. A. Hajnal, E. C. Milner, and E. Szemeredi, "A cure for the

telephone disease", Canad Math. Bull 15 (1976), 447-450.

4. Kleitman and Shearer, Disc. Math. 30 (1980), 151-156.

5. R. T. Bumby, "A problem with telephones", Siam J. Disc. Meth. 2

(1981), 13-18.

==> combinatorics/grid.dissection.p <==

How many (possibly overlapping) squares are in an mxn grid? Assume that all

the squares have their edges parallel to the edges of the grid.

==> combinatorics/grid.dissection.s <==

Given an n*m grid with n > m.

Orient the grid so n is its width. Divide the grid into two portions,

an m*m square on the left and an (n-m)*m rectangle on the right.

Count the squares that have their upper right-hand corners in the

m*m square. There are m^2 of size 1*1, (m-1)^2 of size 2*2, ...

up to 1^2 of size m*m. Now look at the n-m columns of lattice points

in the rectangle on the right, in which we find upper right-hand

corners of squares not yet counted. For each column we count m new

1*1 squares, m-1 new 2*2 squares, ... up to 1 new m*m square.

Combining all these counts in summations:

m m

total = sum i^2 + (n - m) sum i

i=1 i=1

(2m + 1)(m + 1)m (n - m)(m + 1)m

= ---------------- + ---------------

6 2

= (3n - m + 1)(m + 1)m/6

-- David Karr

==> combinatorics/permutation.p <==

Compute the nth permutation of k numbers (or objects).

==> combinatorics/permutation.s <==

#include <stdio.h>

/*

adapted from 'Notation as a Tool of Thought', by K.E.Iverson

Radix Representation of Permutations

*/

/* direct from radix; of given order */

dfr(short direct[],short radix[],long order)

{

if (order)

{

direct[0] = radix[0];

dfr (direct+1, radix+1, order-1);

while (--order)

direct[order] += direct[order] >= direct[0];

}

}

/* radix representation; of given order and given index */

rr(short radix[], long order, long index)

{

int i;

for (i=1; i<=order; i++)

{

radix[order-i] = index % i;

index = index/i;

}

}

show(short perm[],long order)

{

while(order--)

printf("%hd ",*perm++);

printf("\n");

}

short parity(short radix[],long order)

{

long p=0;

while(order--)

p+=*radix++;

return p%2;

}

void usage(char *name)

{

fprintf(stderr,"usage: %s order number_of_permutation\n",name);

exit(-1);

}

main(int argc, char *argv[])

{

#define MAX_ORDER 512

short radix[MAX_ORDER], direct[MAX_ORDER];

long order, nth;

if (argc!=3) usage(argv[0]);

order = atol(argv[1]);

nth = atol(argv[2]);

rr(radix, order, nth-1); /* where 0 is the first permuatation */

dfr(direct, radix, order);

printf("radix "); show(radix,order);

printf("direct "); show(direct,order);

printf("parity %d\n",parity(radix,order));

}

--

J. Henri Schueler, H&h Software, Toronto +1 416 698 9075

j...@ipsa.reuter.com

==> combinatorics/subsets.p <==

Out of the set of integers 1,...,100 you are given ten different

integers. From this set, A, of ten integers you can always find two

disjoint non-empty subsets, S & T, such that the sum of elements in S

equals the sum of elements in T. Note: S union T need not be all ten

elements of A. Prove this.

==> combinatorics/subsets.s <==

There are 2^10 = 1,024 subsets of the 10 integers, but there can be only 901

possible sums, the number of integers between the minimum and maximum sums.

With more subsets than possible sums, there must exist at least one sum that

corresponds to at least two subsets. Call two subsets with equal sums A and B.

Let C = A intersect B; define S = A - C, T = B - C. Then S is disjoint from T,

and sum(S) = sum(A-C) = sum(A) - sum(C) = sum(B) - sum(C) = sum(B-C) = sum(T).

QED

Addendum: 9 integers suffice. This was part of my Westinghouse project

in 1981 (the above problem was in Martin Gardner's Scientific American

column not long before). The argument is along the same lines, but

a bit more complicated; for starters you only work with the subsets

consisting of 3, 4, 5, or 6 of the 9 elements.

Let M(n) be the smallest integer such that there exists an n-element

set {a1,a2,a3,...,an=M(n)} of positive integers all 2^n of whose

subsums are distinct. The pigeonhole argument of subsets.s shows that

M(n)>2^n/n, and it is known that M(n)>c*2^n/sqrt(n) for some c>0.

It is still an unsolved problem (with an Erdos bounty) whether

there is a positive constant c such that M(n)>c*2^n for all n.

--Noam D. Elkies (elk...@zariski.harvard.edu)

Dept. of Mathematics, Harvard University

==> combinatorics/transitions.p <==

How many n-bit binary strings (0/1) have exactly k transitions

(an adjacent pair of dissimilar bits, i.e., a 01 or a 10)?

==> combinatorics/transitions.s <==

A transition can occur at an adjacent pair (i,i+1) where 1<=i<i+1<=n.

Since there are k transitions, there are C(n-1,k) total number of ways

that transitions can occur. But the string may start with a 1 or a 0

(after which its transitions uniquely determine the string). So there

are a total of 2C(n-1,k) such strings.

Aug 18, 1993, 2:04:40 AM8/18/93

to

Archive-name: puzzles/archive/competition/part1

Last-modified: 17 Aug 1993

Version: 4

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

m...@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 to...@mantis.co.uk OR tony%mantis...@uknet.ac.uk

OR EVEN ar...@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

* d...@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 or 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 matrix? */

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.

vic...@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)

a...@unhcs.unh.edu, a...@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.

Aug 18, 1993, 2:04:47 AM8/18/93

to

Archive-name: puzzles/archive/competition/part2

Last-modified: 17 Aug 1993

Version: 4

Last-modified: 17 Aug 1993

Version: 4

==> 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: myrb...@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

sou...@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,

ro...@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 (ka...@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.

Aug 18, 1993, 2:04:31 AM8/18/93

to

Archive-name: puzzles/archive/arithmetic/part1

Last-modified: 17 Aug 1993

Version: 4

Last-modified: 17 Aug 1993

Version: 4

==> arithmetic/7-11.p <==

A customer at a 7-11 store selected four items to buy, and was told

that the cost was $7.11. He was curious that the cost was the same

as the store name, so he inquired as to how the figure was derived.

The clerk said that he had simply multiplied the prices of the four

individual items. The customer protested that the four prices

should have been ADDED, not MULTIPLIED. The clerk said that that

was OK with him, but, the result was still the same: exactly $7.11.

What were the prices of the four items?

==> arithmetic/7-11.s <==

The prices are: $1.20, $1.25, $1.50, and $3.16

$7.11 is not the only number which works. Here are the first 160 such

numbers, preceded by a count of distinct solutions for that price.

Note that $7.11 has a single, unique solution.

1 - $6.44 1 - $7.83 2 - $9.20 3 - $10.89

1 - $6.51 1 - $7.86 1 - $9.23 1 - $10.95

1 - $6.60 3 - $7.92 1 - $9.24 2 - $11.00

1 - $6.63 1 - $8.00 1 - $9.27 1 - $11.07

1 - $6.65 1 - $8.01 2 - $9.35 1 - $11.13

1 - $6.72 1 - $8.03 3 - $9.36 1 - $11.16

2 - $6.75 5 - $8.10 1 - $9.38 1 - $11.22

1 - $6.78 1 - $8.12 5 - $9.45 2 - $11.25

1 - $6.80 1 - $8.16 2 - $9.48 2 - $11.27

2 - $6.84 2 - $8.19 1 - $9.54 1 - $11.30

1 - $6.86 1 - $8.22 1 - $9.57 1 - $11.36

1 - $6.89 1 - $8.25 1 - $9.59 1 - $11.40

2 - $6.93 3 - $8.28 2 - $9.60 2 - $11.43

1 - $7.02 3 - $8.33 1 - $9.62 2 - $11.52

1 - $7.05 1 - $8.36 2 - $9.63 2 - $11.55

2 - $7.07 1 - $8.37 1 - $9.66 2 - $11.61

1 - $7.08 2 - $8.40 1 - $9.68 1 - $11.69

1 - $7.11 1 - $8.45 2 - $9.69 1 - $11.70

1 - $7.13 2 - $8.46 1 - $9.78 1 - $11.88

2 - $7.14 1 - $8.52 2 - $9.80 1 - $11.90

3 - $7.20 5 - $8.55 1 - $9.81 1 - $11.99

1 - $7.25 1 - $8.60 1 - $9.87 1 - $12.06

1 - $7.26 4 - $8.64 4 - $9.90 1 - $12.15

2 - $7.28 1 - $8.67 1 - $9.92 1 - $12.18

1 - $7.29 1 - $8.69 2 - $9.99 1 - $12.24

3 - $7.35 1 - $8.73 1 - $10.01 1 - $12.30

1 - $7.37 2 - $8.75 1 - $10.05 1 - $12.32

1 - $7.47 1 - $8.76 2 - $10.08 1 - $12.35

1 - $7.50 1 - $8.78 1 - $10.17 2 - $12.42

1 - $7.52 5 - $8.82 1 - $10.20 1 - $12.51

4 - $7.56 1 - $8.85 2 - $10.26 1 - $12.65

1 - $7.62 1 - $8.88 3 - $10.29 2 - $12.69

4 - $7.65 2 - $8.91 3 - $10.35 1 - $12.75

1 - $7.67 1 - $8.94 2 - $10.44 1 - $12.92

2 - $7.70 1 - $8.96 1 - $10.53 1 - $12.96

3 - $7.74 3 - $9.00 1 - $10.56 1 - $13.23

1 - $7.77 1 - $9.02 1 - $10.64 1 - $13.41

1 - $7.79 2 - $9.03 2 - $10.71 1 - $13.56

2 - $7.80 1 - $9.12 3 - $10.80 1 - $14.49

1 - $7.82 2 - $9.18 1 - $10.85 1 - $15.18

There are plenty of solutions for five summands. Here are a few:

$8.28 -- at least two solutions

$8.47 -- at least two solutions

$8.82 -- at least two solutions

--

Mark Johnson ma...@microunity.com (408) 734-8100

There may be many approximate solutions, for example: $1.01, $1.15, $2.41,

and $2.54. These sum to $7.11 but the product is 7.1100061.

==> arithmetic/arithmetic.progression.p <==

Is there an arithmetic progression of 20 or more primes?

==> arithmetic/arithmetic.progression.s <==

There is an arithmetic progression of 21 primes:

142072321123 + 1419763024680 i, 0 <= i < 21.

It was discovered on 30 November 1990, by programs running in the background

on a network of Sun 3 workstations in the Department of Computer Science,

University of Queensland, Australia.

See: Andrew Moran and Paul Pritchard, The design of a background job

on a local area network, Procs. 14th Australian Computer Science Conference,

1991, to appear.

==> arithmetic/clock/day.of.week.p <==

It's restful sitting in Tom's cosy den, talking quietly and sipping

a glass of his Madeira.

I was there one Sunday and we had the usual business of his clock.

When the radio gave the time at the hour, the Ormolu antique was

exactly 3 minutes slow.

"It loses 7 minutes every hour", my old friend told me, as he had done

so many times before. "No more and no less, but I've gotten used to

it that way."

When I spent a second evening with him later that same month, I remarked

on the fact that the clock was dead right by radio time at the hour.

It was rather late in the evening, but Tom assured me that his treasure

had not been adjusted nor fixed since my last visit.

What day of the week was the second visit?

From "Mathematical Diversions" by Hunter + Madachy

==> arithmetic/clock/day.of.week.s <==

The answer is 17 days and 3 hours later, which would have been a Wednesday.

This is the only other time in the same month when the two would agree at all.

In 17 days the slow clock loses 17*24*7 minutes = 2856 minutes,

or 47 hours and 36 minutes. In 3 hours more it loses 21 minutes, so

it has lost a total of 47 hours and 57 minutes. Modulo 12 hours, it

has *gained* 3 minutes so as to make up the 3 minutes it was slow on

Sunday. It is now (fortnight plus 3 days) exactly accurate.

Since the clock was not adjusted since the last visit, it's also

possible that the radio time shifted by one hour due to a change to or

from summer daylight saving time. However, it turns out that the only

additional possibilities that need to be considered are those of 4 days

15 hours later, when the clock would have lost 12 hours 57 minutes, and

29 days 15 hours later, when the clock would have lost 3 days 10 hours

57 minutes. Without even considering the rules for when in the month the

clock is changed, these possible solutions are ruled out because we know

that both visits were in the evening ("I spent a second evening with him").

and they involve times in a different part of the day.

==> arithmetic/clock/palindromic.p <==

How many times per day does a digital clock display a palindromic number?

==> arithmetic/clock/palindromic.s <==

The problem is underspecified. Digital clocks may run from

(a) 1:00 to 12:59

(b) 01:00 to 12:59

(c) 0:00 to 23:59

(d) 00:00 to 23:59

(e-h) any of the above with seconds appended, :00 to :59.

I agree that not all of these are common, but I have seen some uncommon

ones. For that matter, I've seen ones not on the above list -- the Toronto

subway stations used to contain digital clocks that ran from 0:00 to 12:59

(pm), then from 1:00 (pm) to 11:59 (pm), while a computer that I used to

use had the inverse anomaly -- its time of day command displayed times

from 12:00:00 to 12:59:59 (am), then 01:00:00 to 23:59:59!

I get the following results for the 8 cases.

CASE AM+PM HOURS pals/hr TOTAL OVERALL TOTAL

(a) yes 1-9 6 54

10-12 1 3 114

(b) yes 01-05 1 5

06-09 0 0

10-12 1 3 16

(c) no 0-9 6 60

10-15 1 6

16-19 0 0

20-23 1 4 70

(d) no 00-05 1 6

06-09 0 0

10-15 1 6

16-19 0 0

20-23 1 4 16

(e) yes 1-9 60 540

10-12 6 18 1116

(f) yes 01-05 6 30

06-09 0 0

10-12 6 18 96

(g) no 0-9 60 600

10-15 6 36

16-19 0 0

20-23 6 24 660

(h) no 00-05 6 36

06-09 0 0

10-15 6 36

16-19 0 0

20-23 6 24 96

--Mark Brader (m...@sq.com)

==> arithmetic/clock/reversible.p <==

How many times per day can the hour and minute hands on an analog clock switch

roles and still signify a valid time, ignoring the second hand?

==> arithmetic/clock/reversible.s <==

Have 12 clocks C1, C2 ... C12 show 1:00, 2:00, ..., 12:00. Have a

clock C0 show 12:00

Now turn C0 around 12 hours, simultaneously turning C1-C12 so their

hour hands always coincide with the minute hand of C0, i.e., as C0

spans 12 hours, C1-C12 will span 1 hour, but for each possible placing

of the hour hand, all 12 possible 'true' placings of the minute hand

will be represented by one of the 12 clocks.

Each time the hour hand of C0 coincides with the minute hand of a

C1-C12 clock we have a reversible valid time. This happens regularly

12 times each C0 hour, but the first and last time is equal (12:00), so

the number of reversible true times is 12*12-1 = 143 spaced regularly

in the 12-hour interval, ie. each 5 min 2.0979+ sec

--

stein....@tf.tele.no [X.400] stein....@nta.no [internet]

==> arithmetic/clock/right.angle.p <==

How many times per day do the hour and minute hands of a clock form a

right angle?

==> arithmetic/clock/right.angle.s <==

44. Twice each hour equals 48, less one between 2:00 and 4:00 and one between

8:00 and 10:00 for both A.M. and P.M.

==> arithmetic/clock/thirds.p <==

Do the 3 hands on a clock ever divide the face of the clock into 3

equal segments, i.e. 120 degrees between each hand?

==> arithmetic/clock/thirds.s <==

First let us assume that our clock has 60 divisions. We will show that

any time the hour hand and the minute hand are 20 divisions (120 degrees)

apart, the second hand cannot be an integral number of divisions from the

other hands, unless it is straight up (on the minute).

Let us use h for hours, m for minutes, and s for seconds.

We will use =n to mean congruent mod n, thus 12 =5 7.

We know that m =60 12h, that is, the minute hand moves 12 times as fast

as the hour hand, and wraps around at 60.

We also have s =60 60m. This simplifies to s/60 =1 m, which goes to

s/60 = frac(m) (assuming s is in the range 0 <= s < 60), which goes to

s = 60 frac(m). Thus, if m is 5.5, s is 30.

Now let us assume the minute hand is 20 divisions ahead of the hour hand.

So m =60 h + 20, thus 12h =60 h + 20, 11h =60 20, and, finally,

h =60/11 20/11 (read 'h is congruent mod 60/11 to 20/11').

So all values of m are k + n/11 for some integral k and integral n,

0 <= n < 11. s is therefore 60n/11. If s is to be an integral number of

units from m and h, we must have 60n =11 n. But 60 and 11 are relatively

prime, so this holds only for n = 0. But if n = 0, m is integral, so

s is 0.

Now assume, instead, that the minute hand is 20 divisions behind the hour hand.

So m =60 h - 20, 12h =60 h - 20, 11h =60 -20, h =60/11 -20/11.

So m is still k + n/11. Thus s must be 0.

But if s is 0, h must be 20 or 40. But this translates to 4 o'clock or

8 o'clock, at both of which the minute hand is at 0, along with the second

hand.

Thus the 3 hands can never be 120 degrees apart, Q.E.D.

This assumes, of course, that the second hand is synchronized with the

minute hand. This is not true on some inexpensive analog watches. This

also assumes that the watch is not broken (:^)).

==> arithmetic/consecutive.composites.p <==

Are there 10,000 consecutive non-prime numbers?

==> arithmetic/consecutive.composites.s <==

9973!+2 through 9973!+10006 are composite.

==> arithmetic/consecutive.product.p <==

Prove that the product of three or more consecutive positive integers cannot

be a perfect square.

==> arithmetic/consecutive.product.s <==

Three consecutive numbers:

If a and b are relatively prime, and ab is a square,

then a and b are squares. (This is left as an exercise.)

Suppose (n - 1)n(n + 1) = k^2, where n > 1.

Then n(n^2 - 1) = k^2. But n and (n^2 - 1) are relatively prime.

Therefore n^2 - 1 is a perfect square, which is a contradiction.

Four consecutive numbers:

n(n + 1)(n + 2)(n + 3) = (n^2 + 3n + 1)^2 - 1

Five consecutive numbers:

Assume the product is a integer square, call it m.

The prime factorization of m must have even numbers of each prime factor.

For each prime factor, p, of m, p >= 5, p^2k must divide one of the

consecutive naturals in the product. (Otherwise, the difference between two

of the naturals in the product would be a positive multiple of a prime >= 5.

But in this problem, the greatest difference is 4.) So we need only consider

the primes 2 and 3.

Each of the consecutive naturals is one of:

1) a perfect square

2) 2 times a perfect square

3) 3 times a perfect square

4) 6 times a perfect square.

By the shoe box principle, two of the five consecutive numbers must fall into

the same category.

If there are two perfect squares, then their difference being less than five

limits their values to be 1 and 4. (0 is not a natural number, so 0 and 1

and 0 and 4 cannot be the perfect squares.) But 1*2*3*4*5=120!=x*x where x

is an integer.

If there are two numbers that are 2 times a perfect square, then their

difference being less than five implies that the perfect squares (which are

multiplied by 2) are less than 3 apart, and no two natural squares differ by

only 1 or 2.

A similar argument holds for two numbers which are 3 times a perfect square.

We cannot have the case that two of the 5 consecutive numbers are multiples

(much less square multiples) of 6, since their difference would be >= 6, and

our span of five consecutive numbers is only 4.

Therefore the assumption that m is a perfect square does not hold.

QED.

In general the equation:

y^2 = x(x+1)(x+2)...(x+n), n > 3

has only the solution corresponding to y = 0.

This is a theorem of Rigge [O. Rigge, ``Uber ein diophantisches Problem'',

IX Skan. Math. Kong. Helsingfors (1938)] and Erdos [P. Erdos, ``Note on

products of consecutive integers,'' J. London Math. Soc. #14 (1939),

pages 194-198].

A proof can be found on page 276 of [L. Mordell, ``Diophantine

Equations'', Academic Press 1969].

==> arithmetic/consecutive.sums.p <==

Find all series of consecutive positive integers whose sum is exactly 10,000.

==> arithmetic/consecutive.sums.s <==

Generalize to find X (and I) such that

(X + X+1 + X+2 + ... + X+I) = T

for any integer T.

You are asking for all (X,I) s.t. (2X+I)(I+1) = 2T. The problem is

(very) slightly easier if we don't restrict X to being positive, so

we'll solve this first.

Note that 2X+I and I+1 must have different parities, so the answer

to the relaxed question is N = 2*(o_1+1)*(o_2+1)*...*(o_n+1), where

2T = 2^o_0*3^o_1*...*p_n^o_n (the prime factorization); this is easily

seen to be the number of ways we can break 2T up into two positive

factors of differing parity (with order).

In particular, 20000 = 2^5*5^4, hence there are 2*(4+1) = 10 solutions

for T = 10000. These are (2X+I,I+1):

(32*1,5^4) (32*5,5^3) (32*5^2,5^2) (32*5^3,5) (32*5^4,1)

(5^4,32*1) (5^3,32*5) (5^2,32*5^2) (5,32*5^3) (1,32*5^4)

And they give rise to the solutions (X,I):

(-296,624) (28,124) (388,24) (1998,4) (10000,0)

(297,31) (-27,179) (-387,799) (-1997,3999) (-9999,19999)

If you require that X>0 note that this is true iff 2X+I > I+1 and

hence the number of solutions to this problem is N/2 (due to the

symmetry of the above ordered pairs).

==> arithmetic/conway.p <==

Describe the sequence a(1)=a(2)=1, a(n) = a(a(n-1)) + a(n-a(n-1)) for n>2.

==> arithmetic/conway.s <==

This sequence and its remarkable properties were discovered, apparently

independently, by Douglas Hofstadter (circa 1975), John Conway (in the

early 1980's), B.W. Connoly, and others. Since Conway discovered many of

the deeper properties, and is the one responsible for popularizing the

sequence, it seems appropriate to name the sequence after him.

Some properties of a(n):

-- a(n+1) - a(n) = 0 or 1

-- a(2^n) = 2^(n-1)

-- n/2 <= a(n) <= n

-- A(n)= 2a(n) - n has zeros at the powers of 2 and

positive "humps" in between

-- A(2^n + t) = A(2^(n+1) - t) for t between 0 and 2^n,

i.e. the humps are symmetric

-- a(2n) <= 2a(n)

-- a(n)/n --> 1/2 as n --> infinity

-- a(n) and A(n) are self-similar, in the sense that their values on the

(N+1)'st hump can be obtained by a "magnification" process applied

to the values on the N'th hump. They are *not* chaotic sequences,

since their asymptotics and combinatorial structure are very regular

and rigid.

In a lecture at Bell Labs in 1988, Conway asked for the rate at

which a(n)/n converges to 1/2. In particular, he asked for

N(epsilon), the last value of n such that |a(n)/n - 1/2|

exceeds epsilon, in the case epsilon=1/20. This problem was

solved by Colin Mallows of Bell Labs: he found that N(1/20)=1489

and N(1/40)=6083008742. These values are reported in his article

in the American Mathematical Monthly, January 1991, p. 5.

Conway's sequence has a deep combinatorial structure, and is intimately

connected with all of the following: variants of Pascal's triangle, the

Gaussian distribution, combinatorial operations on finite sets,

coin-pushing games, and Fibonacci and Catalan numbers. All of this is

explained in my joint paper with Ravi Vakil; anyone who would like to

receive a copy in LaTex format should contact me at the e-mail address

listed below.

One byproduct of our work is an algorithm to determine N(epsilon) for

given positive epsilon. Here are some particular values:

e Last n such that |a(n)/n - 1/2| > e

---- ----------------------------------------------------------

1/20 1489 (found by Mallows in 1988)

1/30 758765

1/40 6083008742 (found by Mallows in 1988)

1/50 809308036481621

1/60 1684539346496977501739

1/70 55738373698123373661810220400

1/80 15088841875190938484828948428612052839

1/90 127565909103887972767169084026274554426122918035

1/100 8826608001127077619581589939550531021943059906967127007025

These values were computed by the Mathematica program listed below; the

algorithm is explained in our paper. To use the program, load it into

Mathematica and type neps[t] for some numerical value of t (which

should probably be smaller than 1/5 or so). The program will output N(t),

e.g. neps[1/20] = 1489. These numbers grow very fast: N(epsilon) will be

about 2^((0.138015/epsilon)^2), so N(1/1000) will have about 5735 digits.

The program requires very little memory space, but its runtime appears to

grow rapidly as epsilon decreases (on a Sun 3, it took about one second to

find the first value listed, and several minutes to find the last).

neps[eps_] := Block[{W}, L = 1 + Floor[(0.138015/eps)^2]; e = eps*2;

W = processvector[L]; While[Length[W] > 0,

nmax = 1 + Last[W][[4]]; L++; W = processvector[L]]; nmax]

processvector[L_] :=

Block[{V}, V = startvector[L]; While[notfound[V], V = newbody[V]]; V]

startvector[L_] := Select[initialvector[L], gt]

initialvector[L_] :=

Table[{L, b, Binomial[L - 1, b - 1],

2^(L + 1) - Sum[Binomial[L, c], {c, b, L}]}, {b, 0, L - 1}]

c[0] = 0

c[n_] := c[n] = Sum[Binomial[2*a, a]/(a + 1), {a, 0, n - 1}]

gt[x_] := U[x] > e

U[x_] := (x[[3]] + M[x[[1]], x[[2]]])/(x[[4]] + incp[x[[1]], x[[2]]])

M[n_, n_] = -1

M[n_, k_] := Binomial[n - 1, K[n, k]] - Binomial[n - 1, k - 1] + c[K[n, k]]

K[n_, k_] := Min[k, n - k]

incp[n_, k_] := Max[M[n, k], 1]

notfound[V_] :=

Length[V] > 0 && Last[V][[2]] > 0 && Last[V][[1]] > Last[V][[2]]

newbody[V_] := Join[Drop[V, -1], newtail[V]]

newtail[V_] := Select[{vleft[Last[V]], vright[Last[V]]}, gt]

vleft[x_] := {x[[1]] - 1, x[[2]] - 1, x[[3]], x[[4]]}

vright[x_] := {x[[1]] - 1, x[[2]], x[[3]] + S[x[[1]] - 1, x[[2]] - 1],

x[[4]] + Binomial[x[[1]] - 1, x[[2]] - 1]}

S[n_, k_] := Binomial[n - 1, k] - Binomial[n - 1, k - 1]

-Tal Kubo ku...@math.harvard.edu or ku...@zariski.harvard.edu

==> arithmetic/digits/6.and.7.p <==

Does every number which is not divisible by 5 have a multiple whose

only digits are 6 and 7?

==> arithmetic/digits/6.and.7.s <==

Yes. My proof follows:

Claim 1: For every k, there is a k-digit number whose only digits

are 6 and 7, which is divisible by 2^k.

The proof is by induction. Suppose N is a k-digit number

satisfying the above condition. Then either N = 0 (mod 2^(k+1))

or N = 2^k (mod 2^(k+1)). Note that 6(10^k) = 0 (mod 2^(k+1)),

and 7(10^k) = 2^k (mod 2^(k+1)). So, either 6*10^k + N or

7*10^k + N is divisible by 2^(k+1).

Claim 2: If m and 10 are relatively prime, then for any r,

there is a number N whose only digits are 6 and 7 such that

N = r (mod m).

Proof: Let K be the (m^2)-digit number whose only digit is 6.

There is an s, 0 <= s < m, so that K + s = r (mod m).

Let N = K + 10^(m - 1) + 10^(2m - 2) + . . . + 10^(sm - s).

Since 10^(im - i) = 1 (mod m), N = K + s (mod m) = r (mod m).

Clearly, every digit of N is either 6 or 7.

Claim 3: If n is not divisible by 5, then there is a number N whose

only digits are 6 and 7, so that N is divisible by n.

Proof: We can write n = (2^k)m, with gcd(m,10)=1.

Use claim 1 to find a k-digit number M, whose only digits are 6 and 7,

which is divisible by 2^k. Choose an integer r so that

(10^k)r + M = 0 (mod m). Use claim 2 to find a number K whose

only digits are 6 and 7, so that K = r (mod m). Let N = 10^k K + M.

Then N = 0 (mod m) and N = 0 (mod 2^k), so N is divisible by n.

Finally, the only digits of N are 6 and 7, so we are done.

--

David Radcliffe radc...@csd4.csd.uwm.edu

==> arithmetic/digits/all.ones.p <==

Prove that some multiple of any integer ending in 3 contains all 1s.

==> arithmetic/digits/all.ones.s <==

Let n be our integer; one such desired multiple is then

(10^(phi(n))-1)/9. All we need is that (n,10) = 1, and if the last

digit is 3 this must be the case. A different proof using the

pigeonhole principle is to consider the sequence 1, 11, 111, ..., (10^n

- 1)/9. We must have at some point that either some member of our

sequence = 0 (mod n) or else some value (mod n) is duplicated. Assume

the latter, with x_a and x_b, x_b>x_a, possesing the duplicated

remainders. We then have that x_b - x-a = 0 (mod n). Let m be the

highest power of 10 dividing x_b - x_a. Now since (10,n) = 1, we can

divide by 10^m and get that (x_b - x_a)/10^m = 0 (n). But (x_b -

x_a)/10^m is a number containing only the digit 1.

Q.E.D.

==> arithmetic/digits/arabian.p <==

What is the Arabian Nights factorial, the number x such that x! has 1001

digits? How about the prime x such that x! has exactly 1001 zeroes on

the tail end. (Bonus question, what is the 'rightmost' non-zero digit in x!?)

==> arithmetic/digits/arabian.s <==

The first answer is 450!.

Determining the number of zeroes at the end of x! is relatively easy once

you realize that each such zero comes from a factor of 10 in the product

1 * 2 * 3 * ... * x

Each factor of 10, in turn, comes from a factor of 5 and a factor of 2.

Since there are many more factors of 2 than factors of 5, the number of 5s

determines the number of zeroes at the end of the factorial.

The number of 5s in the set of numbers 1 .. x (and therefore the number

of zeroes at the end of x!) is:

z(x) = int(x/5) + int(x/25) + int(x/125) + int(x/625) + ...

This series terminates when the powers of 5 exceed x.

I know of no simple way to invert the above formula (i.e., to find x for

a given z(x)), but I can approximate it by noting that, except for the "int"

function,

5*z(x) - x = z(x)

which gives:

x = 4*z(x) (approximately).

The given problem asked, "For what prime x is z(x)=1001". By the above forumla,

this is approximately 4*1001=4004. However, 4004! has only

800 + 160 + 32 + 6 + 1 = 999 zeroes at the end of it.

The numbers 4005! through 4009! all have 1000 zeroes at their end and

the numbers 4010! through 4014! all have 1001 zeroes at their end.

Since the problem asked for a prime x, and 4011 = 3*7*191, the only solution

is x=4013.

The problem of determining the rightmost nonzero digit in x! is somewhat more

difficult. If we took the numbers 1, 2, ... , x and removed all factors of 5

(and an equal number of factors of 2), the remaining numbers multiplied

together modulo 10 would be the answer. Note that since there are still many

factors of 2 left, the rightmost nonzero digit must be 2, 4, 6, or 8 (x > 1).

Letting r(x) be the rightmost nonzero digit in x!, an expression for r(x) is:

r(x) = (r(int(x/5)) * w * r(x mod 10)) mod 10, x >= 10.

where w is 4 if int(x/10) is odd and 6 if it is even.

The values of r(x) for 0 <= x <= 9 are 1, 1, 2, 6, 4, 2, 2, 4, 2, and 8.

The way to see this is true is to take the numbers 1, 2, ..., x in groups

of 10. In each group, remove 2 factors of 10. For example, from the

set 1, 2, ..., 10, choose a factor of 2 from 2 and 6 and a factor of 5 from

5 and 10. This leaves 1, 1, 3, 4, 1, 3, 7, 8, 9, 2. Next, separate all the

factors that came from multiples of 5. The rightmost nonzero digit of x!

can now (hopefully) be seen to be:

r(x) = (r(int(x/5)) * w * r(x mod 10)) mod 10

where w is the rightmost digit in the number formed by multiplying the numbers

1, 2, 3, ..., 10*int(x/10) after the factors of 10 and the factors left over

by the multiples of 5 have been removed. In the example with x = 10, this

would be (1 * 1 * 3 * 4 * 3 * 7 * 8 * 9) mod 10 = 4. The "r(x mod 10)" term

takes care of the numbers from 10*int(x/10)+1 up to x.

The "w" term can be seen to be 4 or 6 depending on whether int(x/10) is odd or

even since, after removing 10*n+5 and 10*n+10 and a factor of 2 each from

10*n+2 and 10*n+6 from the group of numbers 10*n+1 through 10*n+10, the

remaining factors (mod 10) always equals 4 and 4^t mod 10 = 4 if t is odd and

6 when t is even (t != 0).

So, finally, the rightmost nonzero digit in 4013! is found as follows:

r(4013) = (r(802) * 4 * 6) mod 10

r(802) = (r(160) * 6 * 2) mod 10

r(160) = (r(32) * 6 * 1) mod 10

r(32) = (r(6) * 4 * 2) mod 10

Using a table of r(x) for 0 <= x <= 9, r(6) = 2. Then,

r(32) = (2 * 4 * 2) mod 10 = 6

r(160) = (6 * 6 * 1) mod 10 = 6

r(802) = (6 * 6 * 2) mod 10 = 2

r(4013) = (2 * 4 * 6) mod 10 = 8

Thus, the rightmost nonzero digit in 4013! is 8.

==> arithmetic/digits/circular.p <==

What 6 digit number, with 6 different digits, when multiplied by all integers

up to 6, circulates its digits through all 6 possible positions, as follows:

ABCDEF * 1 = ABCDEF

ABCDEF * 3 = BCDEFA

ABCDEF * 2 = CDEFAB

ABCDEF * 6 = DEFABC

ABCDEF * 4 = EFABCD

ABCDEF * 5 = FABCDE

==> arithmetic/digits/circular.s <==

ABCDEF=142857 (the digits of the expansion of 1/7).

==> arithmetic/digits/divisible.p <==

Find the least number using 0-9 exactly once that is evenly divisible by each

of these digits.

==> arithmetic/digits/divisible.s <==

Since the sum of the digits is 45, any permutation of the digits gives a

multiple of 9. To get a multiple of both 2 and 5, the last digit must

be 0, and thus to get a multiple of 8 (and 4), the tens digit must be

even, and the hundreds digit must be odd if the tens digit is 2 or 6,

and even otherwise. The number will also be divisible by 6, since it is

divisible by 2 and 3, so 7 is all we need to check. First, we will look

for a number whose first five digits are 12345; now, 1234500000 has a

remainder of 6 when divided by 7, so we have to arrange the remaining

digits to get a remainder of 1. The possible arrangements, in

increasing order, are

78960, remainder 0

79680, remainder 6

87960, remainder 5

89760, remainder 6

97680, remainder 2

98760, remainder 4

That didn't work, so try numbers starting with 12346; this is impossible

because the tens digit must be 8, and the hundreds digit cannot be even.

Now try 12347, and 1234700000 has remainder 2. The last five digits can

be

58960, remainder 6

59680, remainder 5, so this works, and the number is

1234759680.

==> arithmetic/digits/equations/123456789.p <==

In how many ways can "." be replaced with "+", "-", or "" (concatenate) in

.1.2.3.4.5.6.7.8.9=1 to form a correct equation?

==> arithmetic/digits/equations/123456789.s <==

1-2 3+4 5+6 7-8 9 = 1

+1-2 3+4 5+6 7-8 9 = 1

1+2 3+4-5+6 7-8 9 = 1

+1+2 3+4-5+6 7-8 9 = 1

-1+2 3-4+5+6 7-8 9 = 1

1+2 3-4 5-6 7+8 9 = 1

+1+2 3-4 5-6 7+8 9 = 1

1-2 3-4+5-6 7+8 9 = 1

+1-2 3-4+5-6 7+8 9 = 1

1-2-3-4 5+6 7-8-9 = 1

+1-2-3-4 5+6 7-8-9 = 1

1+2-3 4+5 6-7-8-9 = 1

+1+2-3 4+5 6-7-8-9 = 1

-1+2 3+4+5-6-7-8-9 = 1

-1 2+3 4-5-6+7-8-9 = 1

1+2+3+4-5+6+7-8-9 = 1

+1+2+3+4-5+6+7-8-9 = 1

-1+2+3-4+5+6+7-8-9 = 1

1-2-3+4+5+6+7-8-9 = 1

+1-2-3+4+5+6+7-8-9 = 1

1+2 3+4 5-6 7+8-9 = 1

+1+2 3+4 5-6 7+8-9 = 1

1+2 3-4-5-6-7+8-9 = 1

+1+2 3-4-5-6-7+8-9 = 1

1+2+3+4+5-6-7+8-9 = 1

+1+2+3+4+5-6-7+8-9 = 1

-1+2+3+4-5+6-7+8-9 = 1

1-2+3-4+5+6-7+8-9 = 1

+1-2+3-4+5+6-7+8-9 = 1

-1-2-3+4+5+6-7+8-9 = 1

1-2+3+4-5-6+7+8-9 = 1

+1-2+3+4-5-6+7+8-9 = 1

1+2-3-4+5-6+7+8-9 = 1

+1+2-3-4+5-6+7+8-9 = 1

-1-2+3-4+5-6+7+8-9 = 1

-1+2-3-4-5+6+7+8-9 = 1

-1+2 3+4 5-6 7-8+9 = 1

1-2 3-4 5+6 7-8+9 = 1

+1-2 3-4 5+6 7-8+9 = 1

-1+2 3-4-5-6-7-8+9 = 1

-1+2+3+4+5-6-7-8+9 = 1

1-2+3+4-5+6-7-8+9 = 1

+1-2+3+4-5+6-7-8+9 = 1

1+2-3-4+5+6-7-8+9 = 1

+1+2-3-4+5+6-7-8+9 = 1

-1-2+3-4+5+6-7-8+9 = 1

1+2-3+4-5-6+7-8+9 = 1

+1+2-3+4-5-6+7-8+9 = 1

-1-2+3+4-5-6+7-8+9 = 1

-1+2-3-4+5-6+7-8+9 = 1

1-2-3-4-5+6+7-8+9 = 1

+1-2-3-4-5+6+7-8+9 = 1

1-2 3+4+5+6+7-8+9 = 1

+1-2 3+4+5+6+7-8+9 = 1

1+2+3+4 5-6 7+8+9 = 1

+1+2+3+4 5-6 7+8+9 = 1

1 2+3 4+5-6 7+8+9 = 1

+1 2+3 4+5-6 7+8+9 = 1

1+2+3-4-5-6-7+8+9 = 1

+1+2+3-4-5-6-7+8+9 = 1

-1+2-3+4-5-6-7+8+9 = 1

1-2-3-4+5-6-7+8+9 = 1

+1-2-3-4+5-6-7+8+9 = 1

-1-2-3-4-5+6-7+8+9 = 1

-1-2 3+4+5+6-7+8+9 = 1

1-2+3 4-5 6+7+8+9 = 1

+1-2+3 4-5 6+7+8+9 = 1

1 2-3 4+5-6+7+8+9 = 1

+1 2-3 4+5-6+7+8+9 = 1

Total solutions = 69 (26 of which have a leading "+", which is redundant)

69/19683 = 0.35 %

for those who care (it's not very elegant but it did the trick):

#include <stdio.h>

#include <math.h>

main (argc,argv)

int argc;

char *argv[];

{

int sresult, result, operator[10],thisop;

char buf[256],ops[3];

int i,j,tot=0,temp;

ops[0] = ' ';

ops[1] = '-';

ops[2] = '+';

for (i=1; i<10; i++) operator[i] = 0;

for (j=0; j < 19683; j++) {

result = 0;

sresult = 0;

thisop = 1;

for (i=1; i<10; i++) {

switch (operator[i]) {

case 0:

sresult = sresult * 10 + i;

break;

case 1:

result = result + sresult * thisop;

sresult = i;

thisop = -1;

break;

case 2:

result = result + sresult * thisop;

sresult = i;

thisop = 1;

break;

}

}

result = result + sresult * thisop;

if (result == 1) {

tot++;

for (i=1;i<10;i++)

printf("%c%d",ops[operator[i]],i);

printf(" = %d\n",result);

}

temp = 0;

operator[1] += 1;

for (i=1;i<10;i++) {

operator[i] += temp;

if (operator[i] > 2) { operator[i] = 0; temp = 1;}

else temp = 0;

}

}

printf("Total solutions = %d\n" , tot);

}

cw...@media.mit.edu (Christopher Wren)

==> arithmetic/digits/equations/1992.p <==

1 = -1+9-9+2. Extend this list to 2 through 100 on the left side of

the equals sign.

==> arithmetic/digits/equations/1992.s <==

1 = -1+9-9+2

2 = 1*9-9+2

3 = 1+9-9+2

4 = 1+9/9+2

5 = 1+9-sqrt(9)-2

6 = 1^9+sqrt(9)+2

7 = -1+sqrt(9)+sqrt(9)+2

8 = 19-9-2

9 = (1/9)*9^2

10= 1+(9+9)/2

11= 1+9+sqrt(9)-2

12= 19-9+2

13= (1+sqrt(9))!-9-2

14= 1+9+sqrt(9)!-2

15= -1+9+9-2

16= -1+9+sqrt(9)!+2

17= 1+9+9-2

18= 1+9+sqrt(9)!+2

19= -1+9+9+2

20= (19-9)*2

21= 1+9+9+2

22= (-1+sqrt(9))*(9-2)

23= (1+sqrt(9))!-sqrt(9)+2

24= -1+9*sqrt(9)-2

25= 1*9*sqrt(9)-2

26= 19+9-2

27= 1*9+9*2

28= 1+9+9*2

29= 1*9*sqrt(9)+2

30= 19+9+2

31= (1+sqrt(9))!+9-2

32= -1+sqrt(9)*(9+2)

33= 1*sqrt(9)*(9+2)

34= (-1+9+9)*2

35= -1+(9+9)*2

36= 1^9*sqrt(9)!^2

37= 19+9*2

38= 1*sqrt(9)!*sqrt(9)!+2

39= 1+sqrt(9)!*sqrt(9)!+2

40= (1+sqrt(9)!)*sqrt(9)!-2

41= -1+sqrt(9)!*(9-2)

42= (1+sqrt(9))!+9*2

43= 1+sqrt(9)!*(9-2)

44= -1+9*(sqrt(9)+2)

45= 1*9*(sqrt(9)+2)

46= 1+9*(sqrt(9)+2)

47= (-1+sqrt(9)!)*9+2

48= 1*sqrt(9)!*(sqrt(9)!+2)

49= (1+sqrt(9)!)*(9-2)

50= (-1+9)*sqrt(9)!+2

51= -1+9*sqrt(9)!-2

52= 1*9*sqrt(9)!-2

53= -1+9*sqrt(9)*2

54= 1*9*sqrt(9)*2

55= 1+9*sqrt(9)*2

56= 1*9*sqrt(9)!+2

57= 1+9*sqrt(9)!+2

58= (1+9)*sqrt(9)!-2

59= 19*sqrt(9)+2

60= (1+9)*sqrt(9)*2

61= (1+sqrt(9)!)*9-2

62= -1+9*(9-2)

63= 1*9*(9-2)

64= 1+9*(9-2)

65= (1+sqrt(9)!)*9+2

66= 1*sqrt(9)!*(9+2)

67= 1+sqrt(9)!*(9+2)

68= -(1+sqrt(9))!+92

69= (1+sqrt(9))!+(9/.2)

70= (1+9)*(9-2)

71= -1-9+9^2

72= (1+sqrt(9))*9*2

73= -19+92

74= (-1+9)*9+2

75= -1*sqrt(9)!+9^2

76= 1-sqrt(9)!+9^2

77= (1+sqrt(9)!)*(9+2)

78= -1+9*9-2

79= 1*9*9-2

80= 1+9*9-2

81= 1*9*sqrt(9)^2

82= -1+9*9+2

83= 1*9*9+2

84= 1+9*9+2

85= -1-sqrt(9)!+92

86= -1*sqrt(9)!+92

87= 1-sqrt(9)!+92

88= (1+9)*9-2

89= -1*sqrt(9)+92

90= 1-sqrt(9)+92

91= -1^9+92

92= (1+9)*9+2

93= 1^9+92

94= -1+sqrt(9)+92

95= 19*(sqrt(9)+2)

96= -1+99-2

97= 1*99-2

98= 1+99-2

99= 1*9*(9+2)

100= -1+99+2

==> arithmetic/digits/equations/24.p <==

Form an expression that evaluates to 24 that contains two 3's, two 7's,

and zero or more of the operators +, -, *, and /, and parentheses. What

about two 4's and two 7's, or three 5's and one 1, or two 3's and two 8's?

==> arithmetic/digits/equations/24.s <==

7*(3+3/7)

7*(4-4/7)

5*(5-1/5)

8/(3-8/3)

==> arithmetic/digits/equations/383.p <==

Make 383 out of 1,2,25,50,75,100 using +,-,*,/.

==> arithmetic/digits/equations/383.s <==

You can get 383 with ((2+50)/25+1)*100+75.

Of course, if you expect / as in C, the above expression is just 375.

But then you can get 383 with (25*50-100)/(1+2). Pity there's no way

to use the 75.

If we had a language that rounded instead of truncating, we could use

((1+75+100)*50)/(25-2) or (2*75*(25+100))/(50-1).

I imagine your problem lies in not dividing things that aren't

divisible.

Dan Hoey

Ho...@AIC.NRL.Navy.Mil

==> arithmetic/digits/equations/find.p <==

Write a program for finding expressions built out of given numbers and using

given operators that evaluate to a given value, or listing all possible values.

==> arithmetic/digits/equations/find.s <==

As set up, it requires recompilation for different sets of numbers;

it's currently set up for 8,8,3,3; to try in other numbers, stick 'em

in the 'val' array. To find all target numbers for which the equation

is valid, uncomment the 't' loop and 'target = t', and extend the range

to be checked... you might want to turn off VERBOSE. I don't bother

with eliminating symmetries if equal vals are given (like 8 8 3 3), so

I normally use it like

numop 24 | sort | uniq

As it stands, this gives the output:

8 / (3 - (8 / 3)) = 24.0

8 / (3 - (8 / 3)) = 24.0

8 / (3 - (8 / 3)) = 24.0

8 / (3 - (8 / 3)) = 24.0

As you can see, there are five different kinds of binary trees with

exactly four leaf nodes. The program tries all four operators in each

place, and all four values in each of the leaves, guaranteeing that each

is used only once... a fairly quick operation. A small extract from

'numop 1' shows the five different shapes of trees:

((3 * 8) / 3) / 8 = 1.0

(3 * (8 / 3)) / 8 = 1.0

(3 - 3) + (8 / 8) = 1.0

3 * ((8 / 3) / 8) = 1.0

3 * (8 / (3 * 8)) = 1.0

Probably FUDGE ought to be set a little lower, for more confidence that

the equality isn't fortuitous. Extensions to other binary operators are

obvious; unary operators and more values are not. For a more general

problem I'd go recursive, use exact rational arithmetic, and have a fine

old time.

Enjoy...

Jim Gillogly <uunet!rand.org!James_Gillogly>

21 Wedmath S.R. 1993, 10:58

----------------------------------------------------------------

/* numop: using elementary operations on 4 numbers, find a

* desired result; e.g. 24.

*

* Don't worry about symmetries resulting in multiple correct answers.

*

* 11 Aug 93, SCRYER

*/

#include <stdio.h>

#define VERBOSE

#define MUL 0

#define DIV 1

#define ADD 2

#define SUB 3

#define FUDGE 0.01

float val[4] = {8, 8, 3, 3};

float eval(), atof(), fabs();

char nameop();

int divzero;

main(argc, argv)

int argc;

char *argv[];

{

int op1, op2, op3;

int iv1, iv2, iv3, iv4;

int used[4];

int i;

float target;

float e1, e2, e3;

int t, winner;

if (argc != 2)

{

fprintf(stderr, "Usage: numop <target>\n");

exit(1);

}

target = atof(argv[1]);

/* for (t = -1000; t < 1000; t++) */

{

/* target = t;*/

winner = 0;

for (i = 0; i < 4; i++) used[i] = 0;

for (op1 = 0; op1 < 4; op1++)

for (op2 = 0; op2 < 4; op2++)

for (op3 = 0; op3 < 4; op3++)

for (iv1 = 0; iv1 < 4; iv1++)

{

used[iv1] = 1;

for (iv2 = 0; iv2 < 4; iv2++)

{

if (used[iv2]) continue;

used[iv2] = 1;

for (iv3 = 0; iv3 < 4; iv3++)

{

if (used[iv3]) continue;

used[iv3] = 1;

for (iv4 = 0; iv4 < 4; iv4++)

{

if (used[iv4]) continue;

/* Case 1 */

divzero = 0;

e3 = eval(op3, val[iv3], val[iv4]);

e2 = eval(op2, val[iv1], val[iv2]);

e1 = eval(op1, e2, e3); /* (u + v) * (w - x) */

if (fabs(e1 - target) < FUDGE && ! divzero)

#ifdef VERBOSE

printf("(%.0f %c %.0f) %c (%.0f %c %.0f) = %.1f\n",

val[iv1], nameop(op2), val[iv2], nameop(op1),

val[iv3], nameop(op3), val[iv4], e1);

#else

winner = 1;

#endif

/* Case 2 */

divzero = 0;

e3 = eval(op3, val[iv1], val[iv2]);

e2 = eval(op2, e3, val[iv3]);

e1 = eval(op1, e2, val[iv4]); /* ((u + v) * w) - x */

if (fabs(e1 - target) < FUDGE && ! divzero)

#ifdef VERBOSE

printf("((%.0f %c %.0f) %c %.0f) %c %.0f = %.1f\n",

val[iv1], nameop(op3), val[iv2], nameop(op2), val[iv3], nameop(op1), val[iv4], e1);

#else

winner = 1;

#endif

/* Case 3 */

divzero = 0;

e3 = eval(op3, val[iv2], val[iv3]);

e2 = eval(op2, val[iv1], e3);

e1 = eval(op1, e2, val[iv4]); /* (u + (v * w)) - x */

if (fabs(e1 - target) < FUDGE && ! divzero)

#ifdef VERBOSE

printf("(%.0f %c (%.0f %c %.0f)) %c %.0f = %.1f\n",

val[iv1], nameop(op2), val[iv2], nameop(op3), val[iv3],

nameop(op1), val[iv4], e1);

#else

winner = 1;

#endif

/* Case 4 */

divzero = 0;

e3 = eval(op3, val[iv2], val[iv3]);

e2 = eval(op2, e3, val[iv4]);

e1 = eval(op1, val[iv1], e2); /* u + ((v * w) - x) */

if (fabs(e1 - target) < FUDGE && ! divzero)

#ifdef VERBOSE

printf("%.0f %c ((%.0f %c %.0f) %c %.0f) = %.1f\n",

val[iv1], nameop(op1), val[iv2], nameop(op3), val[iv3],

nameop(op2), val[iv4], e1);

#else

winner = 1;

#endif

/* Case 5 */ /* u + (v * (w - x)) */

divzero = 0;

e3 = eval(op3, val[iv3], val[iv4]);

e2 = eval(op2, val[iv2], e3);

e1 = eval(op1, val[iv1], e2);

if (fabs(e1 - target) < FUDGE && ! divzero)

#ifdef VERBOSE

printf("%.0f %c (%.0f %c (%.0f %c %.0f)) = %.1f\n",

val[iv1], nameop(op1), val[iv2], nameop(op2), val[iv3],

nameop(op3), val[iv4], e1);

#else

winner = 1;

#endif

}

used[iv3] = 0;

}

used[iv2] = 0;

}

used[iv1] = 0;

}

#ifndef VERBOSE

if (winner) printf("%d\n", t), fflush(stdout);

#endif

}

}

char nameop(op)

int op;

{

switch(op)

{

case MUL: return '*';

case DIV: return '/';

case ADD: return '+';

case SUB: return '-';

}

return '?';

}

float eval(op, val1, val2)

int op;

float val1, val2;

{

switch(op)

{

case MUL: return val1 * val2;

case DIV:

if (val2 == 0.)

{

divzero = 1;

#ifdef EXTREMELYVERBOSE

fprintf(stderr, "Division by zero.\n");

#endif

}

return val2 == 0.? 0. : val1 / val2;

case ADD: return val1 + val2;

case SUB: return val1 - val2;

}

return 0.;

}

==> arithmetic/digits/extreme.products.p <==

What are the extremal products of three three-digit numbers using digits 1-9?

==> arithmetic/digits/extreme.products.s <==

There is a simple procedure which applies to these types of problems (and

which can be proven with help from the arithmetic-geometric inequality).

For the first part we use the "first large then equal" procedure.

This means that are three numbers will be 7**, 8**, and 9**. Now

the digits 4,5,6 get distributed so as to make our three number as

close to each other as possible, i.e. 76*, 85*, 94*. The same goes

for the remaining three digits, and we get 763, 852, 941.

For the second part we use the "first small then different" procedure.

Our three numbers will be of the form 1**, 2**, 3**. We now place

the three digits so as to make our three numbers as unequal as possible;

this gives 14*, 25*, 36*. Finishing, we get 147, 258, 369.

Now, *prove* that these procedures work for generalizations of this

problem.

==> arithmetic/digits/labels.p <==

You have an arbitrary number of model kits (which you assemble for

fun and profit). Each kit comes with twenty (20) stickers, two of which

are labeled "0", two are labeled "1", ..., two are labeled "9".

You decide to stick a serial number on each model you assemble starting

with one. What is the first number you cannot stick. You may stockpile

unused numbers on already assembled models, but you may not crack open

a new model to get at its stickers. You complete assembling the current

model before starting the next.

==> arithmetic/digits/labels.s <==

The method I used for this problem involved first coming up with a

formula that says how many times a digit has been used in all n models.

n = k*10^i + m for some k,m with 0 <k <10, m < 10^i

f(d,n) = (number of d's used getting to k*10^i from digits 0 to (i-1)) +

(number of d's used by #'s 10^i to n from digit i) + f(d,m)

f(d,n) = i*k*10^(i-1) + (if (d < k) 10^i else if (d == k) m+1 else 0) + f(d,m)

This doesn't count 0's, which should be ok as they are not used as often

as other digits. From the formula, it is clear that f(1,n) is never

less than f(d,n) for 1<d<10.

So I just calculated f(1,n) for various n (with some help from bc).

I quickly discovered that for n = 2*10^15, f(1,n) = 2*n. After further

trials I determined that for n = 1999919999999981, f(1,n) = 2*n + 1.

This appears to be the smallest n with f(1,n) > 2*n.

==> arithmetic/digits/least.significant/factorial.p <==

What is the least significant non-zero digit in the decimal expansion of n!?

==> arithmetic/digits/least.significant/factorial.s <==

Reduce mod 10 the numbers 2..n and then cancel out the

required factors of 10. The final step then involves

computing 2^i*3^j*7^k mod 10 for suitable i,j and k.

A small program that performs this calculation is appended. Like the

other solutions, it takes O(log n) arithmetic operations.

-kym

===

#include<stdio.h>

#include<assert.h>

int p[6][4]={

/*2*/ 2, 4, 8, 6,

/*3*/ 3, 9, 7, 1,

/*4*/ 4, 6, 4, 6,

/*5*/ 5, 5, 5, 5,

/*6*/ 6, 6, 6, 6,

/*7*/ 7, 9, 3, 1,

};

main(){

int i;

int n;

for(n=2;n<1000;n++){

i=lsdfact(n);

printf("%d\n",i);

}

exit(0);

}

lsdfact(n){

int a[10];

int i;

int n5;

int tmp;

for(i=0;i<=9;i++)a[i]=alpha(i,n);

n5=0;

/* NOTE: order is important in following */

l5:;

while(tmp=a[5]){ /* cancel factors of 5 */

n5+=tmp;

a[1]+=(tmp+4)/5;

a[3]+=(tmp+3)/5;

a[5]=(tmp+2)/5;

a[7]+=(tmp+1)/5;

a[9]+=(tmp+0)/5;

}

l10:;

if(tmp=a[0]){

a[0]=0; /* cancel all factors of 10 */

for(i=0;i<=9;i++)a[i]+=alpha(i,tmp);

}

if(a[5]) goto l5;

if(a[0]) goto l10;

/* n5 == number of 5's cancelled;

must now cancel same number of factors of 2 */

i=ipow(2,a[2]+2*a[4]+a[6]+3*a[8]-n5)*

ipow(3,a[3]+a[6]+2*a[9])*

ipow(7,a[7]);

assert(i%10); /* must not be zero */

return i%10;

}

alpha(d,n){

/* number of decimal numbers in [1,n] ending in digit d */

int tmp;

tmp=(n+10-d)/10;

if(d==0)tmp--; /* forget 0 */

return tmp;

}

ipow(x,y){

/* x^y mod 10 */

if(y==0) return 1;

if(y==1) return x;

return p[x-2][(y-1)%4];

}

==> arithmetic/digits/least.significant/tower.of.power.p <==

What are the least significant digits of 9^(8^(7^(6^(5^(4^(3^(2^1))))))) ?

==> arithmetic/digits/least.significant/tower.of.power.s <==

9^11 = 9 (mod 100), so we need to find 8^...^1 (mod 10).

8^5 = 8 (mod 10), so we need to find 7^...^1 (mod 4).

7^3 = 7 (mod 4), so we need to find 6^...^1 (mod 2), but

this is clearly 0, so 7^...^1 = 1 (mod 4) ==>

8^...^1 = 8 (mod 10) ==> 9^...^1 = 9^8 (mod 100) = 21 (mod 100).

==> arithmetic/digits/most.significant/googol.p <==

What digits does googol! start with?

==> arithmetic/digits/most.significant/googol.s <==

I'm not sure how to calculate the first googol of digits of log10(e), but

here's the first 150(approximately) of them...

0.43429448190325182765112891891660508229439700580366656611445378316586464920

8870774729224949338431748318706106744766303733641679287158963906569221064663

We need to deal with the digits immediately after the decimal point in

googol*log10(e), which are .187061

frac[log(googol!)] = frac[halflog2pi + 50 + googol(100-log10(e))]

= frac{halflog2pi + frac[googol(100-log10(e))]}

= frac[.399090 + (1- .187061)]

= .212029

10 ** .212029 = 1.629405

Which means that googol! starts with 1629

==> arithmetic/digits/most.significant/powers.p <==

What is the probability that 2^N begins with the digits 603245?

==> arithmetic/digits/most.significant/powers.s <==

2^N begins with 603245 iff 603246*10^m > 2^N >= 603245*10^m for some

positive integer m ==> m+log(603246) > N*log(2) >= m+log(603245);

so 2^N begins with 603245 iff frac(log(603246)) > frac(N*log(2))

>= frac(log(603245)). If we are using natural density then N*log(2)

is uniformly distributed mod 1 since log(2) is irrational, hence the

probability is frac(log(603246)) - frac(log(603245)) =

frac(log(603246)-log(603245)) = frac(log(603246/603245)).

A neat observation is that since it is known p_n*c, where p_n is the

nth prime and c is irrational, is uniformly distributed mod 1, we get

the same answer if we replace 2^N with 2^{p_n}.

--

Chris Long, 265 Old York Rd., Bridgewater, NJ 08807-2618

==> arithmetic/digits/nine.digits.p <==

Form a number using 0-9 once with its first n digits divisible by n.

==> arithmetic/digits/nine.digits.s <==

First, reduce the sample set. For each digit of ABCDEFGHI, such that the last

digit, (current digit), is the same as a multiple of N :

A: Any number 1-9

B: Even numbers 2,4,6,8 (divisible by 2).

C: Any number 1-9 (21,12,3,24,15,6,27,18,9).

D: Even numbers 2,4,6,8 (divisible by 4, every other even).

E: 5 (divisible by 5 and 0 not allowed).

F: Even numbers (12,24,6,18)

G: Any number 1-9 (21,42,63,14,35,56,7,28,49).

H: Even numbers (32,24,16,8)

I: Any number 1-9 (81,72,63,54,45,36,27,18,9)

Since E must be 5, I can eliminate it everywhere else.

Since I will use up all the even digits, (2,4,6,8) filling in those spots

that must be even. Any number becomes all odds, except 5.

A: 1,3,7,9

B: 2,4,6,8

C: 1,3,7,9

D: 2,4,6,8

E: 5

F: 2,4,6,8

G: 1,3,7,9

H: 2,4,6,8

I: 1,3,7,9

We have that 2C+D=0 (mod 4), and since C is odd,

this implies that D is 2 or 6; similarly we find that H is 2 or 6 ==>

{B,F} = {4,8}. D+5+F=0 (mod 3) ==> if D=2 then F=8, if D=6 then F=4.

We have two cases.

Assume our number is of the form A4C258G6I0. Now the case n=8 ==>

G=1,9; case n=3 ==> A+1+C=0 (mod 3) ==> {A,C}={1,7} ==> G=9, I=3.

The two numbers remaining fail for n=7.

Assume our number is of the form A8C654G2I0. The case n=8 ==> G=3,7.

If G=3, we need to check to see which of 1896543, 9816543, 7896543,

and 9876543 are divisible by 7; none are.

If G=7, we need to check to see which of 1896547, 9816547, 1836547,

and 3816547 are divisible by 7; only the last one is, which yields

the solution 3816547290.

==> arithmetic/digits/palindrome.p <==

Does the series formed by adding a number to its reversal always end in

a palindrome?

==> arithmetic/digits/palindrome.s <==

This is not known.

If you start with 196, after 9480000 iterations you get a 3924257-digit

non-palindromic number. However, there is no known proof that you will

never get a palindrome.

The statement is provably false for binary numbers. Roland Sprague has

shown that 10110 starts a series that never goes palindromic.

==> arithmetic/digits/palintiples.p <==

Find all numbers that are multiples of their reversals.

==> arithmetic/digits/palintiples.s <==

We are asked to find numbers that are integer multiples of their

reversals, which I call palintiples. Of course, all the palindromic

numbers are a trivial example, but if we disregard the unit multiples,

the field is narrowed considerably.

Rouse Ball (_Mathematical_recreations_and_essays_) originated the

problem, and G. H. Hardy (_A_mathematician's_apology_) used the result

that 9801 and 8712 are the only four-digit palintiples as an example

of a theorem that is not ``serious''. Martin Beech (_The_mathema-

tical_gazette_, Vol 74, #467, pp 50-51, March '90) observed that

989*01 and 879*12 are palintiples, an observation he ``confirmed'' on

a hand calculator, and conjectured that these are all that exist.

I confirm that Beech's numbers are palintiples, I will show that they

are not all of the palintiples. I will show that the palintiples do

not form a regular language. And then I will prove that I have found

all the palintiples, by describing the them with a generalized form

of regular expression. The results become more interesting in other

bases.

First, I have a more reasonable method of confirming that these

numbers are palintiples:

Proof: First, letting "9*" and "0*" refer an arbitrary string of

nines and a string of zeroes of the same length, I note that

879*12 = 879*00 + 12 = (880*00 - 100) + 12 = 880*00 - 88

219*78 = 219*00 + 78 = (220*00 - 100) + 78 = 220*00 - 22

989*01 = 989*00 + 1 = (990*00 - 100) + 1 = 990*00 - 99

109*89 = 109*00 + 89 = (110*00 - 100) + 89 = 110*00 - 11

It is obvious that 4x(220*00 - 22) = 880*00 - 88 and that

9x(110*00 - 11) = 990*00 - 99. QED.

Now, to show that these palintiples are not all that exist, let us

take the (infinite) language L[4] = (879*12 + 0*), and let Pal(L[4])

refer to the set of palindromes over the alphabet L[4]. It is

immediate that the numbers in Pal(L[4]) are palintiples. For

instance,

8712 000 87912 879999912 879999912 87912 000 8712

= 4 x 2178 000 21978 219999978 219999978 21978 000 2178

(where I have inserted spaces to enhance readability) is a palintiple.

Similarly, taking L[9] = (989*01 + 0*), the numbers in Pal(L[9]) are

palintiples. We exclude numbers starting with zeroes.

The reason these do not form a regular language is that the

sub-palintiples on the left end of the number must be the same (in

reverse order) as the sub-palintiples on the right end of the number:

8712 8712 87999912 = 4 x 2178 2178 21999978

is not a palintiple, because 8712 8712 87999912 is not the reverse of

2178 2178 21999978. The pumping lemma can be used to prove that

Pal(L[4])+Pal(L[9]) is not a regular language, just as in the familiar

proof that the palindromes over a non-singleton alphabet do not form a

regular language.

Now to characterize all the palintiples, let N be a palintiple,

N=CxR(N), where R(.) signifies reversal, and C>1 is an integer. (I

use "x" for multiplication, to avoid confusion with the Kleene star

"*", which signifies the concatenated closure.) If D is a digit of N,

let D' refer to the corresponding digit of R(N). Since N=CxR(N),

D+10T = CxD'+S, where S is the carry in to the position occupied by D'

when R(N) is multiplied by C, and T is the carry out of that position.

Similarly, D'+10T'=CxD+S', where S', T' are carries in and out of the

position occupied by D when R(N) is multiplied by C.

Since D and D' are so closely related, I will use the symbol D:D' to

refer to a digit D on the left side of a string with a corresponding

digit D' on the right side of the string. More formally, an

expression "x[1]:y[1] x[2]:y[2] ... x[n]:y[n] w" will refer to a

string "x[1] x[2] ... x[n] w y[n] ... y[2] y[1]", where the x[i] and

y[i] are digits and w is a string of zero or one digits. So 989901

may be written as 9:1 8:0 9:9 and 87912 may be written as 8:2 7:1 9.

Thus Pal(L[4])+Pal(L[9]) (omitting numbers with leading zeroes) can be

represented as

(8:2 7:1 9:9* 1:7 2:8 0:0*)*

(0:0* + 0 + 8:2 7:1 ( 9:9* + 9:9* 9))

+ (9:1 8:0 9:9* 0:8 1:9 0:0*)*

(0:0* + 0 + 9:1 8:0 ( 9:9* + 9:9* 9)). (1)

For each pair of digits D:D', there are a very limited--and often

empty--set of quadruples S,T,S',T' of digits that satisfy the

equations

D +10T =CxD'+S

D'+10T'=CxD +S', (2)

yet such a quadruple must exist for "D:D'" to appear in a palintiple

with multiplier C. Furthermore, the S and T' of one D:D' must be T

and S', respectively, of the next pair of digits that appear. This

enables us to construct a finite state machine to recognize those

palintiples. The states [X#Y] refer to a pair of carries in D and D',

and we allow a transition from state [T#S'] to state [S#T'] on input

symbol D:D' exactly when equations (2) are satisfied. Special

transitions for a single-digit input symbol (the central digit of

odd-length palintiples) and the criteria for the initial and the

accepting states are left as exercises. The finite state machines

thus formed are

State Symbol New Symbol New Symbol New

Accept? State State State

--> [0#0] Y 8:2 [0#3] 0:0 [0#0] 0 [A]

[0#3] N 7:1 [3#3]

[3#3] Y 1:7 [3#0] 9:9 [3#3] 9 [A]

[3#0] N 2:8 [0#0]

[A] Y

for constant C=4, and

State Symbol New Symbol New Symbol New

Accept? State State State

--> [0#0] Y 1:9 [0#8] 0:0 [0#0] 0 [A]

[0#8] N 8:0 [8#8]

[8#8] Y 0:8 [8#0] 9:9 [8#8] 9 [A]

[8#0] N 9:1 [0#0]

[A] Y

for constant C=9, and the finite state machines for other constants

accept only strings of zeroes. It is not hard to verify that the

proposed regular expression (1) represents the union of the languages

accepted by these machines, omitting the empty string and strings

beginning with zero.

I have written a computer program that constructs finite state

machines for recognizing palintiples for various bases and constants.

I found that base 10 is actually an unusually boring base for this

problem. For instance, the machine for base 8, constant C=5 is

State Symbol New Symbol New Symbol New

Accept? State State State

--> [0#0] Y 0:0 [0#0] 5:1 [0#3] 0 [A]

[0#3] N 1:0 [1#1] 6:1 [1#4]

[1#1] Y 0:1 [3#0] 5:2 [3#3]

[3#0] N 1:5 [0#0] 6:6 [0#3] 6 [A]

[3#3] Y 2:5 [1#1] 7:6 [1#4]

[1#4] N 1:1 [4#1] 6:2 [4#4] 1 [A]

[4#4] Y 2:6 [4#1] 7:7 [4#4] 7 [A]

[4#1] N 1:6 [3#0] 6:7 [3#3]

[A] Y

for which I invite masochists to write the regular expression. If

anyone wants more, I should remark that the base 29 machine for

constant C=18 has 71 states!

By the way, I did not find any way of predicting the size or form of

the machines for the various bases, except that the machines for C=B-1

all seem to be isomorphic to each other. If anyone investigates the

general behavior, I would be most happy to hear about it.

Dan Hoey

Ho...@AIC.NRL.Navy.Mil

May, 1992

[ A preliminary version of this message appeared in April, 1991. ]

================================================================

Dan

==> arithmetic/digits/power.two.p <==

Prove that for any 9-digit number (base 10) there is an integral power

of 2 whose first 9 digits are that number.

==> arithmetic/digits/power.two.s <==

Let v = log to base 10 of 2.

Then v is irrational.

Let w = log to base 10 of these 9 digits.

Since v is irrational, given epsilon > 0, there exists some natural number

n such that

{w} < {nv} < {w} + epsilon

({x} is the fractional part of x.) Let us pick n for when

epsilon = log 1.00000000000000000000001.

Then 2^n does the job.

==> arithmetic/digits/prime/101.p <==

How many primes are in the sequence 101, 10101, 1010101, ...?

==> arithmetic/digits/prime/101.s <==

Note that the sequence

101 , 10101, 1010101, ....

can be viewed as

100**1 +1, 100**2 + 100**1 + 1, 100**3 + 100**2 + 100**1 +1 ....

that is,

the k-th term in the sequence is

100**k + 100**(k-1) + 100**(k-2) + ...+ 100**(1) + 1

= (100)**(k+1) - 1

----------------

11 * 9

= (10)**(2k+2) - 1

----------------

11 * 9

= ((10)**(k+1) - 1)*((10)**(k+1) +1)

---------------------------------

11*9

thus either 11 and 9 divide the numerator. Either they both divide the

same factor in the numerator or different factors in the numerator. In

any case, after dividing, they leave the numerators as a product of two

integers. Only in the case of k = 1, one of the integers is 1. Thus

there is exactly one prime in the above sequence: 101.

==> arithmetic/digits/prime/all.prefix.p <==

<