From: bboru@lobby.ti.com (B. Borowicz)
Subject: Geometry Ratio


Begin with a unit circle.  Circumscribe a square about the circle.
Then circumscribe another circle about the square.  Circumscribe an
octagon about THIS circle, and a circle about the octagon... ad infinitum,
doubling the number of sides in the polygon for each iteration.
If this were carried on an infinite number of times, what would be 
the diameter of the final circle?

	Brian Borowicz
	bboru@lobby.ti.com


From: Van@cup.portal.com
Subject: First probability prob

 Re: First probability problem:
 1) You have two numbers that are different. You randomly give me one of them
which I look at. With no more information I can be certain of having a better
than 50% chance of telling correctly whether you gave me the larger. (Not much
better though...) How?
----------
 Posts from Paul and Steve on Genie: 
 One can't have better than a 50% chance.
 ===========================
 P.MIDDLER (Paul) on Genie
 ------
The solution is just a math trick that exploits the weaknesses of
probability calculations by going through an unusual route to find the
solution. Using a slightly different, but correct, route it can be proven that
the probability is exactly 1/2.
--------
 Definitions:

 "Known" is the number that is seen.
 "Unknown" is the number that is not seen.
 "x" and "y" are the actual numbers.
 "Random" is the random number.

 Solution:

 Since the other `solution' used this condition -> it is assumed that the
random number cannot be exactly the same as x or y.
 [ P (random = x) = 0  and P (random = y) = 0 ]

 P (making right decision)
               = P (random and unknown are on the same side of known)

               = P (random < known) * P (unknown < known)
                  + P (random > known) * P (unknown > known)

 The known number has a 50 percent chance of being the larger number and a 50
percent chance of being the smaller number, so the above equation can be
written as:

    = [ 1/2 * P (random < x) + 1/2 * P (random < y) ] * 1/2
      + [ 1/2 * P (random > x) + 1/2 * P (random > y) ] * 1/2

 If the above equation is rearranged:

    = 1/4 * [ P (random < x) + P (random > x) ]
      + 1/4 * [ P ( random < y ) + P (random > y) ]

 Since both P (random = x) and P (random = y) are zero:

    = 1/4 * 1 + 1/4 * 1 = 1/2

 So, the probability of making the correct decision, even with the `help' of a
random number, is exactly 50 percent.

                                                   ...Paul

 ------------
 Note: I put forth an argument that prob(random is in between) = 0 because of 
the infinite interval, which was shot down.
 ============
 S.CHASE7 [Steve]  on Genie
 
 Van:
    Although your analysis is OK, I strongly diagree that the
  flaw depends on x & y from an infinite range.  The trick is
  far more bogus than that.  Let us pick x=2, and y the 50-50
  random choice of 1 or 3.  No oo here.  The bogus method applies
  as well as it ever did, only now the trick is more exposed.
  (see below). Just as the
  1=2 proofs depend on the viewer not seeing the disguised /0.
 
  There are several other simlar bogus proofs in probability;
  i.e., the common flaw is reliance on "_I_ don't know which of
  2 values an event will take, therefore the probability is 0.5".
  So just as we experts know to look for "/0" in "1=2" proofs,
  we can look for "probablity of a biased-bit-valued event
  = 0.5" in these bogus methods.
 ===========
 S.CHASE7 [Steve]          on Genie
 
 Re: Latest "solution" to guessing larger of 2 numbers.
 The flaw in this one is more obvious (or maybe just becoming
 clear once I've seen two of them).  The bogus assumption is
 that for all (guesses) z such that z < x (the shown #) and
 z < y (the hidden #), P(x<y) is .5  This is trivial to rig
 to be false; but even if x and y are random, and say fix
 abs(x-y)=10, then if z=x-1, there is no chance that z<y and
 x>y.  Just because the guesser throws away the knowledge that
 this can't be does not restore the probablities to even-up.
 In this case, given z=x-1, it is 50-50 that x<y, but one
 can not count the case y<z once, and still add on .5 of the
 probability that z<y as if there were still a chance (let alone
 an even chance) that y<x.
 ------------


From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly)
Subject: Re: First probability prob

Again I am posting this because I feel that it is of general interest. There
is no problem with the first probability problem as stated. I challenge
anyone who thinks that there is to model it on a computer and see for
yourself that it works. The person that I heard it from, Laurie Snell, is a
noted probability theorist who specializes in strange results like this one
and has won more than one bet on it by having the doubters model it on a
computer. Now on to the flaws in the analysis given to show that it is false.
Paul's mistake is interesting. Note that P(random<x) depends on what x is. He
has in one formula P(random<x) and P(random>x) while P(random<x) happens only
if x>y and P(random>x) only happens if y>x. However x and y are assumed to be
specified numbers so only one of those cases can happen at a time. In essence
he is using terms thatare not well defined. Now if you take either of those
cases, x<y or y<x, and carry out the analysis you get that I have better than
even odds of being right. What is most amusing about this is that he starts
off with a high-handed statement that the solution that I gave is incorrect
and his is correct.

Steve Chase's solutions would be easier to criticize if he gave his argument.
However this "expert" is wrong on this one. There is no division by infinity
anywhere. But the problem with the argument that he gave was that there is no
relation between x,y, and z. Now again I challenge people to do this problem
out on a computer before you post things. It is an easy programming exercise
and you will find that I have better that even odds, and you can even
calculate how much better than even odds. As a matter of fact I ask that
others try it and post what they get. It is interesting to watch it work.
Also a good way to win bets with friends!

Ben Tilly


From: alanm@efi.com
Subject: Re: First probability prob

 
> Now again I challenge people to do this problem
> out on a computer before you post things. It is an easy programming exercise

No doubt.  I was one of the people who criticized your solution originally
although I am convinced now.  I am at a loss to know how to model this
problem accurately on a computer.  Any computer can only exactly represent
a finite (although large) subset of the real numbers.  Thus, by doing
it on a computer in the obvious fashion I have reduced the problem from
one dealing with infinite sets to one dealing with finite sets.  This
strikes me as being a fundamentally different problem and, assuming
I was not convinced you were right to begin with, would have no chance
of convincing me.  What am I missing?

> Ben Tilly

Alan



From: Android <benjie@quack.kfu.com>
Subject: P.O.D.


The base of a triangle is 21 cm. long.  Two lines are drawn parallel
to the base which separate triangle into three parts whose areas are
equal.  Find the length of the upper base of the lower tapezoid
formed.

Enjoy

Benjie


From: algebra@leland.stanford.edu
Subject: Re: POD


> > The base of a triangle is 21 cm. long.  Two lines are drawn parallel
> > to the base which separate triangle into three parts whose areas are
> > equal.  Find the length of the upper base of the lower tapezoid
> > formed.
> > 
> > Enjoy
> > 
> > Benjie
> >
> ** SPOILER ALERT **
>
 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> Let x be the length of the base (coincides with lower parallel line).
> Let A be the area of each division (1 small triangle and 2 trapeziums)
> 
> Area of whole triangle = 3A
> Area of triangle with base length x = 2A
> Notice that the latter triangle is similar to the former one.
> So by that familiar formula relating length ratios to area ratios 
> between similar geometrical figures (name??) we have,
> 
> (x/21)^2 = 2A/3A => x = Sqrt(294).
> 
> If anybody read this solution, please wish me a Happy Birthday; I just
> turned 21 today!
> 
> ****************************************************************************
> 
> Kelly's Reformation of Levy's Law: Nice guys don't finish nice.
> 
> Cohen's Law: People are divided into two groups -- the righteous and the
> 	     unrighteous -- and the righteous do the dividing.
> 
> Christie-Davies Theorem: If your facts are wrong but your logic is perfect,
> 			 then your conclusions are inevitably false.
> 			 Therefore, by making mistakes in your logic, you
> 			 have at least a random chance of coming to a
> 			 correct conclusion.
> 
> De Never's Law of Debate: Two monologues do not make a dialogue.
> 
> (Source: The Complete Murphy's Law -- A Definitive Collection) Only $6.95
> 
> Weng Leong
> Stanford U.
> 
> ***************************************************************************
> 

****************************************************************************

Kelly's Reformation of Levy's Law: Nice guys don't finish nice.

Cohen's Law: People are divided into two groups -- the righteous and the
	     unrighteous -- and the righteous do the dividing.

Christie-Davies Theorem: If your facts are wrong but your logic is perfect,
			 then your conclusions are inevitably false.
			 Therefore, by making mistakes in your logic, you
			 have at least a random chance of coming to a
			 correct conclusion.

De Never's Law of Debate: Two monologues do not make a dialogue.

(Source: The Complete Murphy's Law -- A Definitive Collection) Only $6.95

Weng Leong
Stanford U.

***************************************************************************


From: algebra@leland.stanford.edu
Subject: Re: Geometry Ratio

> 
> 
> Begin with a unit circle.  Circumscribe a square about the circle.
> Then circumscribe another circle about the square.  Circumscribe an
> octagon about THIS circle, and a circle about the octagon... ad infinitum,
> doubling the number of sides in the polygon for each iteration.
> If this were carried on an infinite number of times, what would be 
> the diameter of the final circle?
> 
> 	Brian Borowicz
> 	bboru@lobby.ti.com
> 

** SPOLIER ALERT **










































We merely have to observe the relationship between each 2^(n-1)-gon
and 2^n-gon. The key fact is that the distance from the center of the
circle to one vertex of the 2^(n-1)-gon is equal to the perp. distance
from the center to one side of the 2^n-gon. So if the vertex distance
of the 2^(n-1)-gon = x, then the vertex distance of the 2^n -gon is
limit of the infinite product sec(Pi/2^2) sec(Pi/2^3) ... ad infinitum,
whose value is Pi/2 by a standard identity due to Euler,

(sin x)/x = cos (x/2) cos (x/2^2) cos (x/2^3) ... ad infinitum.

For a non-rigorous derivation of this identity, take sin x and apply
the double angle formula for sine to get 2 sin(x/2) cos(x/2). Do the
same to sin (x/2) and so on. At the nth application you get 

sin x = 2^n [product of cosines] sin (x/2^n). 

But as n approaches infinity, sin (x/2^n) approaches x/2^n, so the 2^n's
cancel off to give the desired identity. 

****************************************************************************

Kelly's Reformation of Levy's Law: Nice guys don't finish nice.

Cohen's Law: People are divided into two groups -- the righteous and the
	     unrighteous -- and the righteous do the dividing.

Christie-Davies Theorem: If your facts are wrong but your logic is perfect,
			 then your conclusions are inevitably false.
			 Therefore, by making mistakes in your logic, you
			 have at least a random chance of coming to a
			 correct conclusion.

De Never's Law of Debate: Two monologues do not make a dialogue.

(Source: The Complete Murphy's Law -- A Definitive Collection) Only $6.95

Weng Leong
Stanford U.

***************************************************************************


From: "David W. Wilson" <wilson@web.ctron.com>
Subject: SPOILER: Geometry ratio



> Begin with a unit circle.  Circumscribe a square about the circle.
> Then circumscribe another circle about the square.  Circumscribe an
> octagon about THIS circle, and a circle about the octagon... ad infinitum,
> doubling the number of sides in the polygon for each iteration.
> If this were carried on an infinite number of times, what would be 
> the diameter of the final circle?
> 
> 	Brian Borowicz
> 	bboru@lobby.ti.com


    NITPICK ALERT:  There is no "final circle" as described.  Instead,
    the increasing diameters of the circles in question ostensibly
    approach some value.  We attack the problem from this standpoint.

    Let c_n be the circle inscribed within the n-gon (Thus, c4 is the
    unit circle inscribed within the square, c8 is the circle
    circumscribing the square and inscribing the octagon, etc.) We
    establish the following recursion for the diameter d_n of c_n,
    where n >= 4 is a power of 2:

	    d_4	= 2;  d_(2n) = d_n * sec(pi/(2^n)).

    Had we taken d_n to be the area of an n-gon inscribed within the
    unit circle, we would have arrived at the same recursion.  Hence
    d_n approaches pi, the area of the unit circle, as n increases. 




From: bboru@lobby.ti.com (B. Borowicz)
Subject: Series Puzzle: SPOILER


OK, don't twist my arm.  Here's the answers to the two series I posted last
week.  In case you forgot, they are:
 	1, 1, 0, 1, 0, 7, 28, 79, ...
and 
	5, 7, 11, 17, 29, 47, 83, ...

And now the solution which you have, no doubt, anticipated with bated breath...






















SPOILER HERE

The first one is just |2^n-n^2| for n = 0, 1, 2, 3, ...
It kinda goes
	1, 1, 0, 1, 0, 7, 28, 79, 192, 431, 924, ...

The second is a spinoff, 2^(n-1)+p(n)+2, where p(n) is the nth prime.
	1+2+2 = 5
	2+3+2 = 7
	4+5+2 = 11
...
	128+19+2 = 149
	256+23+2 = 281
	512+29+2 = 543

I thought if you noticed the 2^n trend it would come clear.  Well, I'll 
just go wade through Iowa now.

	:)rian :)orowicz
	bboru@lobby.ti.com


From: Android <benjie@quack.kfu.com>
Subject: Polynomial Problem


I made up the following problem couple of weeks ago, I tried to solve
it but didn't succeed.  I was wondering if there is a meaningful
solution.

----------------------Problem Follows--------------------

Assume you have a nth order polynomial in the form

	a_1 x^n + a_2 x^(n-1) + ...... + a_n x + a_(n+1) = P_n(x)        (A)

Now you take the derivative of this polynomial n-1 times, you get something
like

	a_1 (n!) x + a_2 (n-1)! = P_1(x)                                 (B)


(Problem 1) Now if you graph (A) and (B) on the same set of axis, what
would be the relationship between the intersection points and the
original curve (A) ?


I have found the following:

	If the original polynomial is a second degree polynomial, that
	is, let P_2(x) denote

		P_2(x) = a_1 (x^2) + a_2 x + a_3 		        (C)

	Then P_1(x) would be

		P_1(x) = 2(a_1)x + a_2					(D)

	Now if the curve of (C) intersects the axis twice, then the
	x-intercept of (D) would be (m+n)/2 where m and n are solutions
	of

		0 = a_1 (x^2) + a_2 x + a_3 			        (E)

	
	(Theorem 1)
	For (C) and (D), there is always an unique y such that the
	solution of

		y = 2(a_1)x + a_2					(F)

	is one half of the sum of the solutions of the following

		y = a_1 (x^2) + a_2 x + a_3 			        (G)


But that didn't solve the original problem (problem1) !  And what does
the above statement (theorem1) mean anyway?





From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly)
Subject: Another Probability Problem

Here is another strange probability problem. You are probably all familiar
with the problem that Marilyn Vos Savant popularized. The one where you have
three doors, behind one of which there is a prize. You pick one, the game
show host picks another and shows you that it does not have a prize behind
it. Now what is your chance of having the prize behind the door that you
picked? The interesting problem is that you actually do not really have
enough information to answer this! What more in the way of information is
needed?

Please send all flames to me and not to the list. :-) I will send out a
spoiler over the weekend. Incidentally, if anyone is interested, the answer
could be anything from 1/2 to 1/3. And yes, I am certain that this problem is
stated correctly.

Ben Tilly


From: Amit Sahai <amits@cory.EECS.Berkeley.EDU>
Subject: Yet another Combinatorics problem - a REAL one though



You are making a necklace, and you have 24 beads. 8 are green,
8 are red and 8 are blue. Taking into account all the symmetries
of the necklace, how many distinct arrangements of the 24 beads
on the necklace are possible? 

	Before posting your answer, make sure your method
works for a simpler case, say with 4 beads devided equally among
2 colors, which has only 2 arrangements. As far as I know,
this is NOT an easy problem.

Amit Sahai



From: benjie%wales@hip-hop.suvl.ca.us (Android)
Subject: 


From: Michael Somos <somos@alpha.ces.cwru.edu>
Subject: Somos(6) = Theta Series

14 July 1993 Cleveland, Ohio at Case Western Reserve University

             Somos(6) = Theta Series  (Preliminary Announcement)

Fix the following seven constants:

 c1 = 0.875782749065950194217251..., c2 = 1.084125925473763343779968...,
 c3 = 0.114986002186402203509006..., c4 = 0.077115634258697284328024...,
 c5 = 1.180397390176742642553759..., c6 = 1.508030831265086447098989..., and
 c7 = 2.551548771413081602906643... .  Consider the doubly indexed series:

                    +oo      +oo
                 x*y --    k2 --   k1*k1   k2*k2   k1*k2
 f(x,y) = c1 * c2  * > (-1) * >  c3    * c4    * c5     * cos(c6*k1*x+c7*k2*y)
                     --       --
                   k2=-oo   k1=-oo

The sequence  a(n) = f(n-2.5,n-2.5)  is the Somos(6) sequence of integers as
defined by  a(n) = ( a(n-1)a(n-5)+a(n-2)a(n-4)+a(n-3)a(n-3) )/a(n-6), and
initial values  a(0) = ... = a(5) = 1 .




From: benjie%wales@hip-hop.suvl.ca.us (Android)
Subject: Japan Math Olympiad


The 1993 Japan Math Olympiad was posted to sci.math in tex format.  I have
it here.

----------------cut, 93final.tex---------------
%\parindent=1zw
\nopagenumbers
\hsize=140true mm

% Plain TeX で AMS TeX のフォントを使うための宣言
¥font¥tenfrak=eufm10
¥font¥sevenfrak=eufm7
¥font¥fivefrak=eufm5
¥newfam¥frakfam ¥def¥frak{¥fam¥frakfam¥tenfrak} ¥textfont¥frakfam=¥tenfrak
   ¥scriptfont¥frakfam=¥sevenfrak ¥scriptscriptfont¥frakfam=¥fivefrak
¥font¥tenBbb=msbm10
¥font¥sevenBbb=msbm7
¥font¥fiveBbb=msbm5
¥newfam¥Bbbfam ¥def¥Bbb{¥fam¥Bbbfam¥tenBbb} ¥textfont¥Bbbfam=¥tenBbb
   ¥scriptfont¥Bbbfam=¥sevenBbb ¥scriptscriptfont¥Bbbfam=¥fiveBbb
¥font¥tenxm=msam10
¥font¥sevenxm=msam7
¥font¥fivexm=msam5
¥newfam¥xmfam ¥def¥xm{¥fam¥xmfam¥tenxm} ¥textfont¥xmfam=¥tenxm
   ¥scriptfont¥xmfam=¥sevenxm ¥scriptscriptfont¥xmfam=¥fivexm
¥font¥tenCal=eusb10
¥font¥sevenCal=eusb7
¥font¥fiveCal=eusb5
¥newfam¥Calfam ¥def¥Cal{¥fam¥Calfam¥tenCal} ¥textfont¥Calfam=¥tenCal
   ¥scriptfont¥Calfam=¥sevenCal ¥scriptscriptfont¥Calfam=¥fiveCal

% 不等号 ¥leqq, ¥geqq の宣言
¥catcode`¥@=11
¥def¥hexnumber@#1{¥ifcase#1 0¥or1¥or2¥or3¥or4¥or5¥or6¥or7¥or8¥or9¥or
 A¥or B¥or C¥or D¥or E¥or F¥fi}
¥edef¥xm@{¥hexnumber@¥xmfam}
¥edef¥ym@{¥hexnumber@¥Bbbfam}
¥mathchardef¥leqq="3¥xm@35
¥mathchardef¥geqq="3¥xm@3D
¥mathchardef¥subseteqq="3¥xm@6A
¥mathchardef¥supseteqq="3¥xm@6B
¥mathchardef¥subsetne="3¥ym@24
¥mathchardef¥supsetne="3¥ym@25
¥catcode`¥@=¥active

{¥bf The Final Round of Japan Math. Olympiad}
¥hfill 11 Feb. 1993 13:00---17:30

¥footnote{}{Copyright ¥copyright 1993
            by Mathematical Olympiad Foundation of Japan.}

¥medskip

¥noindent {¥bf 1.} 
Suppose that two words $A$ and $B$ have same length $n > 1$ and
the first letters of them are different and others are same.
Prove that $A$ or $B$ is not periodic.

¥medskip

¥noindent {¥bf 2.} 
Let $d(n)$ be the largest odd number which divides a given number $n$.
Suppose that $D(n)$ and $T(n)$ are defined by ¥par
¥hskip 10mm $D(n) = d(1)+d(2)+ ¥cdots +d(n)$ ¥par
¥hskip 10mm $T(n) = 1+2+ ¥cdots +n$ ¥par
¥noindent Prove that there exist infinitely many positive numbers $n$ 
such that $3D(n) = 2T(n)$.

¥medskip

¥noindent {¥bf 3.} 
In a contest, $x$ students took part and $y$ problems were posed. 
Each student solved $y/2$ problems. 
For every problem, the number of students who solve it was the same.  
For each pair of students, just three problems were solved by both of them. 
Determine all possible pair $(x,y)$'s.
Moreover for each $(x,y)$, give an example 
of the matrix $(a_{ij})$ defined by $a_{ij} = 1$ if $i$-th student solved 
the $j$-th problem and $a_{ij}=0$ if not.

¥medskip

¥noindent {¥bf 4.} 
Five radii of a sphere are given so that no three
of them are in a common
plane. Among 32 possible choices of 5 end points from each segments, 
find out the number of choices such that they are in a hemisphere.

¥medskip

¥noindent {¥bf 5.} 
Prove that there exists a positive constant $C$ (independent of $n$, $a_j$) 
which satisfies the inequality ¥par
¥hskip 15mm $¥displaystyle{¥max_{0 ¥leqq x ¥leqq 2} ¥prod_{j=1}^n
           {¥left¥vert x-a_j ¥right¥vert} ¥leqq C^n {¥max_{0 ¥leqq x
            ¥leqq 1} ¥prod_{j=1}^n {¥left¥vert x-a_j¥right¥vert}}}$ ¥par
for any positive integer n and any real numbers $a_1$,$¥dots$,$a_n$.

¥end

-------------------cut, 93first.tex---------------------
% Need include file ``macroc.h''
%
%
%¥parindent=1zw
¥nopagenumbers
¥hsize=140true mm
¥input macroc.h

{¥bf The First Round of Japan Math. Olympiad} 
¥hfill 9 Jan. 1993 13:00---16:00

¥footnote{}{Copyright ¥copyright 1993
            by Mathematical Olympiad Foundation of Japan.}

¥medskip

{¥bf 1.} 
Count out the number of positive integers $n < 120$
such that $n^2 ¥equiv 1$ modulo 120.

¥smallskip

{¥bf 2.} 
There is a parking lot in which 12 square are aligned. 
To park a truck we need two adjoining squares, 
and to park a car we need one.
We park six cars and two trucks with leaving two squares 
so that we can park one more truck.
Find out the number of such parking patterns.

¥smallskip

{¥bf 3.}
There is a regular tetrahedron with volume 1.
We divide this by the six perpendicular planes at midpoints of each edge.
Find out the volume of the minimum piece.

¥smallskip

{¥bf 4.}
Find the lattice point $(a,b)$ nearest to the origin such that
the triangle with the vertices
$(0,0)$, $(276,153)$, $(a,b)$ 
has the area less then 2, and that $a$ and $b$ are positive.

¥smallskip

{¥bf 5.}
Find the minimum value of 
${¥rm AP}+{¥rm BP}+{¥rm PQ}+{¥rm CQ}+{¥rm DQ}$
where P and Q are points in the unit square.

¥smallskip

{¥bf 6.}
Let $A$ be the set $¥{1,2,3,4,5,6,7¥}$.
Count out the number of mappings $f ¥colon A ¥to A$ 
satisfying the following conditions:

¥hskip 8mm (1) For each $j ¥in A$, 
there exists the unique $k ¥in A$ with $j=f(k)$ and $k ¥neq j$. ¥par
¥hskip 8mm (2) There exists a mapping $g ¥colon A ¥to A$ 
such that $f(j)=g(g(j))$ for every $j ¥in A$. ¥par


¥smallskip

{¥bf 7.}
A fair coin is tossed repeatedly until the difference of the numbers
of heads and tails comes to three. Count out the number of such
processes to become 6 heads and 3 tails after 9 tosses.


¥smallskip

{¥bf 8.}
Let
$$A = ¥{¥;(x,y,z) ¥; ¥mid ¥; 2xy ¥geqq z^2, ¥ 
         x + y ¥leqq 1, ¥ x ¥geqq 0, ¥ y ¥geqq 0¥;¥}, $$
and let
$$B = ¥{¥;(u,v,w) ¥; ¥mid ¥; 0 ¥leqq ux + vy + wz ¥leqq 1¥;
  ¥hbox{for all}¥; (x,y,z) ¥in A ¥;¥}.$$
Determine the volume of $B$.


¥smallskip

{¥bf 9.}
Let $S = ¥{1, 11, 31, 51, 71¥}$ and suppose $¥{a_n¥}$ be
a sequence of numbers satisfying the following conditions
(1),(2),(3):¥par
¥hskip 8mm (1) $a_1 ¥in S$,¥par
¥hskip 8mm (2) $¥displaystyle{{a_{n+1}-1 ¥over a_n +1} ¥in S}$, ¥par
¥hskip 8mm (3) There exists a positive number $n ¥leqq 10$ with $a_n = 1993$. 
¥par
¥noindent List up $a_4$ for all such sequences $¥{a_n¥}$.


¥smallskip

{¥bf 10.}
Determine the minimum denominator of the rationalization of
$¥displaystyle{1 ¥over 1 + {}^5¥sqrt{64} - {}^5¥sqrt{4}}$.

¥smallskip

{¥bf 11.}
Count out the number of one-path writings of the figure:

¥vskip 3mm

¥unitlength=1mm
¥hskip 15mm
¥hbox{
  ¥put(10,16.666){¥xline(1,0){60}}
  ¥put(70,16.666){¥xline(-3,-5){10}}
  ¥put(60,0){¥xline(-1,0){60}}
  ¥put(0,0){¥xline(3,5){10}}
  ¥put(10,16.666){¥xline(3,-5){10}}
  ¥put(20,0){¥xline(3,5){10}}
  ¥put(30,16.666){¥xline(3,-5){10}}
  ¥put(40,0){¥xline(3,5){10}}
  ¥put(50,16.666){¥xline(3,-5){10}}
}

¥smallskip

{¥bf 12.}
There are four different 3-digits numbers with the same top digits.
Three of them divides the sum of the four numbers.
Determine the four numbers.

¥end 
---------------------cut, macros.h----------------
¥font¥tencmss=cmss10
¥font¥tencmssi=cmssi10
% Plain TeX で AMS TeX のフォントを使うための宣言
¥font¥tenfrak=eufm10
¥font¥sevenfrak=eufm7
¥font¥fivefrak=eufm5
¥newfam¥frakfam ¥def¥frak{¥fam¥frakfam¥tenfrak} ¥textfont¥frakfam=¥tenfrak
   ¥scriptfont¥frakfam=¥sevenfrak ¥scriptscriptfont¥frakfam=¥fivefrak
¥font¥tenBbb=msbm10
¥font¥sevenBbb=msbm7
¥font¥fiveBbb=msbm5
¥newfam¥Bbbfam ¥def¥Bbb{¥fam¥Bbbfam¥tenBbb} ¥textfont¥Bbbfam=¥tenBbb
   ¥scriptfont¥Bbbfam=¥sevenBbb ¥scriptscriptfont¥Bbbfam=¥fiveBbb
¥font¥tenxm=msam10
¥font¥sevenxm=msam7
¥font¥fivexm=msam5
¥newfam¥xmfam ¥def¥xm{¥fam¥xmfam¥tenxm} ¥textfont¥xmfam=¥tenxm
   ¥scriptfont¥xmfam=¥sevenxm ¥scriptscriptfont¥xmfam=¥fivexm
¥font¥tenCal=eusb10
¥font¥sevenCal=eusb7
¥font¥fiveCal=eusb5
¥newfam¥Calfam ¥def¥Cal{¥fam¥Calfam¥tenCal} ¥textfont¥Calfam=¥tenCal
   ¥scriptfont¥Calfam=¥sevenCal ¥scriptscriptfont¥Calfam=¥fiveCal

% 不等号 ¥leqq, ¥geqq の宣言
¥catcode`¥@=11
¥def¥hexnumber@#1{¥ifcase#1 0¥or1¥or2¥or3¥or4¥or5¥or6¥or7¥or8¥or9¥or
 A¥or B¥or C¥or D¥or E¥or F¥fi}
¥edef¥xm@{¥hexnumber@¥xmfam}
¥edef¥ym@{¥hexnumber@¥Bbbfam}
¥mathchardef¥leqq="3¥xm@35
¥mathchardef¥geqq="3¥xm@3D
¥mathchardef¥subseteqq="3¥xm@6A
¥mathchardef¥supseteqq="3¥xm@6B
¥mathchardef¥subsetne="3¥ym@24
¥mathchardef¥supsetne="3¥ym@25
¥catcode`¥@=¥active

% Numerical equivalent (〜線三本) の定義
¥def¥threealign#1{¥mathchoice
  {¥lower1.5pt¥vbox{¥baselineskip0pt ¥lineskip-1.5pt¥ialign{$¥mathsurround=0pt 
   ¥displaystyle{¥hfill##¥hfill}$¥crcr#1¥crcr#1¥crcr#1¥crcr}}}
  {¥lower1.5pt¥vbox{¥baselineskip0pt ¥lineskip-1.5pt¥ialign{$¥mathsurround=0pt 
   ¥textstyle{¥hfill##¥hfill}$¥crcr#1¥crcr#1¥crcr#1¥crcr}}}
  {¥lower1pt¥vbox{¥baselineskip0pt ¥lineskip-1.05pt¥ialign{$¥mathsurround=0pt 
   ¥scriptstyle{¥hfill##¥hfill}$¥crcr#1¥crcr#1¥crcr#1¥crcr}}}
  {¥lower.7pt¥vbox{¥baselineskip0pt ¥lineskip-.75pt¥ialign{$¥mathsurround=0pt 
   ¥scriptscriptstyle{¥hfill##¥hfill}$¥crcr#1¥crcr#1¥crcr#1¥crcr}}}
}
¥def¥numeq{¥mathrel{¥threealign¥sim}}

% 見出しに使う文字の定義
¥font¥Bigrm=cmr10 scaled¥magstep3
¥font¥Bigmi=cmmi10 scaled¥magstep3
¥font¥Bigsy=cmsy10 scaled¥magstep3
¥font¥bigrm=cmr10 scaled¥magstep1
¥font¥bigcp=cmcsc10 scaled¥magstep1
¥font¥smallrm=cmr8
¥font¥smallmi=cmmi8
¥font¥smallsy=cmsy8
¥font¥smallcp=cmr5
¥font¥smallit=cmti8
¥def¥titlefont{¥textfont0=¥Bigrm ¥textfont1=¥Bigmi ¥textfont2=¥Bigsy ¥Bigrm}
¥def¥smallfont{¥textfont0=¥smallrm ¥textfont1=¥smallmi
               ¥textfont2=¥smallsy ¥smallrm}

% よく使う数学記号
¥def¥LRA{$¥Longrightarrow$}
¥def¥lto{¥longrightarrow}
¥def¥mdot{¥smash{¥mathop{¥cdot}¥limits}}
¥def¥restrict{¥mathord{¥hbox{$¥scriptstyle¥smash|$}}}
¥def¥Supp{¥mathop{¥rm Supp}¥nolimits}
¥def¥Spec{¥mathop{¥rm Spec}¥nolimits}
¥def¥Sat{¥mathop{¥rm Sat}¥nolimits}
¥def¥Ker{¥mathop{¥rm Ker}¥nolimits}
¥def¥Im{¥mathop{¥rm Im}¥nolimits}
¥def¥Bs{¥mathop{¥rm Bs}¥nolimits}
¥def¥rank{¥mathop{¥rm rank}¥nolimits}
¥def¥length{¥mathop{¥rm length}¥nolimits}
¥def¥sExt{¥mathop{{¥cal E}xt}¥nolimits}
¥def¥Ext{¥mathop{¥rm Ext}¥nolimits}
¥def¥sHom{¥mathop{{¥cal H}om}¥nolimits}
¥def¥Hom{¥mathop{¥rm Hom}¥nolimits}
¥def¥mod{¥mathop{¥rm mod}¥nolimits}
¥def¥ov{¥allowbreak / ¥allowbreak}
¥def¥Proof{{¥sl Proof.}¥quad}
¥def¥Z{{¥Bbb Z}}
¥def¥Q{{¥Bbb Q}}
¥def¥R{{¥Bbb R}}
¥def¥C{{¥Bbb C}}
¥def¥hH{{¥rm H}}
¥def¥Oc{{¥cal O}_C}
¥def¥Ox{{¥cal O}_X}
¥def¥QED{{¥unskip¥nobreak¥hfil¥penalty50¥quad¥null¥nobreak¥hfil
{¥sl q.e.d.}¥parfillskip0pt¥finalhyphendemerits0¥par¥medskip}}
¥def¥mapr#1{¥smash{¥mathop{¥longrightarrow}¥limits^{#1}}}
¥def¥maprdown#1{¥big¥downarrow¥rlap{$¥vcenter{¥hbox{$¥scriptstyle#1$}}$}}
¥def¥mapldown#1{¥llap{$¥vcenter{¥hbox{$¥scriptstyle#1$}}$}¥big¥downarrow}
¥def¥roundup#1{¥raise.3em¥hbox{$¥scriptstyle¥lceil$}#1¥raise.3em¥hbox{$¥scriptstyle¥rceil$}}


%----------------- 斜めの線分と矢印を書くマクロ -----------------+
%                                                                |
% 使い方                                                         |
%   ¥unitlength=1mm   単位の設定                                 |
%   ¥hbox{¥put(col,-lin){¥xline(dx,-dy){length}}}                |
%        (col,lin) から傾き (dy/dx), 長さ length の線分を書く    |
%   例: ¥hbox{¥put(10,26){¥xline(1,1){20}}}                      |
%                                                                |
%   ¥hbox{¥put(col,-lin){¥vector(dx,-dy){length}}}               |
%        (col,lin) から傾き (dy/dx), 長さ length の矢印を書く    |
%   例: ¥hbox{¥put(20,30){¥vector(1,-2){40}}}                    |
%                                                                |
%----------------------------------------------------------------+

¥font¥tenln    = line10
¥font¥tenlnw   = linew10  
% ¥font¥tencirc  = lcirle10 % PAM, in the interests of name consistency
% ¥font¥tencircw = lcirew10 % This is circle*10 renamed.  No changes

¥catcode`¥@=11

¥newcount¥@tempcnta    % 1483 (LATEX.TEX での行番号)
¥newcount¥@tempcntb    % 1483
¥newdimen¥@tempdima    % 1488
¥newdimen¥@tempdimb    % 1489
¥newbox¥@tempboxa      % 1490

¥newdimen¥@wholewidth  % 4831
¥newdimen¥@halfwidth   % 4832
¥newdimen¥unitlength ¥unitlength =1pt
¥newbox¥@picbox        % 4834
¥newdimen¥@picht       % 4835

¥newcount¥@xarg        % 5555
¥newcount¥@yarg        % 5556
¥newcount¥@yyarg
¥newcount¥@multicnt 
¥newdimen¥@xdim
¥newdimen¥@ydim
¥newbox¥@linechar
¥newdimen¥@linelen
¥newdimen¥@clnwd
¥newdimen¥@clnht
¥newdimen¥@dashdim
¥newbox¥@dashbox
¥newcount¥@dashcnt     % 5567
¥newdimen¥z@ ¥z@=0pt   % can be used both for 0pt and 0

¥newif¥if@negarg     % 5050

¥def¥@height{height}   % 1433
¥def¥@depth{depth}     % 1434
¥def¥@width{width}     % 1435

% ¥def¥@badlinearg{¥@latexerr{Bad ¥string¥line¥space or ¥string¥vector
%   ¥space argument}¥@ehb}
¥def¥@badlinearg{}

% ¥def¥picture(#1,#2){¥@ifnextchar({¥@picture(#1,#2)}{¥@picture(#1,#2)(0,0)}}
%
% ¥def¥@picture(#1,#2)(#3,#4){
%   ¥@picht #2¥unitlength
%   ¥setbox¥@picbox¥hbox to #1¥unitlength¥bgroup 
%   ¥hskip -#3¥unitlength ¥lower #4¥unitlength ¥hbox¥bgroup
% }
%
% ¥def¥endpicture{
%   ¥egroup¥hss¥egroup¥ht¥@picbox¥@picht
%   ¥dp¥@picbox¥z@¥leavevmode¥box¥@picbox
% }

¥long¥def¥put(#1,#2)#3{%
  ¥@killglue¥raise#2¥unitlength¥hbox to ¥z@{¥kern%
  #1¥unitlength #3¥hss}¥ignorespaces%
}

¥def¥@killglue{¥unskip¥@whiledim ¥lastskip >¥z@¥do{¥unskip}}

¥def¥thinlines{¥let¥@linefnt¥tenln ¥let¥@circlefnt¥tencirc
  ¥@wholewidth¥fontdimen8¥tenln ¥@halfwidth .5¥@wholewidth}
¥def¥thicklines{¥let¥@linefnt¥tenlnw ¥let¥@circlefnt¥tencircw
  ¥@wholewidth¥fontdimen8¥tenlnw ¥@halfwidth .5¥@wholewidth}

¥def¥@whilenoop#1{}
% ¥def¥@whilenum#1¥do #2{¥ifnum #1¥relax #2¥relax¥@iwhilenum{#1¥relax 
%      #2¥relax}¥fi}
% ¥def¥@iwhilenum#1{¥ifnum #1¥let¥@nextwhile=¥@iwhilenum 
%          ¥else¥let¥@nextwhile=¥@whilenoop¥fi¥@nextwhile{#1}}
¥def¥@whiledim#1¥do #2{¥ifdim #1¥relax#2¥@iwhiledim{#1¥relax#2}¥fi}
¥def¥@iwhiledim#1{¥ifdim #1¥let¥@nextwhile=¥@iwhiledim 
        ¥else¥let¥@nextwhile=¥@whilenoop¥fi¥@nextwhile{#1}}


¥def¥xline(#1,#2)#3{¥@xarg #1¥relax ¥@yarg #2¥relax%
  ¥@linelen=#3¥unitlength%
  ¥ifnum¥@xarg =0 ¥@vline%
    ¥else ¥ifnum¥@yarg =0 ¥@hline ¥else ¥@sline¥fi%
  ¥fi%
}

¥def¥@sline{%
  ¥ifnum¥@xarg< 0 ¥@negargtrue ¥@xarg -¥@xarg ¥@yyarg -¥@yarg%
  ¥else ¥@negargfalse ¥@yyarg ¥@yarg ¥fi%
  ¥ifnum ¥@yyarg >0 ¥@tempcnta¥@yyarg ¥else ¥@tempcnta -¥@yyarg ¥fi%
  ¥ifnum¥@tempcnta>6 ¥@badlinearg¥@tempcnta0 ¥fi%
  ¥ifnum¥@xarg>6 ¥@badlinearg¥@xarg 1 ¥fi%
  ¥setbox¥@linechar¥hbox{¥@linefnt¥@getlinechar(¥@xarg,¥@yyarg)}%
  ¥ifnum ¥@yarg >0 ¥let¥@upordown¥raise ¥@clnht¥z@%
  ¥else¥let¥@upordown¥lower ¥@clnht ¥ht¥@linechar¥fi%
  ¥@clnwd=¥wd¥@linechar%
  ¥if@negarg ¥hskip -¥wd¥@linechar ¥def¥@tempa{¥hskip -2¥wd¥@linechar}¥else%
     ¥let¥@tempa¥relax ¥fi%
  ¥@whiledim ¥@clnwd <¥@linelen ¥do%
    {¥@upordown¥@clnht¥copy¥@linechar%
     ¥@tempa%
     ¥advance¥@clnht ¥ht¥@linechar%
     ¥advance¥@clnwd ¥wd¥@linechar}%
  ¥advance¥@clnht -¥ht¥@linechar%
  ¥advance¥@clnwd -¥wd¥@linechar%
  ¥@tempdima¥@linelen¥advance¥@tempdima -¥@clnwd%
  ¥@tempdimb¥@tempdima¥advance¥@tempdimb -¥wd¥@linechar%
  ¥if@negarg ¥hskip -¥@tempdimb ¥else ¥hskip ¥@tempdimb ¥fi%
  ¥multiply¥@tempdima ¥@m%
  ¥@tempcnta ¥@tempdima ¥@tempdima ¥wd¥@linechar ¥divide¥@tempcnta ¥@tempdima%
  ¥@tempdima ¥ht¥@linechar ¥multiply¥@tempdima ¥@tempcnta%
  ¥divide¥@tempdima ¥@m%
  ¥advance¥@clnht ¥@tempdima%
  ¥ifdim ¥@linelen <¥wd¥@linechar%
    ¥hskip ¥wd¥@linechar%
    ¥else¥@upordown¥@clnht¥copy¥@linechar¥fi%
}

¥def¥@hline{%
  ¥ifnum ¥@xarg <0 ¥hskip -¥@linelen ¥fi%
  ¥vrule ¥@height ¥@halfwidth ¥@depth ¥@halfwidth ¥@width ¥@linelen%
  ¥ifnum ¥@xarg <0 ¥hskip -¥@linelen ¥fi%
}

¥def¥@getlinechar(#1,#2){
   ¥@tempcnta#1¥relax¥multiply¥@tempcnta 8
   ¥advance¥@tempcnta -9 ¥ifnum #2>0 ¥advance¥@tempcnta #2¥relax¥else
   ¥advance¥@tempcnta -#2¥relax¥advance¥@tempcnta 64 ¥fi
   ¥char¥@tempcnta
}

¥def¥@vline{¥ifnum ¥@yarg <0 ¥@downline ¥else ¥@upline¥fi}

¥def¥@upline{¥hbox to ¥z@{¥hskip -¥@halfwidth ¥vrule ¥@width ¥@wholewidth
   ¥@height ¥@linelen ¥@depth ¥z@¥hss}}

¥def¥@downline{¥hbox to ¥z@{¥hskip -¥@halfwidth ¥vrule ¥@width ¥@wholewidth
   ¥@height ¥z@ ¥@depth ¥@linelen ¥hss}}

¥def¥@upvector{¥@upline¥setbox¥@tempboxa¥hbox{¥@linefnt¥char'66}¥raise 
     ¥@linelen ¥hbox to¥z@{¥lower ¥ht¥@tempboxa¥box¥@tempboxa¥hss}}

¥def¥@downvector{¥@downline¥lower ¥@linelen
      ¥hbox to ¥z@{¥@linefnt¥char'77¥hss}}



¥def¥vector(#1,#2)#3{%
  ¥@xarg #1¥relax ¥@yarg #2¥relax%
  ¥@tempcnta ¥ifnum¥@xarg<0 -¥@xarg¥else¥@xarg¥fi%
  ¥ifnum¥@tempcnta<5¥relax%
  ¥@linelen=#3¥unitlength%
  ¥ifnum¥@xarg =0 ¥@vvector%
    ¥else ¥ifnum¥@yarg =0 ¥@hvector ¥else ¥@svector¥fi%
  ¥fi%
  ¥else¥@badlinearg¥fi%
}

¥def¥@hvector{¥@hline¥hbox to 0pt{¥@linefnt%
¥ifnum ¥@xarg <0 ¥@getlarrow(1,0)¥hss¥else%
    ¥hss¥@getrarrow(1,0)¥fi}}%

¥def¥@vvector{¥ifnum ¥@yarg <0 ¥@downvector ¥else ¥@upvector ¥fi}

¥def¥@svector{%
  ¥@sline%
  ¥@tempcnta¥@yarg ¥ifnum¥@tempcnta <0 ¥@tempcnta=-¥@tempcnta¥fi%
  ¥ifnum¥@tempcnta <5%
    ¥hskip -¥wd¥@linechar%
    ¥@upordown¥@clnht ¥hbox{¥@linefnt  ¥if@negarg%
    ¥@getlarrow(¥@xarg,¥@yyarg) ¥else ¥@getrarrow(¥@xarg,¥@yyarg) ¥fi}%
  ¥else¥@badlinearg¥fi%
}

¥def¥@getlarrow(#1,#2){
  ¥ifnum #2 =¥z@ ¥@tempcnta='33¥else
  ¥@tempcnta=#1¥relax¥multiply¥@tempcnta ¥sixt@@n ¥advance¥@tempcnta
  -9 ¥@tempcntb=#2¥relax¥multiply¥@tempcntb ¥tw@
  ¥ifnum ¥@tempcntb >0 ¥advance¥@tempcnta ¥@tempcntb¥relax
  ¥else¥advance¥@tempcnta -¥@tempcntb¥advance¥@tempcnta 64
  ¥fi¥fi¥char¥@tempcnta
}

¥def¥@getrarrow(#1,#2){
  ¥@tempcntb=#2¥relax
  ¥ifnum¥@tempcntb < 0 ¥@tempcntb=-¥@tempcntb¥relax¥fi
  ¥ifcase ¥@tempcntb¥relax ¥@tempcnta='55 ¥or 
  ¥ifnum #1<3 ¥@tempcnta=#1¥relax¥multiply¥@tempcnta
  24 ¥advance¥@tempcnta -6 ¥else ¥ifnum #1=3 ¥@tempcnta=49
  ¥else¥@tempcnta=58 ¥fi¥fi¥or 
  ¥ifnum #1<3 ¥@tempcnta=#1¥relax¥multiply¥@tempcnta
  24 ¥advance¥@tempcnta -3 ¥else ¥@tempcnta=51¥fi¥or 
  ¥@tempcnta=#1¥relax¥multiply¥@tempcnta
  ¥sixt@@n ¥advance¥@tempcnta -¥tw@ ¥else
  ¥@tempcnta=#1¥relax¥multiply¥@tempcnta
  ¥sixt@@n ¥advance¥@tempcnta 7 ¥fi¥ifnum #2<0 ¥advance¥@tempcnta 64 ¥fi
  ¥char¥@tempcnta
}

%--------------- 斜めの線分と矢印を書くマクロ 終り -----------------

%---------------------------- 円を描くマクロ --------------------------------

¥def¥@getcirc#1{¥@tempdima #1¥relax ¥advance¥@tempdima 2pt¥relax
  ¥@tempcnta¥@tempdima
  ¥@tempdima 4pt¥relax ¥divide¥@tempcnta¥@tempdima
  ¥ifnum ¥@tempcnta > 10¥relax ¥@tempcnta 10¥relax¥fi
  ¥ifnum ¥@tempcnta >¥z@ ¥advance¥@tempcnta¥m@ne
    ¥else ¥@warning{Oval too small}¥fi
  ¥multiply¥@tempcnta 4¥relax
  ¥setbox ¥@tempboxa ¥hbox{¥@circlefnt
  ¥char ¥@tempcnta}¥@tempdima ¥wd ¥@tempboxa%
}

¥def¥@put#1#2#3{¥raise #2¥hbox to ¥z@{¥hskip #1#3¥hss}}

¥def¥oval(#1,#2){¥@ifnextchar[{¥@oval(#1,#2)}{¥@oval(#1,#2)[]}}

¥def¥@oval(#1,#2)[#3]{¥begingroup¥boxmaxdepth ¥maxdimen
  ¥@ovttrue ¥@ovbtrue ¥@ovltrue ¥@ovrtrue
  ¥@tfor¥@tempa :=#3¥do{¥csname @ov¥@tempa false¥endcsname}¥@ovxx
  #1¥unitlength ¥@ovyy #2¥unitlength
  ¥@tempdimb ¥ifdim ¥@ovyy >¥@ovxx ¥@ovxx¥else ¥@ovyy ¥fi
  ¥@getcirc ¥@tempdimb
  ¥@ovro ¥ht¥@tempboxa ¥@ovri ¥dp¥@tempboxa
  ¥@ovdx¥@ovxx ¥advance¥@ovdx -¥@tempdima ¥divide¥@ovdx ¥tw@
  ¥@ovdy¥@ovyy ¥advance¥@ovdy -¥@tempdima ¥divide¥@ovdy ¥tw@
  ¥@circlefnt ¥setbox¥@tempboxa
  ¥hbox{¥if@ovr ¥@ovvert32¥kern -¥@tempdima ¥fi
  ¥if@ovl ¥kern ¥@ovxx ¥@ovvert01¥kern -¥@tempdima ¥kern -¥@ovxx ¥fi
  ¥if@ovt ¥@ovhorz ¥kern -¥@ovxx ¥fi
  ¥if@ovb ¥raise ¥@ovyy ¥@ovhorz ¥fi}¥advance¥@ovdx¥@ovro
  ¥advance¥@ovdy¥@ovro ¥ht¥@tempboxa¥z@ ¥dp¥@tempboxa¥z@
  ¥@put{-¥@ovdx}{-¥@ovdy}{¥box¥@tempboxa}%
  ¥endgroup}

¥def¥@ovvert#1#2{¥vbox to ¥@ovyy{%
    ¥if@ovb ¥@tempcntb ¥@tempcnta ¥advance ¥@tempcntb by #1¥relax
      ¥kern -¥@ovro ¥hbox{¥char ¥@tempcntb}¥nointerlineskip
    ¥else ¥kern ¥@ovri ¥kern ¥@ovdy ¥fi
    ¥leaders¥vrule width ¥@wholewidth¥vfil ¥nointerlineskip
    ¥if@ovt ¥@tempcntb ¥@tempcnta ¥advance ¥@tempcntb by #2¥relax
      ¥hbox{¥char ¥@tempcntb}%
    ¥else ¥kern ¥@ovdy ¥kern ¥@ovro ¥fi}}

¥def¥@ovhorz{¥hbox to ¥@ovxx{¥kern ¥@ovro
    ¥if@ovr ¥else ¥kern ¥@ovdx ¥fi
    ¥leaders ¥hrule height ¥@wholewidth ¥hfil
    ¥if@ovl ¥else ¥kern ¥@ovdx ¥fi
    ¥kern ¥@ovri}}

¥def¥@ifnch{¥ifx ¥@tempc ¥@sptoken ¥let¥@tempd¥@xifnch
      ¥else ¥ifx ¥@tempc ¥@tempe¥let¥@tempd¥@tempa¥else¥let¥@tempd¥@tempb¥fi
      ¥fi ¥@tempd}
¥def¥@ifnextchar#1#2#3{¥let¥@tempe #1¥def¥@tempa{#2}¥def¥@tempb{#3}¥futurelet
    ¥@tempc¥@ifnch}
¥def¥@ifstar#1#2{¥@ifnextchar *{¥def¥@tempa*{#1}¥@tempa}{#2}}
¥def¥circle{¥@ifstar{¥@dot}{¥@circle}}
¥def¥@circle#1{¥begingroup ¥boxmaxdepth ¥maxdimen ¥@tempdimb #1¥unitlength
   ¥ifdim ¥@tempdimb >15.5pt¥relax ¥@getcirc¥@tempdimb
      ¥@ovro¥ht¥@tempboxa 
     ¥setbox¥@tempboxa¥hbox{¥@circlefnt
      ¥advance¥@tempcnta¥tw@ ¥char ¥@tempcnta
      ¥advance¥@tempcnta¥m@ne ¥char ¥@tempcnta ¥kern -2¥@tempdima
      ¥advance¥@tempcnta¥tw@
      ¥raise ¥@tempdima ¥hbox{¥char¥@tempcnta}¥raise ¥@tempdima
        ¥box¥@tempboxa}¥ht¥@tempboxa¥z@ ¥dp¥@tempboxa¥z@
      ¥@put{-¥@ovro}{-¥@ovro}{¥box¥@tempboxa}%
   ¥else  ¥@circ¥@tempdimb{96}¥fi¥endgroup}

¥def¥@dot#1{¥@tempdimb #1¥unitlength ¥@circ¥@tempdimb{112}}

¥def¥@circ#1#2{¥@tempdima #1¥relax ¥advance¥@tempdima .5pt¥relax
   ¥@tempcnta¥@tempdima ¥@tempdima 1pt¥relax
   ¥divide¥@tempcnta¥@tempdima 
   ¥ifnum¥@tempcnta > 15¥relax ¥@tempcnta 15¥relax ¥fi    
   ¥ifnum ¥@tempcnta >¥z@ ¥advance¥@tempcnta¥m@ne¥fi
   ¥advance¥@tempcnta #2¥relax
   ¥@circlefnt ¥char¥@tempcnta%
}

¥catcode`¥@=¥active

¥thinlines   %INITIALIZATION


------------------------------cut-------------------------------

You need amstex to compile it.
Benjie


From: ramana@mgv01.svl.cdc.com
Subject: Puzzle


Partition numbers 1,2,3,...,16 into two equal groups A and B, such that

  i) sum of numbers in A = sum of numbers in B
 ii) sum of squares of numbers in A = sum of squares of numbers in B
iii) sum of cubes of numbers in A = sum of cubes of numbers in B


--- ramana@svl.cdc.com ---


From: Android <benjie@quack.kfu.com>
Subject: Problem 7 Contest 2



Problem 7
Part 1

Factor x^4 + 64 as the product of two polynomials with real coefficients.
Calculators are not allowed, therefore you must send in your work as well.
You don't have to write a lot, just the basic steps.

Part 2

Let a and b be odd integers with a>b>0.  Find the largest integer
which divides all possible numbers of the form a^2 - b^2.


Solutions are due next Friday.  This is the next to last round.

Enjoy and happy mathing,

Benjie


From: Android <benjie@quack.kfu.com>
Subject: Solutions to problem 6 contest 2, SPOILER



Problem 6
Part 1:
Given the conic curve in the x-y plane described by the equation 
	3x^2 + 2xy + 3y^2 = 32
find its vertices.

Part 2:
Find the constant c such that the line joining A(0,3) and B(5,2) is 
tangent to the curve y = c/(x+1).

--------------------------
Solutions:
Part 1

The equation is 3x^2 + 2xy + 3y^2 = 32, which includes a xy-term.  If we
rotate the axis, we could get rid of the xy-term so that we would have
a simple equation.  To determine the angle of rotation, we use the formula

		cot(2theta) = (A-C)/B 

where 	
		Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0

Therefore, we have

		cot(2theta) = 0
		cos(2theta) = 0
		2theta = pi/2
		theta = pi/4

Therefore we will rotate our axis by 45 degree.

		x = x'cos45 - y'sin45
		y = x'sin45 + y'cos45

Sub those into original equation, we get

		4x^2 + 2y^2 = 32
		x^2/8 + y^2/16 = 1

The above equation is an ellipse with major sqrt(16) and minor
sqrt(8).  So the x,y coordinates for the intersection points of the
ellipse with the new axis are (+-4*cos45, -+4sin45) and
(+-2sqrt(2)cos45, +-2sqrt(2)sin45), which are (2sqrt(2), -2sqrt(2)),
(-2sqrt(2), 2sqrt(2)), (-2,-2) and (2,2).  Therefore the vertices are

      (2sqrt(2), -2sqrt(2)), (-2sqrt(2), 2sqrt(2)), (-2,-2) and (2,2)

Another solution, a simpler one, was submitted by David Radcliffe and
some others.  


	This equation is unchanged if you switch x and y.  Therefore,
	the line y=x is an axis of symmetry.

	Rewrite the equation as a(x+y)^2 + b(x-y)^2 = 32.  Solve for a
	and b.  The equation is now 2(x+y)^2 + (x-y)^2 = 32.

	The vertices lie on the lines y = x and y = -x.  Solving these
	equations gives the points (2,2), (-2,-2), (2sqrt(2),-2sqrt(2),
	and (-2sqrt(2),2sqrt(2)).


Part 2
The equation of the line joining A(0,3) and B(5,2) is

		y = (15-x)/5

from the point-slope form.  This line intersects the curve

		y = c/(x+1)

exactly once.  So we need to solve the equation 

		(15-x)/5 = c/(x+1)
		(15-x)(x+1) = 5c
		15x+15-x^2-x = 5c
		14x - x^2 + 15 = 5c
		-x^2 + 14x + 15 - 5c = 0

But this equation could only have one solution (tangent).  Therefore, 

		-x^2 + 14x + 15 - 5c 

has to be a perfect square.  So

		c = 64/5

---------------------------------
Correct solutions were sent in by 

radcliff@csd4.csd.uwm.edu
martino@rob.csata.it
bboru@lobby.ti.com


Congrats

Benjie


From: Android <benjie@quack.kfu.com>
Subject: more on FLT


From: demarr@math.unm.edu (Ralph DeMarr)
Subject: FLT for matrices

The question has been raised as to whether the classical Fermat equation is 
valid for square matrices with all entries being strictly positive integers.
The answer is "yes" and there are infinitely many solutions as long as we
allow the exponent "n" in the Fermat equation to be the same as the order of
matrices involved. The idea is very simple and I will illustrate only for
exponent n=3 and matrices of size (=order) 3. MATLAB notation will be used.

Define  T=[0 0 2;1 0 0;0 1 0] and note that T^3 = 2*I, where I=identity matrix.

Next put A = T + T^2 + T^3 and note that every entry of A is a strictly 
 
positive integer. Then put B = A and C = A*T and note that A and T commute.

It is easy to verify that A^3 + B^3 = C^3.

We could just as well begin by defining A = 5*T + 2*T^2 + 7*T^3 + 9*I (as an
 example) and then put B=A and C=A*T. MATLAB does the work to verify that 

A^3 + B^3 = C^3.

For exponent n=4 and matrices of order 4 we can define T=[0 0 0 2;1 0 0 0;

0 1 0 0;0 0 1 0] and note that T^4 = 2*I. Simply repeat the above.

In these examples the order of the matrices is the same as the exponent in
the Fermat equation. But this now leads to a new type problem in which we ask,
for example, if we can have A^4 + B^4 = C^4 for matrices of order 3.

I actually have the solution but I don't have enough room in the margin of my
notebook to write it down.

This message of inspiration has been brought to you by:

Professor Ralph DeMarr
Department of Mathematics
University of New Mexico
Albuquerque, NM 87131

e-mail:  demarr@math.unm.edu



From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Solution to Amit Sahai's necklace problem

> You are making a necklace, and you have 24 beads. 8 are green,
> 8 are red and 8 are blue. Taking into account all the symmetries
> of the necklace, how many distinct arrangements of the 24 beads
> on the necklace are possible? 

I calculate that there are 197,216,213 arrangements.
My solution uses group theory, and is quite sketchy. 
It is also quite likely to be wrong.  Anyway, my solution follows...

Let G be the group of symmetries of the necklace.  G has 48
elements; 24 rotations and 24 reflections.

Number the positions of the necklace from 0 to 23.  Write G as
{a_i, b_i : 0 <= i <= 23}, where a_i(n) = n + i (mod 24) and 
b_i(n) = -n + i (mod 24).

The group of symmetries for any particular arrangement must be
a subgroup of G.  G has 68 subgroups, but "only" 46 of them are
the symmetry group of an arrangement of the beads on the necklace.
These subgroups are:
  (1)  <a_3>
  (2)  <a_6, b_i> , i=0..5 
  (3)  <a_6>
  (4)  <a_12,b_i> , i=0..11
  (5)  <a_12>
  (6)  <b_i> , i=0..23
  (7)  {1}  (the trivial subgroup)

For each subgroup H, we count the number of permutations which have
H as their group of symmetries.

(1) <a_3>              6 permutations.
(2) <a_6,b_i>         36 permutations, 6 each.
(3) <a_6>             48 permutations.  (6!/(2!2!2!) - 36 - 6) 
(4) <a_12,b_i>      1008 permutations, 84 each.
                         (6!/(2!2!2!) - 6)
(5) <a_12>         33552 permutations.
                         (12!/(4!4!4!) - 1008 - 48 - 36 - 6)
(6) <b_i>         829440 permutations, 34560 each.
                         (12!/(4!4!4!) - 84 - 6)
(7) {1}       9464647680 permutations.
                         (24!/(8!8!8!) - 829440 - 33552 - 1008 - 48 - 36 - 6).

We count the number of distinct arrangements as follows:  For each
subgroup H of G, let P(H) = the number of permutations whose symmetry
group is H.  Then the number of distinct arrangements is the sum
of P(H)/[G:H] as H runs over all subgroups of G.

This formula yields:

        (6+36)/6 + (48+1008)/12 + (33552+829440)/24 + (9464647680)/48
     =  197,216,213 .



From: greg@math.uchicago.edu (Greg Kuperberg)
Subject: Plane geometry problem.

Here's a plane geometry problem that merits a careful argument:

An isometry of the plane is defined to be a function f:R^2 -> R^2
such that d(x,y) = d(f(x),f(y)) for all x and y.  Here d(x,y)
is the distance from x to y, defined by d((x1,x2),(y1,y2))
= sqrt((x1-y1)^2 + (x2-y2)^2).

Show that an isometry of the plane is the composition of 0,1,2, or 3
reflections through lines.

			Greg


From: t-davidw@microsoft.com
Subject: Re: Japan Math Olympiad *SPOILER*


Some spoilers and many questions follow!


>
> Suppose that two words $A$ and $B$ have same length $n > 1$ and
> the first letters of them are different and others are same.
> Prove that $A$ or $B$ is not periodic.
>

        Can anyone tell me what it means for a word to be "periodic"?

>
> In a contest, $x$ students took part and $y$ problems were posed.
> Each student solved $y/2$ problems.
> For every problem, the number of students who solve it was the same.
> For each pair of students, just three problems were solved by both of
them.
> Determine all possible pair $(x,y)$'s.
> Moreover for each $(x,y)$, give an example
> of the matrix $(a_{ij})$ defined by $a_{ij} = 1$ if $i$-th student solved
> the $j$-th problem and $a_{ij}=0$ if not.
>

     Denote the ith row of the matrix A by r_i.  Let e=(1,1,...,1) be
an element of R^y.  Using the normal inner product on R^y, note that:

[a]  (r_i, e) = y/2      for all 1<=i<=x
[b]  (r_i, r_i) = y/2    for all 1<=i<=x
[c]  (r_i, r_j) = 3      for all 1<=i<j<=x
[d]  r_1 + ... + r_x = (x/2) e

     Now take the inner product of [d] with r_1.  We get

(r_1, r_1) + (r_1, r_2) + ... + (r_1, r_x) = (x/2) (r_1, e)
y/2 + 3 + ... + 3 = (x/2) (y/2)
2y + 12(x-1) = xy
x = 2(y-6)/(y-12)

     So the only possibility is x=8, y=14.  One possible matrix is

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

     I'm not sure if there are any other possibilities.

>
> Five radii of a sphere are given so that no three
> of them are in a common
> plane. Among 32 possible choices of 5 end points from each segments,
> find out the number of choices such that they are in a hemisphere.
>

        How about 15?  I'm probably screwing this up, because I'm
absolutely horrible at anything involving visualizing 3-D objects,
but I'll outline my argument and you can tell me where I went awry.
:-) (by the way I assume that the question intended to stipulate
that 5 diameters, rather than radii, of the sphere were given;
otherwise, the problem seems a little silly.)

        Imagine having your 5 diameters all be "real close" to the
north pole-south pole axis.  For ease of argument, I'll pretend the
endpoints on the northern hemisphere are arranged in a pentagon on
the surface of the sphere.  For each diameter we can choose either
the endpoint closer to the north pole, or the endpoint closer to
the south pole.  For each endpoint near the north pole, if we pick
it, color it red, otherwise color it green.

     Now imagine a pentagon on a piece of paper, and think about
coloring  the vertices red or green.  There are 32 configurations.
Now call a configuration "magic" if you can draw a straight line on
the piece of paper so that all the points on one side of the line
are red, and all the points on the other side are green.  (The line
may not intersect any of the vertices.)  So the following arrangement
of points on the pentagon would be "magic": RRRRR, RRRRG, RRGGR,
etc.  But RGRGR would _not_ be magic.

     The number of "magic" colorations of a pentagon is 5+4+3+2+1.
But this corresponds exactly to the problem listed above!  So the
number of choices that satisfy the requirements of this problem is
15.

        I hope that was almost somewhat clear.  I'd love to hear a
nice clear way to solve this problem, I'm not happy with my attempt
at all... :-(

>
> Prove that there exists a positive constant $C$ (independent of $n$,
$a_j$)
> which satisfies the inequality ¥par
> ¥hskip 15mm $¥displaystyle{¥max_{0 ¥leqq x ¥leqq 2} ¥prod_{j=1}^n
>            {¥left¥vert x-a_j ¥right¥vert} ¥leqq C^n {¥max_{0 ¥leqq x
>             ¥leqq 1} ¥prod_{j=1}^n {¥left¥vert x-a_j¥right¥vert}}}$ ¥par
> for any positive integer n and any real numbers $a_1$,$¥dots$,$a_n$.
>

        This one's really got me good - it seems like it should be
really easy, but I can't quite get it.  Anyone have an answer?

>
> Count out the number of positive integers $n < 120$
> such that $n^2 ¥equiv 1$ modulo 120.
>

        Obviously 1 and -1 (¥equiv 119) will work.  Now we want to find
n such that n^2 = 120k + 1 for some k.  If n were divisible by 2, 3, or
5, we would have a contradiction.  So we'll look at all n which aren't
divisible by 2, 3, or 5 - and we only haveta look at 1<n<60, since if
n^2 ¥equiv 1, then (120-n)^2 ¥equiv (-n)^2 ¥equiv 1.

        Now since the last digit of n^2 must be 1, the last digit of n
must be either 1 or 9.  So check 11^2, 19^2, 29^2, 31^2, 41^2, 49^2,
and 59^2.  I think only 11, 19, 41, 49, and 59 work out right.  That
means 1, -1, 11, -11, 19, -19, 41, -41, 49, -49, 59, and -59 all square
to 1 (modulo 120).  That's 12 of 'em.

        I have a feeling I did this the brute force way and that there
must be some nice number theoretic solution here - but it's beyond me!

>
> There is a parking lot in which 12 square are aligned.
> To park a truck we need two adjoining squares,
> and to park a car we need one.
> We park six cars and two trucks with leaving two squares
> so that we can park one more truck.
> Find out the number of such parking patterns.
>

        This is equivalent to the number of ways to park six cars,
two trucks, and one motorhome in 12 spots (assuming a motorhome takes
up 2 spots, just like a truck).  But that's just the number of ways
to park two trucks and one motorhome in 12 spots.  We can further
reduce this to {the number of ways to park one truck, one motorhome,
and one U-haul in 12 spots} divided by 3, if one U-haul takes up two
spots, just like a truck and a motorhome.

        This last number works out to be {9 choose 3} divided by 3,
or 28.

>
> Find the lattice point $(a,b)$ nearest to the origin such that
> the triangle with the vertices
> $(0,0)$, $(276,153)$, $(a,b)$
> has the area less then 2, and that $a$ and $b$ are positive.
>

        The triangle works out to have area (276a - 153b)/2.  To
minimize the area of the triangle, I'll set b to be the integer
closest to 276a/153.  A little trial and error for small a shows
that (5,9) is the first point with makes the area of the triangle
small enough.  [Then the triangle has area 3/2.]  So I think this
is the probably the best one can do.

        To see why the triangle has area (276a - 153b)/2, draw on
a piece of paper (I can't do ascii line art for my life) 5 points:
O: (0,0), A: (a,b), B: (153,276), C: (153,153b/a), and D: (153,0).
The area of triangle OBD is 276*153/2.  Subtract out the area of
triangle OCD, which is 153*(153b/a)/2.  Subtract out the area of
triangle ABD, which is (153-a)(276-b)/2 - (153-a)(153b/a - b)/2.
This will give you the area of triangle OAB; and a little algebra
turns the ugly mess into (276a - 153b)/2.

>
> Find the minimum value of
> ${¥rm AP}+{¥rm BP}+{¥rm PQ}+{¥rm CQ}+{¥rm DQ}$
> where P and Q are points in the unit square.
>

        I guess I have no clue what this question is asking:
anyone care to explain to clueless lil' me?

>
> Let $A$ be the set $¥{1,2,3,4,5,6,7¥}$.
> Count out the number of mappings $f ¥colon A ¥to A$
> satisfying the following conditions:
>
> ¥hskip 8mm (1) For each $j ¥in A$,
> there exists the unique $k ¥in A$ with $j=f(k)$ and $k ¥neq j$. ¥par
> ¥hskip 8mm (2) There exists a mapping $g ¥colon A ¥to A$
> such that $f(j)=g(g(j))$ for every $j ¥in A$. ¥par
>

        Look at S_7, the group of permutations of A.  We want elements
of S_7 (call one f) with no cycles of length one, and such that there
exists g in S_7 so that g^2=f.  By condition (2), f must have an odd
number of cycles of odd length, and an even number of cycles of even
length.  So a permissible f would be the permutation (1,2)(3,4)(5,6,7)
[then we can pick g to be (1,3,2,4)(7,6,5)].  But the permutation
(1,2,3,4)(5,6,7) is not a permissible value for f, because it does not
satisfy condition (2).

        There are 6! permutations with no even cycles.  There are also
7!/(3! 4!) * 3 * 2 permutations with 2 even cycles.  Thus the total
number of permissible permutations is 720+210=930.

>
> A fair coin is tossed repeatedly until the difference of the numbers
> of heads and tails comes to three. Count out the number of such
> processes to become 6 heads and 3 tails after 9 tosses.
>

        There is 1 way a process may stop after 3 tosses.  There are
3 such processes that stop after 5 tosses.  There are 9 such processes
that stop after 7 tosses.  There are 28 ways for a process to last 9
tosses.  I think.  (I just drew a picture and counted by hand, I didn't
really have any great inspiration for a general technique.)

     I wouldn't be surprised to find out I screwed up a lot of the
problems I tried, or did them the hard way.  Did anyone else attempt
this olympiad?  I haveta say I found it really interesting!

David Wagner
t-davidw@netmail.microsoft.com or dawagner@princeton.edu


From: bboru@lobby.ti.com (B. Borowicz)
Subject: Re: olympiad (little spoiler)


here's a Spoiler for just one of the problems:

> Count out the number of positive integers $n < 120$
> such that $n^2 ¥equiv 1$ modulo 120.

n^2 = 120k+1, which obviously ends in 1.  Any square which ends in 1 must 
be of the form 10m +/- 1, which is squared to 100m^2 +/- 20m + 1.  Therefore, 
m must be a solution to 100m^2 +/- 20m + 1 = 120k + 1, where 10m +/- 1 < 120.
Subtract and divide to get:
		            5m^2 +/- m = 6k
It's not hard to try integers at this point.  
You'll get 1, -2, 3, -3, 4, -5, 6, -6, 7, -8, 9, -9, 10, -11, 12, -12, ...
If 10m + 1 < 120, then all these except 12 will work, and the rest are too big.
Each negative solution above has an additive inverse which is a positive 
integer which is not yet spoken for.  Altogether, that makes 15 solutions.

	Brian Borowicz
	bboru@lobby.ti.com


From: a_rubin@dsg4.dse.beckman.com (arthur rubin)
Subject: Re: Solution to Amit Sahai's necklace problem

> You are making a necklace, and you have 24 beads. 8 are green,
> 8 are red and 8 are blue. Taking into account all the symmetries
> of the necklace, how many distinct arrangements of the 24 beads
> on the necklace are possible? 

Recalculating David Radcliffe's solution using the Polya counting theorem:

Consider all possible symmetries of the necklace (there are 48, as in the
previously mentioned solution), and consider the number of arrangements
preserved by each:

identity                         : C(24;8,8,8)=9,465,511,770

rotation by k, 3 not dividing k  : 0 (x16)                 0
rotation by 3,9,15,21            : 6 (x4)     =           24
rotation by 6,18                 : 90 (x2)    =          180
rotation by 12 or reflection/rotation:
                                 : 34,650 (x25)      866,250
                                               -------------
                                               9,487,237,344


So the answer is that divided by 48, which is

197,650,778.




From: greg@math.uchicago.edu (Greg Kuperberg)
Subject: Re: olympiad (little spoiler)

This is potentially correct, I think, but it's too complicated and
you have a mistake somewhere. 120 = 8 x 5 x 3, which are relatively
prime, and therefore

n^2 = 1 mod 120  <===> n^2 = 1 mod 8,3, and 5

n^2 = 1 mod 8    <===> n = 1,3,5, or 7 mod 8
n^2 = 1 mod 5    <===> n = 1 or 4 mod 5
n^2 = 1 mod 3    <===> n = 1 or 2 mod 3

By the Chinese remainder theorem (which has actually already been
invoked), there is a unique solution between 0 and 119, inclusive, to
the equations n = a mod 8, n = b mod 5, n = c mod 3.  That makes 16
solutions to n^2 = 1 mod 120 for non-negative integers n less than
120.  I have included 0 as a possibility for n for simplicity, but that
doesn't change anything, because it isn't one of the solutions.

Obligatory problem (from Yaglom and Yaglom):  Given a 1 foot stick,
mark two points on it at random, and then cut the stick at the two
points.  What is the probability that the three sticks can make a
triangle?

				Greg


From: Android <benjie@quack.kfu.com>


From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: (fwd) Problem of the Week

From: pow@forum.swarthmore.edu
Subject: Problem of the Week

Problem of the Week  7/19 - 7/23 1993

You have several cubes and three colors of paint: red,
yellow, and blue.  How many distinct cubes can you paint,
if you must use each color on each cube at least once?
(This does not involve combining blue and yellow to make
green, etc., though that is an interesting topic for
further discussion.)



From: Android <benjie@quack.kfu.com>
Subject: SPOILER, POW, SPOILER


SPOILER



























My answer is 5. But I am not sure because I never do a problem right
in this short of time.  Also, I think the solution depends on how you
interpret the word DISTINCT.  In my case, it means that no matter how
you put or rotate the cubes, they are different.


From: bboru@lobby.ti.com (B. Borowicz)
Subject: re: olympiad (little spoiler)


Oops.  I did forget one.  In my figuring, 5m^2+m = 6k, I forgot m = 0
 so 10m+1 would be 1.  Indeed, 1^2 is equiv 1 mod 120.  There ARE 16.

(Greg- I don't think it was that complicated.  I got all the solutions, and
 I did it in my head.  Maybe I didn't write it explicitely enough.
 What's the Chinese Remainder Theorem?)

	Brian Borowicz
	bboru@lobby.ti.com


From: greg@math.uchicago.edu (Greg Kuperberg)
Subject: Sticks (spoiler)

I won't give the solution to the sticks problem just yet, but
my answer for the probability is 1/4, not 1/16.

			Greg


From: greg@math.uchicago.edu (Greg Kuperberg)
Subject: Chinese remainder theorem

The Chinese remainder theorem says that if m_1,m_2,...,m_k are pairwise
relatively prime, then there is a unique solution mod m_1*m_2*...*m_k
of the equations

x = n_1 mod m_1
x = n_2 mod m_2
...
x = n_k mod m_k

for any n_1,...,n_k.  E.g., the theorem says that any question
of this type is well-posed:

I have a number, I know it mod 220.  It's 3 mod 4, 6 mod 11, and 2 mod 5.  
What's my number?

				Greg


From: jhardin@gandalf.pnl.gov
Subject: SPOILER: Greg's "stick problem"




Oops. Sent in my answer to the ObProblem a little too hastily.
I think the answer should be 1/8. You can arbitrarily rotate
the stick such that the leftmost cut is in [0,.5], then the
other cut must be in (.5,.5+x] where x is the first cut. Then
you get

  ¥int_0^{.5} ¥int_{.5}^{.5+x} dy dx = 1/8

All this assumes that to form a triangle, the longest piece (of the 
three pieces) must be less than one half.


  Cheers,

  James



From: pfriel@geom.umn.edu
Subject: P.O.W.--Spoiler

SPOILER
































My answer was 26.  This differs dramatically from Android's, and I have not fully double checked, but I feel rather confident about this answer, assuming I correctly understood the question.
									-PWF



From: Android <benjie@quack.kfu.com>
Subject: POD



How many distinguishable arrangements can be made using exactly 5
letters from the work DIVIDED?

Enjoy,

Happy Mathing,

Benjie

P.S.: Anyone has CompuServe account?



From: benjie@hip-hop.suvl.ca.us (Benjie Chen)
Subject: SPOILER -- POW -- New answer from me

SPOILER





Just realized that I misunderstood the problem.   The answer should be
24 I think, not 5.  But 24 != 26, and I am still checking.

Benjie



From: gracky@math1.kaist.ac.kr (Hong Seongho)
Subject: subscribe




From: josephy@ee.ubc.ca (joseph yan)
Subject: SPOILER -- POW

SPOILER
























At first I agreed with Benjie that the answer was 24 but as I was typing in
my solution, I found a few more distinct cubes and my answer is now 29!
I hope I didn't miss any!  Anyways, here's my explanation:

Work with one colour first (let's start with red).

We can only paint two distinct cubes having 4 red squares (one such that
the yellow and blue are adjacent, and one such that they are opposite).

Now if we are to paint it with 3 red squares, those red squares can only
form two different configurations...all sharing a corner (I'll call it
the "corner" config), or going around in a strip (I'll call it the "strip"
config).  The "strip" config allows 4 distinct cubes...a) 2 blues adjacent
to each other, b) 2 blues opposite to each other, c) 2 yellows adjacent,
or d) 2 yellows opposite.  The "corner" config allows only 2 distinct cubes
...a) 2 blues adjacent or b) 2 yellows adjacent.

Now this shows that there are only 8 distinct cubes that can have red in
the majority.  Obviously, this is true for any of the other colours so 
multiply by 3...to get (ta-da) 24.  I almost stopped here...

Of course, the last possibility is to have 2 of each colour and again, I
start with red.  It can have 2 configurations...adjacent or opposite.  In
the adjacent config, there are 3 distinct cubes...a) 2 blues opposite, b)
2 yellows opposite or c) no colours opposite.  The opposite config only has
2 distinct cubes...a) 2 blues opposite or b) 2 blues adjacent.

So that's 5 more distinct cubes!

...hope I didn't miss any...

Joe


From: Van@cup.portal.com
Subject: Cube problem

 Re: How many N-cubes in an M-cube?
 
 This should be of help to anyone who still has questions about the problem.
 
 I had asked Steve what he meant by a "construction proof", and here is his 
answer.
 ============
 S.CHASE7 [Steve]             at 07:47 EDT
 
 Van:
 Here is that overkill I mentioned over a week ago.

 By "in construction proofs", I mean that
 one builds a model N-cube in [0,1]^M at the origin and then maps
 that model to sister locations.  "At the origin" means whenever
 you need to choose a hyperplane coordinate, choose 0.  Hence my
 comment that M-N values are 0, that's how many choices of fixed
 coordinates there are for our model N-cube representing its sisters.

 These sisters have no boundaries in common with each other.
 There are {M,N} disjoint sets of such sister-groups.
 The representative sisters from these groups taken together
 are the set of N-cubes adjacent to the origin.

 There are 2^(M-N) N-cubes in each family of such sisters.  Each one
 is associated with a unique point (0-cube) in the (M-N) Dim closed
 supporting hyperplane perpendicular to the family and adjacent to
 the origin.  The entire M-cube could be defined as the closure of
 the cross product of any family and its associated hyperplane.

 Example M=2, N=1.
     (1,0) --- a --- (1,1)
       |               |
       b               c
       |               |
     (0,0) --- d --- (0,1)

   The sister families (with model/representative listed 1st)
   are {b,c} and {d,a}.  The associated 0-cubes in hyperplanes
   are as follows:
   1-cube   family    hyperplane   0-cube_of_hyperplane
   ------   ------    ----------   --------------------
     a       ad        (_,0)         (1,0)
     d       ad        (_,0)         (0,0)
     b       bc        (0,_)         (0,0)
     c       bc        (0,_)         (0,1)

 Example M=3, N=2. Faces of dice, usual numbering 1-6 sum of
 opposite faces = 7.

 Define the origin as the point adjacent to 1,2, and 3.
 There are 3 sister families, 2 members each.  Representative
 listed first: {1,6}, {2,5}, {3,4}.

 Example M=3, N=1. Same numbering of faces.  Now there are
  3 families each with 4 members.  Name each 1-cube by the
  2 names of adjacent faces.  Name families by representative.
  Name 0-cubes by the 3 faces adjacent.
  1-cube   family    hyperplane     0-cube,associated
  ------   ------    ----------     ------
    12       12          3           123    *
    15       12          3           135
    65       12          3           356
    26       12          3           236

    13       13          2           123    *
    14       13          2           124
    46       13          2           246
    36       13          2           236

    23       23          1           123    *
    24       23          1           124
    45       23          1           145
    35       23          1           135
   ---
   note * : the representive is associated with the origin.

 Perhaps families of sisters is counter-intuitive in that
 they have all moved away from home as far as possible.
 They share the same DNA (the 1 out of {M,N} choice of unit
 vectors that make them parallel to each other), but their
 mailing addresses (1 out of 2^(M-N) points in assoicated
 perpendicular hyperplane) are different.

 Steve from N-space


From: Van@cup.portal.com
Subject: bead problem

 This is Watson's solution to the bead problem, with the same answer as 
David's.
 (My experience with Watson gives me confidence in his solutions to problems).
  ------------
Category 5,  Topic 24
Message 471       Sat Jul 17, 1993
J.MCGOWAN15 [Watson]   (on Genie)
 
With regards to the beads (24, some read, blue, etc.), the easiest way I know
to look at the orbits is with the PolyaBurnside theorem.
 ------------
Category 5,  Topic 24
Message 476       Sat Jul 17, 1993
J.MCGOWAN15 [Watson]         at 10:33 EDT
 
RE: The beads:

Solution to the beads on a bracelet problem.

Let me consider a simpler problem... you have 24 of each type of bead (this
way, one can create beads of any one colour).

Let G be a group, S a set... let G act on S and let two elements be equivalent
if we can change one into the other using G (the set of elements equivalent to
one is called its orbit). The number of distinct orbits is (Polya-Burnside):

  S/G

Where G is the order of the group and S is the SUM:

  SUM[Ig: over all g in G]

Ig is the number of elements which are unchanged when acted upon by g.

Let us consider two possible groups... the rotations and the dihedral group
(on a polygon of n sides, there are n rotations, and the dihedral group has
order 2n... it includes reflections).

 A--a--B            C
 |¥ | /|           /|¥
 | ¥|/ |          / | ¥
 c--+--d         f  |  e
 | /|¥ |        /   |   ¥
 |/ | ¥|       /    |    ¥
 C--b--D      E-----c-----F

In the square, the rotations move A->B->D->C: A->D,B->C: A->C->B->D and the
identity.

The reflections A<->B,C<->D (around the line ab): B<->C (around the diagonal
AD): A<->C,B<->D around the line cd: and A<->D around the diagonal BC.

Note half the reflections contain two points (for an even sided polygon) and
half none.

For the triangle (n=3) we have the rotations: C->F->E, C->E->F and the
identity and rotations:

around Cc (E<->F) and around Ee and Ff (for n odd, all rotations go through
one vertex and one edge).

Let f(n) be PHI(n) the Euler function (which is the number of 0<r<=n which
have GCD(r,n)=1; that is, the number of numbers less than n which are
relatively prime to n).

If a is a sequence of integers (a1,a2,a3,..,ak): define a!=a1!*a2!*a3!...*ak!.

If we have a set of N numbers... a1 copies of the number 1, a2 copies of "2",
... ak copies of "k" (SUM[ai]=N) then the number of distinct ways of writing
down these N elements is N!/a! (and SUM[N!/a!:for a1+a2+..+ak=N]=k^N, the
multinomial expansion).

Suppose we have a polygon of N sides (vertices) and a rotation through k
places (modulo N)... (I will take k=1,2,...N). Suppose the GCD(k,N)=r, then I
will say that for my purposes, the rotation through k is equivalent to a
rotation through r. The reason this is so, is if I have a colouring of the
vertices of the polygon what is invariant under this rotation,  then the
vertex at zero must have the same colours those at postions 0,r,2r,..N-r (N/r
positions) (eg, in the square, the rotation through three elements, the last
listed, guarantees that the A vertex must be the same as the C vertex and that
the same as the D vertex and that the same as the B vertex... this is the same
as saying the colours are invariant under the rotation through 1 postion
clockwise instead of three!)... so invariance under k is the same as
invariance under r where r=GCD(N,k).

The number of rotations equivalent (as above) to a rotation r (where r divides
N) is f(N/r).

(Thus, for the square, though 3 does not divide 4, for invariance of colour,
rotation three is equivalent to rotation one where 1 DOES divide 4!)

CASE 1: A polygon of N vertices, with k colours for each vertex... we want the
number of inequivalent bracelets makeable if we have infinitely many beads of
each colour and cannot flip the bracelets over (only spin them round)... in
this case we take G as the rotation group with order N.

We need S1=SUM[Ig: g a rotation through k:k<=N]

Suppose we have a rotation equivalent to rotation through r where r divides
N... then we may choose the first position arbitratily (fixes the one r steps
later, and r steps after that, etc.), the second one arbitrarily,... up to the
r'th arbitrarily... such a colouring (choosing these r and fixing the others
so as to ensure invariance) is invariant (and only these)... here we may
choose k colours for any of these first beads for a term of k^r for any
rotation equivalent to r... but there are f(N/r) of them, so:

 S1 = SUM[k^r*f(N/r): r divides N]

and the number of distinct bracelets is S1/N.

CASE 2: we have n1 of colour 1, n2 of colour 2,...nk of colour k with
n1+n2+...+nk=N (and again do not alow flipping the bracelet over).

In this case we cannot arbitrarily pick colours, because we may run out of
some!

G is the rotation group (order N again).

Suppose we have a rotation equivalent to a rotation through r where r divides
N... suppose the first colour occurs a1 time in the first r beads, the second
a2 times, the third a3 times, etc.

The total number of times the first colour occurs is a1*N/r, but this must be
n1 (since we use up all the beads!), so a1=r*n1/N, a2=r*n2/N,...ak=r*nk/N.

Consider the sequence r*n/N (where n is the sequence n1,n2,...nk... this is
the sequence r*n1/N, r*n2/N,... r*nk/N).

The number of ways we can choose the colours of the first r beads is
r!/(rn/N)! (only if rn/N is a sequence of integers!), so Ig=r!/(rn/N)! for any
rotation equivalent to r, of which there are f(N/r) and so, we need the sum:

S1'=SUM[r!*f(N/r)/(rn/N)!: r divides N and rn/N is a seq. of integers]

and the number of bracelets is S1/N.

(remember, (rn/N)!=(r*n1/N)!*(r*n2/N)!*..(r*nk/N)!) CASE 3: Infinite number of
beads of each of k colours, N bead bracelet but we take into account the
flipping over (G is the dihedral group).

As G contains the rotations, we need:

 S = S1 + S2

and the number of bracelets is S/(2N) (S1 the sum for rotations only as in
CASE 1).

S2 has the form (for reflections):

IF N IS EVEN:

 S2 = k^((N-2)/2)*k^2*N/2 + k^(N/2)*N/2

 (the first term for the reflections through diagonals which pass through two
 vertices... we can choose these two colours arbitrarily and fix the colours
 of the (N-2)/2 colours on one side arbitrarily, so Ig=k^((N-2)/2)*k^2 for
 each of these N/2 reflections... for the N/2 reflections which do not pass
 through a vertex, we have Ig=k^(N/2))

IF N IS ODD:

 S2 = k^((N-1)/2)*k*N

 as each of the N rotations through one vertex has that vertex choosable
 (factor of k) and half the others (on one side) arbitrary for invariance.

Finally the case for which the problem asks a solution:

CASE 4: N beads, ni of each of k colours, SUM[ni]=k: allow flipping (G is the
dihedral group) and our answer is:

 S'/(2N) = (S1' + S2')/(2N)

where S1' is the sum from the rotations (CASE 2) and S2' must be obtained.

(let me just do N even): for any rotation NOT going through two vertices, the
stuff on the right must be the same as that on the left... so each ni must be
even and we get:

Ig=(N/2)!/(n/2)! (or zero if any ni is odd) for each of the N/2 reflections
through no vertices.

For reflections through two vertices we must consider:

If there are some odd ni... we can choose any two different colours from odd
ni's use them as the vertices through which the diagonal passes, and split the
other colours evenly on both sides... the even splitting means that we would
only get a contribution here if EXACTLY two ni (say n1,n2) are odd, then we
can choose either 1,2 or 2,1 as the colours for the two vertices (a factor of
2) and then have another factor of:

 2(this is the factor for the order of choice of the first two)*

 ((N-2)/2)!/(m/2)!

(where m=(m1,m2,...mk)=(n1-1,n2-1,n3,n4,..nk)... m just takes away those two
elements from the two colours with an odd number.

This is Ig for the N/2 reflections which pass through two vertices IF there
are precisely two colours with an odd number of beads.

If (instead) all the ni's are even, let m(j) be the sequence:

m(j)=(n1,n2,...nj-2,...nk) where we reduce nj by 2 (for the vertices covered
by the diagonal)

Then the N/2 reflections through 2 vertices have Ig as follows:

SUM[((N-2)/2)!/(m(j)/2)!: for j=1,2,..,k]

(in the posted problem, there are three terms in the sum, each of the same
value, 11!/(4!*4!*3!), and this occurs as Ig for the 12 reflections through
vertices)

If there are more than two ni's that are odd (an even number, since the sum is
N which is even) then the term due to the reflections (S2') is zero.

For N odd, I leave it to your imagination.
 ------------
Category 5,  Topic 24
Message 479       Sat Jul 17, 1993
J.MCGOWAN15 [Watson]         at 11:36 EDT
 
RE: Bead problem

Specific case:

N=24, n=(8,8,8)

The only divisors of 24 for which r*n/N is an integer sequence are
r=3,6,12,24.

For these values we have:

 r  N/r  f(N/r)  rn/R      r!*f(N/r)/(rn/N)!
 -------------------------------------------

 3  8      4    (1,1,1)   3!*4/(1!1!1!)=24
 6  4      2    (2,2,2)   6!*2/(2!2!2!)=180
 12 2      1    (4,4,4)   12!*1/(4!4!4!)=34650
 24 1      1    (8,8,8)   24!*1/(8!8!8!)=9465511770

                                    +-+-+

So S1'=9465546624 (and the number of bracelets, not considering reflections is
S1'/24=394397776)

                                    +-+-+

S1'/48+S2'/48 is the number considering reflections:

For the N/2 reflections NOT going through vertices we have
Ig=12!/(4!4!4!)=(N/2)!/(n/2)!=34650... for part of S2' given by N/2 times
this, or 415800

For the N/2 vertices going through vertices we have Ig given by
11!/(4!*4!*3!)*3 for a contribution to S2' of 12 times this, or
34650*12=415800 again.

                                    +-+-+

So, S1'/48+S2'/48=197216213 different bracelets considering reflection!

(sure... you can submit this solution... with, now, the numbers for the bead
problem!)
 ------------
Category 5,  Topic 24
Message 480       Sat Jul 17, 1993
J.MCGOWAN15 [Watson]         at 12:42 EDT
 
Finishing the bead problem:

I gave the full solution except to the problem when N is odd and we have
n1+n2+..+nk=N.

In this case the number of different bracelets is (S1'+S2')/(2N) (assuming we
take reflections into account) where:

  S1' = SUM[r!/(rn/N)!*f(N/r): for r dividing N and n an integ. seq.]

as before.

S2'=0 unless precisely one of the ni's (say n1) is odd... in that case (with
m=(m1,m2,..mk)=(n1-1,n2,n3,..,nk)),

 S2' = ((N-1)/2)!/(m/2)!*N

(here, each of the N reflections has colour 1, the odd one, as the colour of
the vertex through which the reflection axes passes, and half the other
positions can have an arbitrary choice among the colours (provided half the
beads of each colour are on each side))

                                    +-+-+

So, the formulas above give the results for any bracelet problem provided
either one has enough of each colour to make a bracelet solidly of any one
colour, or just enough of each colour so that all the beads must be used. And
formulas are given depending upon whether can or cannot flip the bracelet (if
one wears one on one's arm, one can twist it around, but not flip it over
without taking it off)... that should kill it!

[ERROR above... the formula for S1' should limit the sum to rn/N being an
integer sequence, of course]
 ------------


From: Android <benjie@quack.kfu.com>
Subject: P.O.D.



P.O.D.

There are four abnormal dice.  Cain chooses one of these four dice and
then Abel chooses one of the remaining three dice.  They each toss
their dice and one getting the highest wins.  But no matter which die
Cain chooses, Abel always has the possibiity of choosing a die such
that he wins with the probablity 2/3.  What kind of dice are they
using (draw a picture, such as:               )?  
				1
                                2
                              4 5 6
                                3  
                                       
Bonus: the name of those dice?

Benjie


From: t-davidw@microsoft.com
Subject: Corrections to Re: Japan Math Olympiad *SPOILER*


Corrections to some spoilers follow!



>
> Count out the number of positive integers $n < 120$
> such that $n^2 ¥equiv 1$ modulo 120.
>

     Ok, as some other posts have pointed out, the correct answer
here is 16.  I can't even multiply straight... :-)

>>
>> There is a parking lot in which 12 square are aligned.
>> To park a truck we need two adjoining squares,
>> and to park a car we need one.
>> We park six cars and two trucks with leaving two squares
>> so that we can park one more truck.
>> Find out the number of such parking patterns.
>>
>
>        This is equivalent to the number of ways to park six cars,
>two trucks, and one motorhome in 12 spots (assuming a motorhome takes
>up 2 spots, just like a truck).  But that's just the number of ways
>to park two trucks and one motorhome in 12 spots.  We can further
>reduce this to {the number of ways to park one truck, one motorhome,
>and one U-haul in 12 spots} divided by 3, if one U-haul takes up two
>spots, just like a truck and a motorhome.
>

     Yikes!  I lied.  This would work if the two empty spaces in
the parking lot hadta be adjacent.  But they don't.  So all I need
do is count the number of ways to place two trucks in the parking
lot and multiply that by the number of ways to put 6 cars in the 8
spaces left over.  So I get 10!/(8!2!) 8!/(2!6!) = 1260.

     Ok, let's hope that's a little closer to being correct... :-)

Dave Wagner
t-davidw@netmail.microsoft.com or dawagner@princeton.edu


From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Re: Solution to Amit Sahai's necklace problem

> 
> > You are making a necklace, and you have 24 beads. 8 are green,
> > 8 are red and 8 are blue. Taking into account all the symmetries
> > of the necklace, how many distinct arrangements of the 24 beads
> > on the necklace are possible? 
> 
> Recalculating David Radcliffe's solution using the Polya counting theorem:
> 
> Consider all possible symmetries of the necklace (there are 48, as in the
> previously mentioned solution), and consider the number of arrangements
> preserved by each:
> 
> identity                         : C(24;8,8,8)=9,465,511,770
> 
> rotation by k, 3 not dividing k  : 0 (x16)                 0
> rotation by 3,9,15,21            : 6 (x4)     =           24
> rotation by 6,18                 : 90 (x2)    =          180
> rotation by 12 or reflection/rotation:
>                                  : 34,650 (x25)      866,250
>                                                -------------
>                                                9,487,237,344
> 
> 
> So the answer is that divided by 48, which is
> 
> 197,650,778.

That is a very simple and elegant solution.  I guess I did it the hard way!
There is an addition mistake above; the sum should be 9,466,378,224.
When you divide this by 48, you get 197,216,213, which (miraculously!)
agrees with my solution.

Dave 


From: Ariel Landau <c0465193@techst02.technion.ac.il>
Subject: P.O.D. *SEMI-SPOILER*

On Tue, 20 Jul 1993, Android wrote:

> P.O.D.
> 
> There are four abnormal dice.  Cain chooses one of these four dice and
> then Abel chooses one of the remaining three dice.  They each toss
> their dice and one getting the highest wins.  But no matter which die
> Cain chooses, Abel always has the possibiity of choosing a die such
> that he wins with the probablity 2/3.  What kind of dice are they
> using (draw a picture, such as:               )?  
> 				1
>                                 2
>                               4 5 6
>                                 3  
>                                        

You can find the answer tho this problem (as many other interesting things)
in the book 'Inumeracy. Mathematical illiteracy and its consequences'
by John Allen Paulos. May be I will take a look tonight and send the complete
answer tomorrow :)

Ariel Landau
Haifa, Israel.


From: josephy@ee.ubc.ca (joseph yan)
Subject: Pam & Sam problem

Here's an interesting problem I got from a friend who got it from a
friend who...(original source unknown)...


----------
There are two different integers from 2-99 inclusive.  Pam gets the product
and Sam gets the sum.  Pam knows that Sam has the sum and Sam knows that Pam
has the product.  The following conversation takes place:

Pam:  I don't know what the two numbers are.
Sam:  I knew you'd say that.
Pam:  In that case, I do know what the numbers are.
Sam:  In that case, I know what the numbers are too.

What are the numbers?

* Assume that Pam and Sam are not lying and have not made mistakes in their
statements ;-)

PS:  I found a solution but had no simple way of proving uniqueness;
	however, I was assured that the solution is unique by someone
	who said he wrote a computer program for it.  I'm very interested
	in seeing what other people come up with.  I'll post my solution
	next Friday (unless someone else's solution is sooooooo good
	that I'd be embarrassed to even mention mine).

-----------------------------------------------------------
Joseph Yan
UBC Electrical Engineering	Tel:  (604) 822-9215
2356 Main Mall			Fax:  (604) 822-5949
Vancouver, BC			email:  josephy@ee.ubc.ca
Canada V6T 1Z4



From: Van@cup.portal.com
Subject: parking problem

 David, regarding your post:
 
>> There is a parking lot in which 12 square are aligned.
>> To park a truck we need two adjoining squares,
>> and to park a car we need one.
>> We park six cars and two trucks with leaving two squares
>> so that we can park one more truck.
>> Find out the number of such parking patterns.
>>
>
>        This is equivalent to the number of ways to park six cars,
>two trucks, and one motorhome in 12 spots (assuming a motorhome takes
>up 2 spots, just like a truck).  But that's just the number of ways
>to park two trucks and one motorhome in 12 spots.  We can further
>reduce this to {the number of ways to park one truck, one motorhome,
>and one U-haul in 12 spots} divided by 3, if one U-haul takes up two
>spots, just like a truck and a motorhome.
>

     Yikes!  I lied.  This would work if the two empty spaces in
the parking lot hadta be adjacent.  But they don't.  So all I need
do is count the number of ways to place two trucks in the parking
lot and multiply that by the number of ways to put 6 cars in the 8
spaces left over.  So I get 10!/(8!2!) 8!/(2!6!) = 1260.

     Ok, let's hope that's a little closer to being correct... :-)

Dave Wagner
t-davidw@netmail.microsoft.com or dawagner@princeton.edu
 ==========
 
 The problem says
 
 >leaving two squares so that we can park one more truck.<
 
 so the 2 remaining squares have to be adjacent, and it is just like
 parking 3 trucks and 6 cars--I think you were right in the first place.
 ========
 
 I am having trouble with this though.
 How many ways are there to park 3 trucks in 12 spaces if they
 take up 2 spaces?
 It seems that the ends make a problem. If a truck parks in space 1,
 that leaves 2-12 available for the others, but if he parks in 2,
 then place 1 can't be used for trucks.
 
 I think I worked this out for 2 trucks, but not for 3.
 
 But this leaves only 6 spaces for the 6 cars, so they are
 irrelevant (as far as "parking patterns" go, the cars and
 trucks are identical).
 
 van@cup.portal.com          Van


From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Distribution of first significant figures



There was some discussion on this list about the distribution of
first significant figures of "random" numbers.  Purely by chance,
I have found an article on this topic.  It appears in the April
1969 issuse of the American Mathematical Monthly.  The first few
paragraphs of the article are quoted below:

                 - - - - - - - - - - -

        ON THE DISTRIBUTION OF FIRST SIGNIFICANT FIGURES
             R. A. Raimi, University of Rochester

According to F. Benford, in what appears to be the earliest paper
on this subject, someone noticed that library books of logarithm
tables used by students were dirtier towards the beginning than 
towards the end.  While such a phenomemon is to be expected in bad
novels, it seemed curious that students of chemistry and engineering
should have been more interested in the logarithms of numbers 
beginning (say) with the digit 1 than with 2, and so on.  This
curiosity suggested that the first digits of the numbers dealt with
by these students did not occur with equal frequency, but that the
earlier digits appeared more often than the later.

Benford made many counts, using numerical tables of various sorts.
Typical examples of such tables might be:
  
  (a) The street addresses of the first thousand people listed in Who's Who;
  (b) The areas, in square miles, of a thousand rivers in the U.S.A.; and
  (c) The freezing points, in degrees centigrade, of a thousand chemical
      compounds.

In his collection of such "random" cases, Benford found that the fraction
of all entries whose first digit is <= p is approximately log_{10}(p+1),
for p=1,2,...,9.  The law does not hold, of course, in "systematic"
tables, such as the square roots of the first thousand digits.




From: Android <benjie@quack.kfu.com>
Subject: Did Fermat Proved His Theorem


From: dlr@math.ams.org (Dave Rodgers)

Did Fermat prove his `Last Theorem'

Andrew Granville


A question that is often asked, and now more frequently 
than ever before, is whether Fermat really did have his
`truly remarkable proof that the margin was too small to
contain'.  Most professional mathematicians seem to doubt
that this is too likely, whereas many optimistic amateurs
not only believe Fermat but are certain that they are 
on the verge of re-discovering that `truly remarkable
proof'.

My view is that you should never discount a statement made 
by someone as formidable as Fermat, though perhaps the history
indicates that he made a mistake.
After all he only wrote his statement while defacing his copy
of Diophantus' `Arithmetic' and presumably did not expect anyone to see
it, except perhaps the next person to borrow the book out of the 
U. of Toulouse library. He never wrote to any of his correspondants
about this question, which he was prone to do when he had done 
something that really pleased him.

Moreover the date is a bit suspicious. The date accredited for his
`marginal comments' is 1637; I have no idea where that date comes from
(how does anyone know when he wrote these notes to himself ?).
But the great flowering of profound ideas from Fermat was in 1640.
That is when he discovered the `Little Theorem', it was when
he wrote to Frenicle about his method of factoring numbers using the
difference of two squares, and when he claimed that he knew how to 
prove that there are no four squares in arithmetic progression,
What a year !  But how could he have worked out something as profound as 
Fermat's Last Theorem, when he didn't even yet know about the `Little
Theorem'. In 1640 he did not know the connection between whether or
not x is a quadratic residue mod p, and the residue of x^((p-1)/2) mod p
(he noted that the residues are always -1 or 1, but he didn't know how
to tell which is which). 

On the other hand, Fermat was amazingly creative and imaginative.
Although we can now prove or disprove everything that he claimed, 
we most often do not know how he proved things:
In his (many) correspondances he was vague, probably deliberately vague 
in order to have `fun' with his peers. He only once wrote down any account 
of his descent process, but evidently he later applied it to far more 
difficult curves than x^4+y^4=z^2.  How did he succeed, given that he did 
not have our hindsight and knowledge to motivate his methods ?    
For those who know something about it, is it impossible that Fermat 
had an awareness of certain obstructions to the descent process
(like the Tate-Safarevic group) ?  Of course I am not suggesting
that he knew such things in any form that was not pretty naive by today's view,
but he evidently did a large amount of calculation and probably had a feeling
for when things were going to work out, and when they are not.

My point in writing all this is that he may not have thought about things
the way we do, but I'm sure that he had many interesting views, some 
of which we may not have recovered.  I notice how many authors patronize Fermat's work, it seems simply because they can find straightforward proofs
of what he did, though those authors have usually had the hindsight of
the mathematical culture created by the work of Euler, Mordell, Weil
and many, many others. Of course, it is possible that we have guessed most of
what Fermat's methods were, but I am not convinced.

We do not patronize the legacy of Ramanujan in quite the same way, even
though though we are also able to prove more-or-less everything that he 
claimed. (And was correct; his work on the distribution of prime numbers 
was way out, but for interesting reasons).  The reason why Ramanujan gets 
so much more respect than Fermat for the genius of his ideas, is that it 
is abundantly clear that we can not have recovered the same techniques
as Ramanujan had, for several questions. He could not have guessed
some of the things he did, and he did not have the technology for the proofs
we have, so how on earth did he get there ?

The only truly plausible account of how Fermat thought, which I have seen,
is in Weil's `Number theory, An Approach Through History'.  Reading Weil's
analysis of what Fermat thought and how he knew it, it does seem likely that 
Fermat only wrote his marginal note after a nice bottle of Margaux at 
lunchtime, and it shouldn't be taken too seriously.

Apparently Euler once received a `proof' of FLT from an optimistic amateur 
with a descent argument that is correct, though complicated, but magically
ends up giving you the same solution to the equation as you started with.
A priori, it is by no means obvious that this will be the outcome.  
It is a plausible explanation of what Fermat did; and perhaps he realized
soon afterwards the flaw, which is why he never publicized `his Theorem'.

But who really cares whether Fermat knew how to do it or not ?
So much wonderful mathematics has resulted from his claim, and that is
surely the important thing. Many number theorists, including Andrew Wiles,
have testified that they would not be doing research in mathematics were it
not for the challenge and mystery of `The Last Theroem'.
What now, though, will take its place ?

One last thing; I recently heard about a seance at which Fermat was
reached. Apparently he let it be known that Wiles' proof does have a flaw.
In fact Fermat has recently found a solution to the equation,
but this universe is too small to contain it!



From: Android <benjie@quack.kfu.com>
Subject: Re: P.O.D....tough problem!

Well, they suppose to be 6 sided dice, all of them, and they don't have to
be distinct.

Benjie


From: greg@math.uchicago.edu (Greg Kuperberg)
Subject: The mod 120 problem (total spoiler)

Ok.  Two people have now claimed that the answer is 15, although one of
them I think has changed his mind.  For the record, the numbers n
from 1 to 119 such that n^2 = 1 mod 120 are:

 1  11  19  29
31  41  49  59
61  71  79  89
91 101 109 119

Maybe there are some patterns here...

				Greg


From: claxnes@sandia.gov


I sent the following message about 2 weeks ago. I assume it never was 
distributed since I didn't receive it. Has anyone done anymore
work on the spider problem?
------- message ---------------------------------
Wlodek proposed the following theorem:

>
> Let's consider n-dim cube  [0,1]^n.  Assuming that our spider crawls
> along n-1 dim faces the answer is  sqrt(n+2) for n>1.
> 
> But what about a spider crawling only along k-dim faces
> of the n-cube? Prove that:
> 
> Theorem. The minimal length of a path joining the opposite
> vertices of n-cube, which is totally contained in its k-skeleton,
> equals to
>                 sqrt(k-1 + (n-k+1)^2)
> 
> for every integer n and k such that 0 < k < or = n.
> 
>         Wlodzimierz Holsztynski  (or simply Wlodek)

Someone, sorry I have forgotten who, posted a counterexample to the above
theorem, Stating that in 4-dim a spider could walk the 2-skeleton path
(0,0,0,0) ----> (1,1,0,0) -----> (1,1,1,1) over a length of 2sqrt(2)
which is less than the sqrt(10) predicted by the above theorem.

I conjecture the following:
A) A Spider walking a 2-skeleton in an n-dim cube has the following 
   minimal path length, p(n):
   1) p(1)=1
   2) n even: p(n)=n/sqrt(2)
   3) n odd>1 : p(2n+1)=sqrt(5)+(n-1)sqrt(2)
   4) For n>2, The minimal path is not unique.

PARTIAL SPOILER (1,2,4 ABOVE)













































1) Notes: Proving the conjecture for n=1,2,3 is fairly trivial. For example,
   for n=3, one may write the line length of the path (0,0,0) --> (1,x,0) -->
   (1,1,1) in terms of x and then minimize using methods of calculus (take
   derivative set to zero and solve for x, etc.).
2) Proof of even case (n>2).
   We first note that the path across face diagonals
   (0,0,0,0,0,0,...0) ---> (1,1,0,0,0,0, ...0) ... (1,1,1,1,...1)
   has length n/sqrt(2).
   For n>2 we consider,
   (0,0,0,0,..0) ---> (1,x,0,0,...0) ---> (1,1,y,0,0,..) ---> ... (1,1,...1)
   which has path length, 
   f(x_1,x_2,...,x_n)=sqrt(1+x_1^2) + sqrt((1-x_1)^2+x_2^2) +
		      sqrt((1-x_2)^2+x_3^2)+...+ sqrt((1-x_{n-2})^2+1)
   Applying Minkowskii's inequality repeatedly,
   f(x_1,x_2,...,x_n)=>sqrt((1+x_2)^2+1) + sqrt((1-x_2)^2 + x_3^2) +...
		     =>sqrt(2^2+(1+x_3)^2) + sqrt((1-x_3)^2 + x_4^2) + ...
		     .
		     .
		     .
		     =>sqrt((n-3+1)^2 + 2^2)
		     = sqrt((n-2)^2 + 4).

But sqrt((n-2)^2+4)=>n/sqrt(2) when n=>4. Therefore, the "diagonal" path
across k-skeletal faces is the minimal one. Strictly speaking, the above
proof should cover all combinations of paths, including combinations of
"diagonal" and "non-diagonal" paths, but it is easy to see that in this case
the "diagonal" paths, may be grouped and the above
logic applied to the "non-diagonal" subset.
4) It is fairly easy to see that many minimal paths exist for n>2. i.e.
   (0,0,0,0) ---> (1,1,0,0) ----> (1,1,1,1) and
   (0,0,0,0) ---> (1,0,1,0) ----> (1,1,1,1) or
(0,0,0,0,0) --> (1,.5,0,0,0) --> (1,1,.5,0,0) --> (1,1,1,.5,0) --> (1,1,1,1,1)
and
(0,0,0,0,0) --> (1,1,0,0,0) --> (1,1,1,.5,0) --> (1,1,1,1,1)
		     <= nsqrt(2)/2.

3)   Note that the M inequality may be used to prove that sqrt(5) is the
     correct minimum when n=3, but gives f=>sqrt(13) rather than sqrt(5)+sqrt(2)     for the case of n=5. Since sqrt(5)+sqrt(2)>sqrt(13) this leaves the
     possibility of a min less that p(2n+1)=sqrt(5)+(n-1)sqrt(2)! I will be
     away from my computer for a while so I will leave it to an interested IAMS
     member to find a rigorous proof. Final Note: If my memory serves me
     correctly the M ineq. is an equality when all the a_i and b_i are
     equal. Unfortunately on this problem the a_i and b_i are of the forms
     1, x, 1-x which cannot all be equal. Thus the lower bound offered by the
     M ineq. is probably not maximal and I'll bet formula 3) is OK.



From: wft@math.canterbury.ac.nz (Bill Taylor)
Subject: Cubes colored in 3 colors.

So far as I've seen, the current count of 3-colored cubes is 29; as sent in
by Joseph Yan.   Sorry Joe, but you still missed one !

> Of course, the last possibility is to have 2 of each colour and again, I
> start with red.  It can have 2 configurations...adjacent or opposite.  In
> the adjacent config, there are 3 distinct cubes...a) 2 blues opposite, b)
> 2 yellows opposite or c) no colours opposite.

Alas !!  Case (c), where all three colors come in adjacent pairs, has two
subcases, according to handedness. It is rather difficult to visualize this at
first, (especially as the two RYB corners have different rotation-senses, so
that this criterion fails to distinguish the two cubes).

So don't despair; I, too, only counted the 29 when I did it. The way I finally
discovered my error was by re-doing the whole problem using the Polya counting
method that A.Rubin recently posted for use on the necklace problem.   This
gave the answer 30; and the problem color-distribution was immediately obvious,
enabling me to detect the missing cube fairly quickly.

The Polya method is slower for very tiny problems, (e.g. cubes with 2 colors,
or tetrahedra with 2,3 or 4 colors); but it is faster for larger problems,
AND has the GREAT ADVANTAGE that it has a built-in check on accidentally
missing sub-cases. The check is that when you divide by the order of the group,
any mistakes will probably show up here as non-integers.

So: looking at cubes painted in three colors....

             Color distributions     4.1.1  3.2.1  2.2.2
                                    ---------------------
             identity move (1 case)    30     60     90
     face quarter-rotation (6 cases)    2      -      -
        face half-rotation (3 cases)    2      4      6
             mid-edge flip (6 cases)    -      -      6
    long-diagonal rotation (8 cases)    -      -      -

                    grand totals       48     72    144

divide by the order(= # cases), 24:     2      3      6
                                      ------------------
   & multiply by # of color-choices     3      6      1
                                      ==================
                            to get      6     18      6  ... 30 distinct cubes.
                                      ==================


You might like to try the same type of calculations to get the number of
distinct cubes in 4, 5 & 6 colors.  I got the wrong answers for 4 & 5, too,
by the Joe Yan counting method.  The Polya method is a great boon.

You might try to count the number of distinct octohedra in 1,2,3,4,5,6,7 or 8
colors.  Those from 3 to 6 are hopeless by the Yan method, but reasonable by
Polya.  (Note: for octohedron coloring, it is easier to visualize coloring the
corners of a cube.)

If no-one else posts the answers to the above problems, I may do so later.

Then of course, there are the dodecahedron and icosahedron cases..... (!)

Bill Taylor.         wft@math.canterbury.ac.nz



From: jhardin@gandalf.pnl.gov
Subject: SPOILER: Stick Problem

This concerms the problem:

     Obligatory problem (from Yaglom and Yaglom):  Given a 1 foot stick,
   mark two points on it at random, and then cut the stick at the two
   points.  What is the probability that the three sticks can make a
   triangle?

posted by greg@math.uchicago.edu










OK - I messed this problem up twice now and hope I finally got it right.
One can consider the first cut as being in the first half of the stick.
If it is not,then just turn the stick around. In any event, that makes
the first cut uniform on (0,.5] and the second cut is uniform on (0,1).
Now, in order to be assured that we can construct a triangle with the 
resulting pieces, the longest any one piece may be is one half. So, 
we have

  ¥int_{0}^{.5} ¥int_{.5 - x}^{1-x} .5 dy dx  = 1/8

where the limits for the inside integral (the second cut) are chosen to 
guarantee that the longest piece is less than one half.



OBLIGATORY FOLLOWUP :  Choose three random points on the unit circle. What is
the probability that the resulting triangle defined by these three points
contains the origin? 


- James




From: greg@math.uchicago.edu (Greg Kuperberg)
Subject: Stick problem (spoiler)

I still claim that the answer is 1/4, and here is my explanation:

You mark two points on a stick and that divides the stick into
a left stick, a middle stick, and a right stick.  You get a triangle
if none of the three is longer than half of the stick.  Since it is
impossible for two of the three sticks to be longer than half,
the chance that at least one is longer than half is the sum
of the chances for each piece.  

What is the chance that the left stick is longer than half?  That
happens exactly when both marks are on the right side, 1/4 of the
time.

What is the chance that the right stick is longer than half?
1/4, for the same reason.

What is the chance that the middle stick is longer than half?
That's the hard one.  The conceptual way to derive the answer is
to notice a hidden and subtle symmetry in the problem:  Since we could have
started with a rubber tube in a circle that we break at three points
to get three straight rubber sticks, the middle stick is just as likely
to be long or short as the left or the right stick.  So this probability
is also 1/4, leaving 1/4 for the final answer.

Warning:  Although this argument is valid, it is *dangerous pool*.  The
way I have worded it, I am veering into the "Monty Hall and the three
doors" area of transformations that look like symmetries, but aren't
because of conditioned probabilities.

James Hardin's argument works in principle also, but he set up his
integral incorrectly.  It should have been something like:

Integral from 0 to 1/2 of (Integral from 1/2 to x+1/2 of 2 dy) dx = 1/4

Explanation of the integral:  I am integrating two random variables, x
(the first point), and y (the second point).  Per James Hardin's
prescription of reversing the stick if x is bigger than 1/2, x
is uniformly distributed in the left half of the stick.
y is uniformly distributed over the whole stick.  However,
if y<1/2, then the right substick is too long for a triangle,
and if y>1/2+x, the middle substick is too long.  Finally,
the integrand is 2 dy dx, because the probability density of x
is 2 dx (since x is distributed over an interval of length 1/2)
and the probability density of y is 1 dy.

				Greg


From: Van@cup.portal.com
Subject: Bead problem

J.MCGOWAN15 [Watson]         at 20:00 EDT
 
RE: BEAD PROBLEM

THIS IS THE LAST POST I WILL MAKE ON THAT PROBLEM

                       (The crowd roars its approval!)
                                    +-+-+

DAMN... I KEEP writing ROTATION for ROTATION or REFLECTION!

In one of my last posts the following occurs:

 > "In the case where SUM[ni]>N but some ni are less than N, one must
   actually worry about what sequences, ui, can occur!  (for ni>=N for each
   i, the rotation case is more trouble to check, as one must..."

Of course, it should say that the "REFLECTION case is more trouble to check"!

I suppose that if there were some Freudian psychologist here, he would say
that I must have been frightened by my own "reflection" when I was a child,
which would explain why I keep using the other word (ROTATION) even in places
where "reflection" is correct.

Whether or not such is a valid analysis, I AGAIN apologize for not using
"REFLECTION" when it should have been used (DAMN! maybe such a Freudian would
be right... for it seems I have difficulty simply in using the word!).


From: Van@cup.portal.com
Subject: Bead problem

J.MCGOWAN15 [Watson]         on Genie
 
NOTE on the solution I posted to the bead problem:

Some typos...

Every time I meant so say ROTATION I DID... but half the time when I meant to
say REFLECTION, I said rotation!

For example, the sums for S2,S2' ALL involve the terms in SUM[Ig:g in G] for
reflections in the dihedral group (some of the terminology uses the words
rotations... drats!).

[another error: In discussing the examples, the rotations for the diagramme I
 gave for the square include the rotation A->C->B->D which SHOULD be
 A->C->D->B.]

In discussing the triangle example, I talk about the three rotations and then
say:

  "...the rotations:

  around Cc... Ee and Ff"

These should have said reflections.

In CASE 3, I start with "...G contains the rotations"... this should say
reflections (the difference between cases 1/2 and 3/4 are the inclusion of the
reflections).

Sorry about that... hopefully you can recognize when REFLECTIONS is meant (if
not, I could repost the solution).

                                    +-+-+

I notice that I also used k for two different things.

One... the number of colours available.

Two... (in discussing rotations) the amount by which a rotation acts (that is,
how many steps around the polygon the rotation moves) (a bracelet is invariant
under rotation of amount k if and only if it is invariant under rotation by
amount GCD(k,N)) <sigh>

                                    +-+-+

Some years ago (over 15) Martin Gardner (in Scientific American) covered the
bead problem (with sufficiently many of each bead to create bracelets of any
colour pattern, with no limit based on the number of beads of each colour) and
this appeared (more than 10 years ago) in one of the compilations of his
columns.

                                    +-+-+

I have covered the case where we have n1,n2,..nk of each number of beads and
either each ni is greater than N (so one can create bracelets of any colour
combination with no limits on colours) or SUM[ni]=N (all beads must be used).

For the case where SUM[ni]>=N the problem is much harder... let me only
consider the rotation sum, S1:

S1=SUM[Ig: g a rotation]

Then this is:

S1=SUM[cr*f(N/r):r divides N]

where:

cr=SUM[r!/(ru/N)!:ui<=ni:SUM(ui)=N:ru/N is an integer sequence]

(u means the sequence of non-negative integers, u=(ui,u2,...,uk) and ru/N
means the sequence (r*u1/N,r*u2/N,..,r*uk/N))

(if SUM[ni]=N, then for ui<=ni and SUM[ui]=N, we must have ui=ni, for if u1<n1
(say) then SUM[ui]<n1+n2+..nk=N: this is for the case where SUM[ni]=N... in
this case there is just one choice for ui!]

(we break the sum up into bracelets that used ui of colour i for each
possibility).

NOTE that if ni>=N (for each i, so that we CAN make bracelets of any colours
with no limit due to the number of beads of each colour), then for ANY
sequence of integers, a=a1,a2,..ak with SUM[ai]=r, DEFINE u=Na/r (remember
that N/r is an integer!)... this gives a sequence (ui=N*ai/r) with SUM[ui]=N
and ui<=N<=ni and ui are integers! Thus, if we have sufficiently many of each
colour (ni>=N for each i), every sequence a=ru/N with SUM[ai]=r appears in cr
and cr becomes:

SUM[r!/a!:a1+..+ak=r]=k^r

(by the multinomial expansion mentioned in the first post on the solutions...
the post which used ROTATIONS in places where REFLECTIONS was meant!)

(thus, breaking down the bracelets into the number of each colour recovers the
S1 sum in CASE 1 (lots of each bead) from the S1' in CASE 2!).

In the case where SUM[ni]>N but some ni are less than N, one must actually
worry about what sequences, ui, can occur!

(for ni>=N for each i, the rotation case is more trouble to check, as one must
worry about N being odd/even and various sequences of the form a=m/2 where m
is a modified sequence reflecting the beads chosen for any vertex covered by
the reflection axis in order to show that one can recover the S2 in case three
from the S2' sum in case four by adding the values for possible u=(u1,u2,..uk)
sequences)

[If someone (Van?) posts my solution to the bead problem to Internet, he/she
 may want to post this errata note... about having typed in ROTATION in
 places where REFLECTION is mentioned... and the note about the covering of
 the poblem in Scientific American and the formula for the case where
 SUM[ni]>=N, at least the rotation sum]

If anyone wants me to, I can post the solution again... this time (hopefully)
with corrections so that reflections are correctly noted!
 ------------
Category 5,  Topic 24
Message 492       Wed Jul 21, 1993
J.MCGOWAN15 [Watson]         at 14:37 EDT
 
RE: The bead problem

ONE: David Ratcliffe's solution

Nice, but overkill!

(with P(H) the number whose invariance subgroup IS H, and letting H represent
the subgroup and the order of the subgroup, his formula is:

S'/G

where S' = SUM[H*P(H):H a subgroup of G]

Consider any element in the set S (of elements we permute), let Is be the
number of elements of G which leave s invariant!

It is easy to see that SUM[Ig:g in G] is SUM[Is:s in S] (simply define
w(g,s)=1 if g(s)=s and zero otherwise... summing over g first, and then s
gives SUM[Is], summing over s first and then g gives SUM[Ig] (that the number
of orbits is SUM[Is]/G is trivial once one notices that Is*Os=G where Os is
the size of the orbit of s, and that we get the number of orbits as SUM[1/Os:s
in S]).

To achieve the formula used by Ratcliffe, simply note that if we partition S
into sets according to what their symmetry groups are (that is, if the
elements s and s' have the same set Is=[g:g(s)=s] (not just the same number of
elements, but the same invariance group), then this partitions S so that
SUM[Is]=SUM[Is*P(H):H a subgroup of G] where P(H) is the number of elements
having H as their invariance subgroup and Is is Is for any s having H as its
symmetry group (these all have the same value for s's having the same symmetry
group, H, and the value of Is for s having H as its symmetry group IS H!)...
of course, if s has symmetry group H, then Is is of size H, so we get
SUM[H*P(H):H a subgroup of G].

Again, all these formulas come from the fact that the number of orbits is
SUM[1/Os:s in S] (with Is*Os=G) and either (ala Ratcliffe) partitioning S by
the symmetry groups, or using the change from sums by G first to sums by S
first, ala Polya-Burnside)

[The above has the proof of the Polya-Burnside lemma and the formula used by
Ratcliffe!]

The problem with Ratcliffe's method is that one must look at every SUBGROUP
(not just element!) of G and find the elements with this as the invariance
subgroup (not just invariant under these elements, but invariant under no
others!). The Polya-Burnside version of the sum only demands looking at
elements of G (rather than subgroups) and elements invariant under each (much
easier).

[This is why I call Ratcliffe's version overkill... it involves analysing all
the subgroups of the dihedral group]


One need not analyse the subgroups of G and find out which ones are symmetry
groups of some arrangement! One only needs the Polya-Burnside lemma to handle
all of that (which ones are invariant under each group operation).

He does get the correct result!

                                    +-+-+

TWO: Arthur Rubin's solution

This solution also (as did mine) uses the Polya-Burnside counting lemma, but
he made an arithmetic error, for:

24+180+866250+9465511770=9466378224 (NOT 9,487,237,344)

Dividing this by 48, one gets: 197216213.

His solution is the same as mine, but he does not notice that invariance under
rotation through k is the same as invariance through GCD(k,24) (well, actually
he does, by grouping rotations through 3,9,15 and 21 as having the same Ig as
3... the number of these elements is four, which is PHI(24/3) (the numbers
relatively prime to 24/3 are 1,3,5,7 and, multiplied by 3, these four terms
give the four "k"'s (rotations) equivalent to 3 for invariance studies...
3,9,15 and 21) (I simply used 3 and noted that there were PHI(24/3) rotations
with the same invariance bracelets).

                                    +-+-+

Neither of those solutions give the general formula for the number of
bracelets (nor so detailed a reasoning) as did my post, but both give the same
solution (correct and agreeing with my result, if one corrects the arithmetic
error in Rubin's post).

                                    +-+-+

So, I guess we can be pretty sure that the number of different bracelets in
the problem (24 bead bracelet, 8 of each colour) is in fact:

             197,216,213.

                                    +-+-+

(The above contains the proof of the formula used by Ratcliffe and the Polya-
Burnside lemma, used by Rubin and myself, with a correction to the arithmetic
of Rubin showing that, modulo that arithmetic error, our solutions all agree
on the number of bracelets... 197,216,213.)


From: Van@cup.portal.com
Subject: stick prob.

 S.CHASE7 [Steve]           (Genie)
 
 The twice (random) broken stick has only 0.25 chance of
 making a triangle.  This is a good example of human's
 difficulty in choosing random numbers.

 Steve


From: Van@cup.portal.com
Subject: Probability#1/Monty Hall

J.MCGOWAN15 [Watson]         on Genie
 
RE: A person picks two numbers... randomly gives you one... find a strategy
better than "just guessing" to determine if you have been given the larger or
smaller of the two numbers.

First.... let us forget the first part ["A person picks two numbers]... for
how can one "randomly pick a number"? If this means uniformly distributed from
1 to infinity, then the prob. of picking a number less than x (for any finite
x) is zero!

The picker uses some strategy... forget it... this is JUST a statement to
confuse you!

                                    +-+-+

SO Consider the problem:

HENRY holds a number (x1) (NOT random, a fixed number!) (I don't give a SOU
how he got it!)

JOEY holds a number (x2) (NOT random, a fixed number!) (I don't give a
CONTINENTAL how he got it!)

SALLY picks one of HENRY/JOEY (prob=.5 for any pick), reads the number and
tells it to you... find a strategy to tell if this is the larger of the two
numbers (even Sally will not know whether you are right or not until JOEY and
HENRY show their numbers).

Consider the strategy... I have my own prob. distribution of numbers (prob. of
picking a number less than x being F(x)), and pick a number using it... if the
number SALLY gives me is larger than that, I say it is the larger number... if
less, I say it is the smaller number.

(HECK... I may always pick the number 100, and will say it is the larger if it
is larger than 100, and the smaller if it is smaller than 100... if both
numbers are larger or smaller than 100, this strategy STILL gives me a 50%
chance of being right; BUT IF one number is larger than 100, and one smaller,
then this WILL give the correct result!]

Most would argue that this strategy will only give me a 50% chance of being
right, but they are wrong!

Let a1=min(x1,x2), a2=max(x1,x2)

If I use the strategy above then:

IF Sally gives me a1 (the smaller) I will be right 1-F(a1) percent of the time
(this is PROB(correct|a1=min given)).

IF Sally gives me a2 (the larger) I will be right F(a2) percent of the time
(this is prob(correct|max given)).

As Sally gives me these numbers with prob.=.5, the prob. I am right is:

.5*(1-F(a1))+.5*F(a2)=.5+.5(F(a2)-F(a1))

[PROB(correct|max given)*PROB(max given)+PROB(correct|min given)*PROB(min
given)]

NOTE THAT F(max(x1,x2))-F(min(x1,x2))>=0!

Suppose, for example, I always guess a number from one to one hundred... guess
50, and Sally gives me the number 5000... is it the larger or smaller (well,
the two numbers may be 5000 and 6000)... I say the larger... well, AT WORST
(BECAUSE SALLY CHOOSES THE NUMBERS WITH PROB=.5) my prob. of being correct is
.5 (if I guess numbers from 1-100, and both numbers are larger than 1000, I
WILL only have a prob. of .5 of being right!).

Suppose I always guess the number 1000000... and Sally tells me the number
400... so I guess LOWER... even if the two numbers are both less than 500, I
STILL have a 50% chance of being right!

BUT suppose I guess 100 and the numbers x1 and x2 are 50 and 200... then this
strategy WILL HELP.
 Watson, 
 
 RE: A person picks two numbers... randomly gives you one... find a strategy
better than "just guessing" to determine if you have been given the larger or
smaller of the two numbers.
 
 I can't find fault with your logic, but consider this:
 SALLY has 2 numbers, x1 and x2 (we don't care where she got them, maybe HENRY 
and JOEY gave them to her). 
 She flips a coin (or whatever to get a .5 probability). If she gets heads, 
she shows the lower number. If tails, the higher number.
  So a method of telling whether she has shown the larger or smaller number 
different from .5 is equivalent to predicting a coin flip different from .5, 
and we have already said a coin flip is .5.
 
 Do things change if she doesn't look at the numbers--i.e., doesn't know 
whether she is giving you the greater or smaller number? I don't see how.
 
 Can you explain how this is different from your formulation, or from the 
original statement of the problem. I don't see it.
 =========
 My other argument is that since all numbers are allowed (an infinite range), 
the chance of you picking a number between any 2 numbers is 0, since |x1 - 
x2|/oo = 0. This sounds like your statement 
 
 >how can one "randomly pick a number"? If this means uniformly distributed 
from
1 to infinity, then the prob. of picking a number less than x (for any finite
x) is zero!<
 
 If we extend the problem to include negative numbers, then your problem would 
not arise. But then one could use |x|, and say that for a uniform distribution 
over all reals R the probability of picking a number with absolute value < |x| 
= 0. (If a uniform distribution over all reals R can be given any meaning, 
since the probability of picking a number in any finite interval is again 0, 
i.e., the probability density must be 0.)
 
 But I am getting off track and worrying about how to pick the numbers again.
 ==========
 As I said, you put the problem clearly, and the logic seems faultless, but it 
also seems to be equivalent to predicting a coin flip, as Steve said.
 
 If we allow negative numbers, you could pick your number to be 0, and then 
you would be right whenever 1 number was + and the other -. Assuming "symmetry"
 
about 0, this will happen 1/2 of the time, so you will be right 1/2 + 1/2*1/2 =
 
3/4 of the time.
 
 But if I'm holding 2 numbers in (-oo, +oo), and flip a coin to decide which 
to show you, the large
  Van

The point is NOT how the numbers x1 and x2 are obtained (WHO CARES? IT IS
IMMATERIAL... forget it!)... the point is, IF SALLY picks each with prob.=.5,
this strategy will NOT hurt (on the average) AND SOMETIMES HELPS!

(One may want to use a strategy so that F(a2)-F(a1) is strictly positive for
any a2>a1... say using an exponential or normal distribution, to ensure that
this strategy WILL help)

Anytime you can come up with a strategy which is never worse than some other
strategy (the strategy of "always guess the number is lowest" for example, has
prob=.5 of being correct) and sometimes is better... heck... prefer it!

                                    +-+-+

This also is the analysis of the Monty Hall problem.

Suppose that the doors are numbered 1,2,3 and Monty ALWAYS chooses the largest
number door (not chosen by you and behind which the prize does NOT lie).

Suppose you choose door one, and Monty chooses door three... should you change
doors? It doesn't matter.

Suppose you choose door one, and Monty chooses door two! Should you change
(well, Monty would have chosen door three unless the prize were there, so...
yep... best to change doors!)? YES.

Suppose instead Monty chooses the lowest number door (instead of the highest)
unchosen by you (and without the prize)... you choose door one, he chooses
door two... should you change? Who cares (does not matter).

Suppose Monty chooses door three, should you change (hell, the prize MUST be
behind door two in this case!)? YES!

Suppose the prob. is p that Monty chooses the highest feasible door number
(feasible meaning, the prize is not behind it AND it is not the door you
chose!) and q=1-p that he chooses the lowest feasible door number... should
you switch doors?

IT NEVER HURTS TO SWITCH DOORS AND SOMETIMES HELPS... SO SWITCH DOORS!

                                    +-+-+

The trick in both cases is simply to look at a new strategy which it does not
hurt to employ... and every now and then helps... so use it!

(in analysing the proposed solution to guessing whether one has or has not
 been given the largest number, the first thing to do is see if EVER - with a
 RANDOM (prob=.5 of being given the larger of the two numbers) presentation
 of the two numbers, it will result in a result of less than 50% for guessing
 right. IF NOT, then it is quite useable... if it NEVER is worse than a
 random guess, and SOMETIMES is BETTER, than, prefer it to a random guess)

[This paradox was discussed, I believe, in a Martin Gardner article in
 Scientific American... under the title of the "Game of El???" (I forget the
 title... it was over 10 years ago!)... someone has a list of numbers and
 randomly gives them to you... you win if you say "STOP" when he gives you
 the largest number on the list... in that case the problem was not to find a
 better strategy than random, but to find the BEST strategy of when to
 say "STOP"!]

[The entire justification for the proposed strategy, or switching doors in
 the Monty Hall problem, is that it never hurts... sometimes helps... so use
 it!]
 ------------
Category 5,  Topic 24
Message 495       Wed Jul 21, 1993
J.MCGOWAN15 [Watson]         at 18:15 EDT
 
The prob. problems:

I mentioned that if we have two strategies, S1 and S2 for which (under the
relevant hypotheses) S2 is always at least as good as S1 and sometimes better,
then we should prefer S2.

This is true... the real problem in maximizing strategies is when we find
strategies S1 and S2 and sometimes S1 is better and sometimes S2 is better (in
the case of guessing the largest number, picking your own number and basing
the guess upon whether the number you are told is larger/smaller has at least
prob=.5 of being correct, maybe more! This is better than a random guess).
When sometimes one is better than the other AND VICE VERSA, then one must
start worrying about when each is better.

This makes the problem in the game of El? (cannot remember the name) (Martin
Gardner in Scientific American) (someone has a list of N numbers... you know
N... and starts to read them off to you... say "STOP" when you want to... if
at the largest of the numbers, you win; if not at the largest of the numbers,
you lose... find the optimal strategy of when to say "STOP") much harder...
but when one has one strategy (in the Monty Hall case, switch) which is never
worse than another (not switch) and is sometimes better... there is no
doubt... USE THE ALTERNATE STRATEGY!

(For the Game of El?... I forget the name, I believe the proper strategy is to
let the person tell you N/e numbers... then say "STOP" as soon as he/she tells
you a number larger than all the N/e numbers that he/she first told you!).


From: Van@cup.portal.com
Subject: Probabillity#1

 Watson, 
 
  Thanks for your help with the bead problem--very useful.
 
 I realized when ROTATION meant REFLECTION in your posts.
 
 I will forward some of your posts to iams--the one you requested, the ones on 
the bead problem (except the answer to my question). I will also post the 
Problem of 2 numbers, (x1 < x2, see below). I will try to keep track and let 
you know. I could mail to you (and anyone here) via Internet the same time I 
post to IAMS, so that everyone will know exactly what I post, but I don't edit 
or anything--its your posts exactly (in one case I left out 1 of Steve's 
sentences so as not to upset Ben Tilly, since it was to the whole group.
 
 Ben Tilly (and others) will be glad to see the post on the
 Problem of 2 numbers, (x1 < x2, see below).
 Maybe he will decide I am not an idiot who should not be allowed to post ;-).
 
    "The trouble with being right, is that
 one finds oneself in such questionable company."
out of the rooming house because he made indecent advances.)
 ===========
 RE: A person picks two numbers... randomly gives you one... find a strategy
 better than "just guessing" to determine if you have been given the larger or
 smaller of the two numbers.
 =========
 NOTE: While writing the following, trying to show that it must be a .5 
probability, I convinced myself of the opposite, by considering the following:
 
 If we allow negative numbers (the problem did not specify positive numbers), 
you could pick your number to be 0, and then you would be right whenever 1 
number was + and the other -. Assuming "symmetry" about 0, this will happen 1/2
 
of the time, so you will be right 1/2 + 1/2*1/2 = 3/4 of the time.
 I have thought about this and it must be true (you will be right 3/4 of the 
time).
 
 But if I'm holding 2 numbers in (-oo, +oo), and flip a coin to decide which 
to show you, 
 and tell you that heads --> smaller and tails --> larger, this allows you to 
predict coin flips 3/4 of the time.
 =====
 Again, after thinking about this, it must be that associating the coin flips 
with the numbers gives information about the coin flips.
 =========
 Maybe you can explain this apparent conflict.
 With this last example I have convinced myself, but am still not clear on why 
the argument for probability always = .5 fails.
 ===============
  My problem is that both your argument and the following argument seem 
convincing.
 I can't find fault with your logic, but consider this:
 SALLY has 2 numbers, x1 and x2 (we don't care where she got them, maybe HENRY 
and JOEY gave them to her). 
 She flips a coin (or whatever, to get a .5 probability). If she gets heads, 
she shows the lower number. If tails, the higher number.
  So a method of telling whether she has shown the larger or smaller number 
different from .5 is equivalent to predicting a coin flip different from .5, 
and we have already said a coin flip is .5.
 
 Does it make any difference whether she looks at the numbers and decides at 
random whether to show you the largest or smallest number, or whether she 
doesn't look and shows you x1 or x2, not knowing which is largest? I don't see 
how. Can't she always call x1 the smaller?
 
 Then surely there is no scheme that can give you an advantage in deciding 
whether she showed you x1 or x2. Isn't this the same as if she just labels them
 
x1 and x2 at random, and then asks you which is x1 and x2? Again, there is no 
scheme for you to have an advantage here.
 Do things change if she doesn't look at the numbers--i.e., doesn't know 
whether she is showing you the greater or smaller number? I don't see how.
 
 Can you explain how this is different from your formulation, or from the 
original statement of the problem. 
 Or do you just stand be your original post, and this is just a non-intuitive 
result that is not iterpreted properly as a coin toss?
 ===========
 One more example: (how the numbers are obtained is irrelevant.)
 If only numbers > 0 are allowed,
 suppose that I always show you a 2, and then flip a coin (or whatever, to get 
a .5 probability). If I get heads, the other number is 3 (or any number bigger 
than 2). If tails, the other number is 1 (or any number < 2). So guessing 
whether 2 is the greater or smaller number is equivalent to predicting a coin 
flip.
 
 If negative numbers are allowed, change the 2 to 0, 1 to -1, and 3 to 1.
 
  As I said, you put the problem clearly, and the logic seems faultless, but 
it also seems to be equivalent to predicting a coin flip, as Steve said.
 =========
 What about this? Since all numbers are allowed (an infinite range), the 
chance of you picking a number between any 2 numbers is 0, since |x1 - x2|/oo =
 
0. This sounds like your statement: 
 
 >how can one "randomly pick a number"? If this means uniformly distributed 
from
1 to infinity, then the prob. of picking a number less than x (for any finite
x) is zero!<
 
 If we extend the problem to include negative numbers, your problem would 
still arise. Then one could use |x|, and say that for a uniform distribut