This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

Title: Cliff Puzzle 15: Cherries in Wine Glasses

From: cliff@watson.ibm.com

If you respond to this puzzle, if possible please send me your name,

address, affiliation, e-mail address, so I can properly credit you if

you provide unique information. PLEASE ALSO directly mail me a copy of

your response in addition to any responding you do in the newsgroup. I

will assume it is OK to describe your answer in any article or

publication I may write in the future, with attribution to you, unless

you state otherwise. Thanks, Cliff Pickover

* * *

Consider a 9x9 grid of beautiful crystal wineglasses. Throw 32 cherries

at the grid. A glass is considered occupied if it contains at least one

cherry. (With each throw a cherry goes into one of the glasses.) How

many different patterns of occupied glasses can you make? (A glass with

more than one cherry is considered the same as a glass with one cherry

in the pattern).

2. Same as above except that you place 8 cherries in glasses (x,y) and

then determine the other positions by placing cherries at (x,-y),

(-x,y), (-x,-y) leading to 32 cherries in the grid. Consider the array

of glasses centered at the origin. How many different patterns of

occupied glasses can you make? (A glass with more than one cherry is

considered the same as a glass with one cherry in the pattern).

3. Can your results be extrapolated to an NxN grid with M cherries

thrown at it for both problems?

pickover/pickover.15.s

In article <1992Oct30.173903.108937@watson.ibm.com> you write:

: Consider a 9x9 grid of beautiful crystal wineglasses. Throw 32 cherries

: at the grid. A glass is considered occupied if it contains at least one

: cherry. (With each throw a cherry goes into one of the glasses.) How

: many different patterns of occupied glasses can you make? (A glass with

: more than one cherry is considered the same as a glass with one cherry

: in the pattern).

Assuming that rotated patterns are allowed, then it is (simply)

sum( 81!/(81-n)! , n=1->32) . Since, if a total of n different classes are

filled, then the number of combinations is 81!/(81-n)!. Since there can

be from 1 to 32 glasses filled, the total # is just the sum of these...

:

: 2. Same as above except that you place 8 cherries in glasses (x,y) and

: then determine the other positions by placing cherries at (x,-y),

: (-x,y), (-x,-y) leading to 32 cherries in the grid. Consider the array

: of glasses centered at the origin. How many different patterns of

: occupied glasses can you make? (A glass with more than one cherry is

: considered the same as a glass with one cherry in the pattern).

This limitation basically reduces the number of available spots, from 9x9

to 5x5. Also, I only have to worry about 8 occupied spaces. Soo...

#of comb. = sum( (25!/(25-n)!, n=1->8)

:

: 3. Can your results be extrapolated to an NxN grid with M cherries

: thrown at it for both problems?

With a odd N, and M = 4k (evenly divs by 4), then

for 1....

#of comb = sum( (N^2)!/(N^2-n)! , n=1->M)

for 2....

#of comb = sum( (((N+1)/2)^2)!/(((N+1)/2)^2-n)! , n=1->M/4)

-- Michael Neylon aka Masem the Great and Almighty Thermodynamics GOD! // | Senior, Chemical Engineering, Univ. of Toledo \\ // Only the | Summer Intern, NASA Lewis Research Center \ \X/ AMIGA! | mneylon@jupiter.cse.utoledo.edu / --------+ How do YOU spell 'potato'? How 'bout 'lousy'? +---------- "Me and Spike are big Malcolm 10 supporters." - J.S.,P.L.C.L

Continue to: