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 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 here.
 ==========
 
 What if we DO worry about how the numbers are picked. Say they are picked at 
random from (-1,1). 
 This won't work since you have the endpoints to guide you (if you are shown 
.9, you will guess its the largest.
 
 ===============
 Sorry for the rambling and thinking out loud. I am confused.
 
  Van


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


Find all solutions of the equation  sqrt(x+4)-sqrt(x-3)+1=0

Enjoy


From: Van@cup.portal.com
Subject: sum and product of 2 numbers in[3,97]

Watson should join the group--he seems to have done many of these in great 
detail.
 ========
 J.MCGOWAN15 [Watson]         on Genie
 
By the way... there was a nice puzzle mentioned on TOPic 19... but if you
haven't seen it... here it is:

Alien walking along a college campus meets two mathematicians and says:

"I am thinking of two numbers (integers) from 3 to 97 (inclusive)"

"Their sum is..." whispers the sum to the first mathematician.

"Their product is..." whispers the product to the second mathematician.

Then he (the alien) beams up...

The first mathematician says:

"Aha... you could NOT know the numbers...."

The second mathematician says:

"You were right... but now I DO know the numbers!"

The first mathematician says:

"Ah... NOW, so do I!"

I guess you can guess the question.... what were the numbers?

(actually, 3 to 100 gives the same answer, but for 3 to 97 there is one
thing... somewhere in it you will have to check that 49 is not prime other
than that I can see no difference)

(Solution up in TOPic 19)

(By the way, does anyone have an algorithm for solving Rubik's 15-puzzle)
===============
Category 5,  Topic 19
Message 5         Thu Aug 13, 1992
J.MCGOWAN15 [Watson]         at 06:54 EDT

RE: The alien who chose numbers between 3 and 97

I was a little too facile about the fact that the numbers from the POSSIBLE
SUM LIST were precisely the possible SUMs that can be derived from the first
statement:

M1 to M2: "You cannot determine the two numbers."

The list is correct... but one must check that one does not get outside
[3,97]...

For example, suppose SUM=3x where x is NOT a prime (we eliminated the 3p
sums)... partitioned as (2x)+x with a corresponding product (2x)*x.

I mentioned that in the product of an even times odd, one can just move the 2
over to get a different factorization... but this is only for (2x)+y where
x<>y! for in x=y,  (2x)*x=x*(2x) is still the same factorization!... but in
this case x<=18 (as 3x<=55) and x is NOT prime so has a prime factor of
<=SQR(18) so there is a factor f<=4 and as x is odd (sum is odd) f<>2, so x
has a factor of f=3!... in this case, move THIS factor from 2x over to x
(2x)*x=(2x/3)*(3x), so we DO get another factorization where 3x<=3*18<97 and
2x/3>=2*3>3!

In another case where one has (2x)+y=SUM (x<>y) and changes (2x)*y to
x*(2y)... what if 2y>97 (y>48)? as 2x is at least 3 and is even AND IS NOT 4
(we handled the case of a partition of 4+x separately by moving a factor of
x), 2x is at least 6, and 2x+y<=55, so y<=49 and y>48... ;this leaves y=49
(for example, suppose the SUM=55... this might be 6+49... could the PROD have
been 6*49 compatible with the first statement... well we cannot change this
product to 3*(2*49)=3*98 as 98>97... BUT in the case of 49, it has a small
factor (7) so 6*49=42*7 is another factorization! Here with 2x+y =SUM...
either we CAN move the 2 over to get a different factorization of (2x)*y or
y=49 in which case (as 2x+y<=55) 2x<=6 (and as 2x>=6, 2x=6 so SUM=55) and y
has a factor of 7, so moving it (f) over, we get (6*7)*(7)... the even and odd
numbers have changed (new factorization) as 6*7=42<97 so even in this case
(2x)*y has another factorization.

Finally in the 4+x category (x not prime) x<=51 so x has a factor <=SQR(51) so
there is a factor of x no larger than 7, and thus 4*x=(4f)*(x/f) has
4x<=28<97.

I think that shows that each of the sums in the LIST are compatible with the
first statement (that is for any partition x+y=SUM where SUM is in the list,
z=x*y has another factorization so that M2 could not have been given a product
with only one factorization permitted and hence M2 could NOT have been able to
determine the numbers solely from the PRODuct).

We have seen that SUM=13 and either PROD=30 or PROD=36 (3,10 or 4,9) are
compatible with the first two statements... so just knowing SUM=13 and the
first two statements, M1 could not determine the numbers and have seen that
SUM=29, PROD=208 (13,16) is compatible with the first two statements and is
the ONLY possible PROD so that the first two statements are true IF SUM=29!

Here is why none of the other possible sums in the list are compatible with
the third statement:


SUM=13=3+10=4+9
       3*10=5*6 but 5+6 not in list
       4*9=8*3=6*6 and 8+3 and 6+6 not in list

SUM=19=3+16=11+8
       3*16=(1)
       8*11=(1)

SUM=25=3+22=8+17
       8*17=(1)
       3*22=33*2 and 35 not in the list.

SUM=31=4+27=5+26
       4*27=12*9=36*3=(1) and 12+9,36+3 NOT in list
       5*26=10*13 and 10+13 not in list

SUM=37=3+34=4+33
       3*34=6*17 and 6+17 not in list
       4*33=12*11=44*3=(1) and 12+11,44+3 not in list

SUM=43=8+31=16+27
       8*31=(1)
       16*27=48*9=(1)

SUM=49=8+41=16+33
       8*41=(1)
       16*33=48*11=(1)

SUM=53=16+37=32+21
       16*37=(1)
       32*21=96*7=(1) and 96+7 not in list

SUM=55=8+47=16+39
       8*47=(1)
       16*39=48*13=(1) and 48+13 not in list

(NOTE there are other possible products in many of the above which are
compatible with the first two statements)

Thus, for example, IF SUM=55 and PROD=8*47 OR SUM=55, PROD=16*39... the first
and second statements would be true... but knowing SUM=55, M1 could not know
the numbers after the two statements (are they 8,47 or 16,39?).

ONLY in the case of SUM=29 would M1 know the numbers after the two statements!

(1) There are other factorizations (x*y) in which both factors (x,y) are
    even... but in this case, the sum=x+y is even and is not in the list!

                                  Addendum:

Why not numbers between 3 and 100 inclusive?

We still eliminate p+x where p is a prime greater than 50 and x is at least
three (but 53 is the first prime over 50 AND over 48!)... still eliminate 3p
and 4+p for primes and p+q for primes p and q (so by Goldbach's conjecture,
all the evens except for a few large ones, which are caught by the p+x)... so
we wind up with the same allowed sum list.

Still to check that all these sums are allowed, we check for extra
factorizations... the only difference seems to be in a sum of the form (2x)+y
where x<>y and the product (2x)*y can be rewritten by moving the 2 to the
other side as x*(2y)... we saw that we had to explicitly check 6*49 (where
6+49=55 is an allowed sum) since 3*98 had a term greater than 97 (for numbers
bounded by 97, we noticed that while 3*98 was no good, 42*7=6*49!). Is the
only difference between a limit of 97 and a limit of 100, that in the former
one must explicitly test 6*49 in order to have a correct proof that the
numbers are 13 and 16?

(This has been reposted, since the last post was only up one night before
being archived... and some who are interested in the solution of the problem
in message 889 may have missed this second part to the solution).
=============
Category 5,  Topic 19
Message 16        Sun Aug 16, 1992
J.MCGOWAN15 [Watson]         at 12:38 EDT

As someone was interested in the full solution to the Alien puzzle, I am
reposting the puzzle and the first part of the solution... the second part
(the grungy details) has been posted uptopic (the puzzle and first part of the
solution are in the archived-ZIP files of messages 1-933 as well)

The puzzle is as follows:


Alien meets two mathematicians and says:

"Gentlemen, I am thinking of two numbers (integers) between 3 and 97
inclusive."

"The SUM of the numbers is:..." (whispers the result to the first
mathematician)

"The PRODuct of the numbers is:..." (whispers the result to the second
mathematician)

The alien then vanishes in a puff of smoke.

(heck if he vanishes in a puff of smoke, he may have escaped from ZorkII)

The first mathematician says:(first statement)

"Ah... you cannot possibly know the numbers!"

The second mathematician says:(second statement)

"Ah... you were right, but now I DO know them..."

The first mathematician says:(third statement)

"Ah... now I know them TOO!"

Question:

What were the two numbers?

                     Description of the Solution follows

(If you want to work on the problem yourself, do NOT read the following!)

The trick is as follows, for a possible SUM given the first mathematician and
a PRODuct given the second we say the sum and product are compatible.

For example, SUM=8, PROD=15 are compatible (the numbers may have been 3,5) but
SUM=9, PROD=15 are NOT (if the PROD is 15, the factors must both be odd, so
the SUM must be even!).

Consider the possible values that one could have had for SUM... IF ANY
compatible product has ONLY one factorization (in numbers from 3 to 97) then
that SUM is NOT compatible with the first statement! (e.g. SUM=8 is not
compatible with the first statement, for then the PROD MAY have been 15=3*5,
so that with such a SUM the second mathematician MAY have known the two
numbers before the first mathematician speaks). Eliminating such terms we have
a list of possible sums (compatible with the first statement) and the first
statement is equivalent to the statement that the SUM is in this list!

For example, SUM=13 IS in this list.

Now consider the second mathematician, he must have a compatible product so
that ONCE HE IS TOLD THE SUM IS FROM THE LISTING (which he, too, can obtain as
done in part one of the solution, which is the message following this), THERE
IS ONLY ONE POSSIBLE FACTORIZATION WHOSE SUM IS IN THE LIST.

The product 30 is compatible with SUM=13 (3+10=13,3*10=30)... and if you look
at every other factorization of 30 (eg.g 5*6=30) the corresponding SUM
(5+6=11) is NOT in the list of possible sums... so that AFTER being told the
sum is in the list, IF the poduct were 30, the second mathematician would know
the numbers... this pair of PROD,SUM IS compatible with the first two
statements.

(a pair of SUM,PROD is compatible with the first two statements if SUM is in
the allowed SUM list and this is the only sum compatible with PROD which IS in
the list)

But SUM=13, PROD=36 (numbers being 4 and 9) IS ALSO COMPATIBLE WITH THE FIRST
TWO STATEMENTS!

So, IF SUM=13, the first mathematician could NOT truthfully have made the
third statement (he would not know if the numbers were 3,10 or 4,9).

The SUM=29, PROD=208 has the property that it is compatible with the first two
statements and for SUM=29, 208 IS THE ONLY COMPATIBLE PRODUCT which has ONLY
ONE compatible sum in the allowed sum list! SO that IF SUM=29 the three
statements could be made (once the second statement is made, the first
mathematician, knowing SUM=29, would know that ONLY a product of 208 would
allow the second statement!)... in fact SUM=29 is the ONLY sum for which there
is ONLY one product compatible with the first two statements... that is the
ONLY sum for which, after the first two statements, the first mathematician
would know the SUM and PRODuct (or equivalently, the two numbers).

The next post (part one of the solution) is how to obtain the compatible sum
list... a listing of such and a check that for SUM=29, 208 is the only
compatible product which has exactly one compatible sum in the allowed sum
list!

The uptopic post post is part two of the solution (part one does not give ALL
the details of obtaining the possible sum list, just most of the material,
subject to some checks that must be made and are made in the uptopic-part 2).
 ------------
Category 5,  Topic 19
Message 17        Sun Aug 16, 1992
J.MCGOWAN15 [Watson]         at 12:56 EDT

RE: The alien who chose numbers between 3 and 97

I believe the two numbers are 13 and 16.

(Do NOT read the rest of this message unless you want to see the solution)

SOLUTION:

Consider SUM, the sum given the first mathematician.

Can it be the sum of two primes between 3 and 97, for example 8=3+5?

NO... for IF all the first mathematician (called from hereon M1) knows is that
the SUM is 8, M2 MIGHT have been given a PRODuct of 15 (the product of the two
primes) and so could immediately factor it! And M1 tells us that he has enough
info (in the SUM) to prevent this.

Eliminate all numbers from 6 to 194=2*97 which are sums of two primes (not
necessarily distinct... heck the alien could have chosen 5 and 5!) by
Goldbach's conjecture (all even numbers greater than 4 are the sums of two odd
primes) all the small even numbers are eliminated (because we only get to use
primes up to 97, we do not eliminate all evens). We are left with odd numbers
and:

 174,182,184,188,190 and 192 (we'll get rid of all large numbers in a minute)

So (except for these few large numbers) the sum cannot be even!

Now, can the sum be 3p where p is a prime less than 49?

For example, can the sum be 3*7?

IF so (sum is 21) IT may have happened that the alien gave M2 the product 98
(2p^2) (if the numbers were 7 and 14).

Just from M1's SUM, he cannot declare that the product is NOT 98 (2p+p) which
can only be factored (no factor of just two, as factors are larger than two)
7*14, that is 2p*p (here, we CAN determine the numbers if the PROD is given as
2p^2 and 2p and p are less than 97...as p*2p).

So by M1's statement we eliminate sums of the form 3p, p a prime<49.

Can the SUM be of the form 4+p where p is a prime? (say 4+19=23)... in this
case, M1 does NOT know that 76 (4p) was NOT given as the product...and if it
were, the only allowed factors are 4*p (no factor of 2!) NO!

So eliminate these from the possible SUMs.

Now consider, can the sum be of the form p+x where p is a prime greater than
48 and x is a number (not necessarily prime) at least equal to three?

E.g. 76=61+15.. in this case M1 does NOT know (at the start) that 915 (=px)
wasn't given as the product... suppose it were... then 915=61*3*5 and how are
we going to factor as two numbers... one must have a factor of 61 AND STILL BE
LESS THAN 98! So it MUST be 61 and if we were only told a product of 915, we
could determine the numbers (if our PROD=px where p is prime and 2p>97, then
we have the numbers... so our sum must not allow such)

This eliminates the large numbers in one fell swoop!

Eliminate all SUM values which M1's statement indicates to get the following
as possible values for SUM

 13,19,25,29,31,37,43,49,53,55

We must check that no more can be eliminated, that is... if one writes a
SUM=x+y then the number z=x*y has another factorization (so no allowed PROD
from M1's statement permits M2 to determine the numbers without some
additional info).

Consider say, 19 = 3+16
                   4+15
                   5+14
                   6+13
                   ....
                   9+10

where I have written the smaller value on the left.

IF the value on the left is ODD, then as the sum is odd, the value on the
right is even and we have another factorization (move a two over)... eg. the
product 5*14 could have been written 10*7... so M1 knows that with SUM=19,
none of the allowed products (well, 5*14 anyway) would give the game away
(move a two to get a different factorization) (we also have to worry about the
case where the even number is 2*m and the odd number is m! for then the
movement of the two changes (2m)*m to m*(2m)... the same factorization, but
see the second part of the solution uptopic for handling this).

IF the value on the left is EVEN and not equal to four, we can move a factor
of two over to the right to get another factorization. If the value on the
left IS four, we have eliminated 4+p sums, so the factor on the right is NOT
prime and we can move one of ITS factors over!

One must check that one never gets numbers outside [3,97] and really only has
to check the smallest and a couple of the largest possible sums to make sure
it all works (in particular, one must worry about 6+49, since if we move the
two over in 6*49, we get 3*98 and 98>97... but see the second part of the
solution uptopic).

Thus we canNOT eliminate ANY more of the possible SUMS, and the above sums are
precisely those in accord with M1's statement.

Now, from M1's statement, BOTH M1 and M2 know that the sum is from the above
list (M1 knows it exactly, and M2 knows the PROD exactly).

What if the sum is 13?

  13=3+10
     4+9

Suppose M1 were given a sum of 13 and M2 a PROD of 30.

 30=3*10=5*6 (all factorizations for numbers
              between 3 and 97)


M2 finds out that the sum (from M1's first statment) is in the above list...
he does NOT know the sum, but knows the product is 30... could the factors be
5 and 6? The sum would be 11, which is NOT in the list! So, the factors could
NOT be 5 and 6, but MUST be 3 and 10!

This is compatible with the first two statements.

But suppose M1 is told SUM=13 and M2 that PROD=36=4*9=12*3=6*6

M2 does NOT know the sum, but DOES know that it is from the list and knows the
PROD... could it be 12*3? NO 12+3 is NOT in the list, nor 6+6 (or any even or
large) number! So the numbers must be 4 and 9.

Again, this is compatible with the first two statements.

Could the SUM=13 then?

Both (3,10) and (4,9) agree with M1's knowledge of the SUM and with M2's
statement that there is a combination that tells him the result... so HOW
could the third statement be true? M1 still does NOT know which it is! (IF
SUM=13, then after the first two statements the numbers could be (3,10) or
(4,9) or even other possibles... so the third statement would not be true)

To finish the problem, one must look at each of the possible SUMs, each of the
possible ways of partitioning as a sum... (x+y) look at factorizations of x*y
and find a SUM so that precisely one of the partitions allows M2 to determine
the numbers.

In our case, SUM=29 we have:

Cases:
  3+26 and 3*26=6*13
  4+25 and 4*25=5*20=(1)
  5+24 and 5*24=8*15=40*3=(1)
  6+23 and 6*23=3*46
  7+22 and 7*22=14*11
  8+21 and 8*21=24*7=56*3=(1)
  9+20 and 9*20=60*3=12*15=36*5=4*45=(1)
  10+19 and 10*19=5*38
  11+18 and 11*18=22*9=6*33=66*3
  12+17 and 12*17=4*51=68*3=(1)
  13+16 and 13*16=(1)
  14+15 and 14*15=6*35=10*21

and all of:
 6+13,5+20,40+3,3+46,14+11,24+7,4+45,38+5,22+9,4+51 and 10+21 yield sums which
ARE in the SUM possibilities.

(for example, IF SUM=29 and PROD=78, M2 would NOT know, after the first
statement whether the numbers were 3,26 or 6,19 and so the second statement
would not be true!)

 (1) There are other factorizations where both factors are even... but this
     yields an even sum which is not an allowed possibility for SUM due to
     M1's statement!

So Suppose the SUM were 29... then ONLY if the factors are 16*13 (PROD=208)
could M2 declare that HAVING heard M1's statement (and calculated the list of
possible SUMS) could he declare the sums (and M1 knowing the SUM can do so now
too)... but M2 could NOT determine the factors as 13*16 from the product alone
(why not 26*8?) until M1 gave him enough information to know that, with the
product of 208, the sum MUST be odd (M1's original statement led us to
eliminate even sums!)

Part two of the solution (posted uptopic) shows that this is the ONLY SUM for
which precisely ONE partition of the SUM permits M2 (using the SUM allowed
table) to determine the factors!

(I REALLLYYY!!!! hope I didn't make any arithmetic errors, as I did this on a
hand calculator and paper rather than a computer)


From: sstrklnd@oyster.smcm.edu
Subject: Re: POD (SPOILER?)

---SPOILER?



















 	Find all solutions to sqrt(x+4)-sqrt(x-3)+1=0.
	Is there a type in this one??  There are no real-valued  
solutions to his equation.  To have a real-valued solution, x must be  
greater than or equal to 3.  In that case, sqrt(x+4)>sqrt(x-3) and  
thus the equation has no solutions.
					-Sue-
********************************************************
Susan R. Strickland              * "If at first        *
St. Mary's College of Maryland   * you do succeed -    *
St. Mary's City, MD 20686        * try to hide         *
sstrklnd@oyster.smcm.edu         * your astonishment." *
********************************************************



From: t-davidw@microsoft.com
Subject: Re: parking problem (corrections to corrections to...)


     Well, I'm now thinking that neither of my solutions to the
parking problem on the Japanese Olympiad were quite right.  *sigh*
(Thanks to van@cup.portal.com for pointing this out, by the way.)
I agree now that the two empty spaces must be adjacent (which I
screwed up in my second try).  But my original post made a different
mistake.  So let me start over from the beginning and hope I come a
little bit closer on this _third_ attempt.  :-(

     Let's look first at the number of ways to place 2 trucks
(which are indistinguishable!) in n parking spaces: I claim it is
C(n-2,2) = (n-2) choose 2.  In case that's not obvious to you, I'll
try to justify it some.  Let's suppose we've already placed the
left-most truck, and there are x empty spaces to the right of it.
Then we can place the right-most truck in any of x-1 ways.  Then,
summing over the possible placements of the leftmost truck, I get
Sum_{x=2}^{n-2} {x-1} = Sum_{y=1}^{n-3} y = C(n-2,2).

     Ok, now how many ways are there to place 3 (indistinguishable!)
trucks in n parking spaces?  I say the answer is C(n-3,3).  This
should be much less obvious, so I'll attempt to back up my statement.
Again suppose for the moment we've already placed the left-most
truck, and there are x empty spaces to the right of it.  Then we
can place the middle and right-most trucks in any of C(x-2,2) ways.
Summing over the possible placements of the left-most truck, I get
Sum_{x=4}^{n-2} C(x-2,2) = Sum_{y=2}^{n-4} C(y,2) = C(n-3,3).

     In fact, I think by an induction argument one can show
that the number of ways to place m (indistinguishable) trucks in
n parking spaces is C(n-m,m).

     Ok, so back to the problem at hand.  I'm gonna place 3
indistinguishable "double-width-objects" in the 12 parking spaces,
which I can do in C(12-3,3) = C(9,3) ways.  Then I'll distinguish
one of them and call it "two adjacent empty parking spaces" (I'll
call the other two objects "trucks").  This gives me a total of
C(9,3) * 3 = 252 ways to place 2 indistinguishable trucks and 2
adjacent empty parking spaces among a total of 12 parking spaces.
But now I only have 6 spaces left over, and I must place all six
(indistinguishable) cars in those 6 spaces - which there's only 1
way to do!

     So my latest answer to the problem is 252.

     By the way I've assumed throughout that you couldn't tell
the trucks apart.  (Same with the cars.)  If you assume that all
all the trucks and cars have different license plates, for instance,
then the number of ways to park them goes up to C(9,3) * 3! * 6!,
which is just 9!.

     Phew.  Let's hope I've gotten it right this time - I've
already got two strikes against me... :-)

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


From: dolan@prep.net (Daryl Dolan)

SPOILER





























solution to sqrt(x+4) - sqrt(x-3) + 1 = 0 ...
try to follow along.

if anyone else got a different answer, i'd like to see it.


sqr(x+4) - sqr(x-3) + 1 = 0

               sqr(x+4) = sqr(x-3) - 1

           (sqr(x+4))^2 = (sqr(x-3) - 1)^2

                  x + 4 = (sqr(x-3))^2 - 2sqr(x-3) + 1

                  x + 4 = (x-3) - 2sqr(x-3) + 1

                  x + 4 = x - 2 - 2sqr(x-3)
 
                      6 = -2sqr(x-3)

                     -3 = sqr(x-3)

                 (-3)^2 = (sqr(x-3))^2

                      9 = x - 3

                     12 = x

no applause, really.

Daryl


From: mantell@ams.sunysb.edu (Abraham Mantell)
Subject: x<>12


x=12 does not work!!!

Abe




From: t-davidw@microsoft.com
Subject: Re: Probability#1


     Ack!  This thread seems to go on and on, and I really wish I
could reply by email, but I have NO idea how to.  Sorry.  :-(

Someone somewhere wrote something like this some time ago:
>
>  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.
>

     Nope.  It's equivalent to predicting a coin flip *given* some
information about the coin flip.  It's not equivalent to predicting
a coin flip with no information.  With no information, your expected
chance at predicting a coin flip correctly is indeed .5.  But if I
give you some information about the coin flip, you can increase your
chances of guessing correctly.  In this case, knowing the number Sally
selected with the coin toss gives you some information about the coin
toss.

     Consider an exaggerated case of your example.  x1=10, x2=20.
Sally flips a coin and gives you 10 if she got heads, or 20 if she got
tails.  Let's say you fortuitously decide you like the number 15, and
decide to respond that the number you received was smaller if she gives
you something less than 15, or to respond that the number you received
was higher if she gives you something larger than 15.  Now, with what
probability of success can you "predict" the coin flip after she tells
you one of her two numbers?  It's 1.0, of course, in this case!  You
can "predict" the coin flip every time.

     This is, in effect, a conditional probability.  You're asking
why Pr{Sally got heads | Sally shows you x} != Pr{Sally got heads}.  In
this case,

Pr{Sally got heads} = 0.5, and
Pr{Sally got heads | Sally shows you 10} =
  Pr{Sally got heads AND Sally shows you 10} / Pr{Sally shows you 10} =
  0.5 / 0.5 = 1.0, and
Pr{Sally got heads | Sally shows you 20} =
  Pr{Sally got heads AND Sally shows you 20} / Pr{Sally shows you 20} =
  0 / 0.5 = 0.

     Did that make any sense?

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


From: Android <benjie@quack.kfu.com>
Subject: Mail Server Added!


procmail was installed at my place, so I added some new feature.  Please read
the following FAQ.  Small discussion lists are avilable if anyone think it is
useful (but it has to be small).

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

INFO - Internet Amateur Mathematics Society - 7/22/93

I.  Intro

Internet Amateur Mathematics Society is an internet based math club
for discussing math and math related topics, problems and puzzles.  We
have a mailing-list at IAMS@quack.kfu.com.  Some of the features of
the society are

	- A mailing-list for problems and discussions
	- finger benjie@quack.kfu.com  for the latest problems
	- Participating in our math contests
	- Participating in the Problem of the Day/Week activities
	- Mail server for getting the latest problems

and more ......


======================================================
II.  Mailing List/Mail Server/Finger Access/FTP Access

Mailing List				IAMS@quack.kfu.com

Mail Server		

   -- To obtain the latest problem(s) (providing service to those who don't 
      have finger access):  email  iams-request@quack.kfu.com  with PODS on 
      the subject line.  

   -- To obtain this file:  email  iams-request@quack.kfu.com  with HELP on
      the subject line.

   -- To obtain the solution to last contest problem: email  
      iams-request@quack.kfu.com   with SOLUTION on the subject line.

Finger Access (The latest POD/POW(s)):    finger benjie@quack.kfu.com

FTP Access: 	The old newsletters/posts/digests are stored at
		princeton.edu in /pub/iams.  If you don't have ftp
		access, email me, and I will be happy to do the dl for
		you.

I could be reached at	   benjie@quack.kfu.com   or
		           benjie@wales%hip-hop.suvl.ca.us 


=============
III. Contests

Yes, we have contests every other month or so.  I run them, and there
are no actual prizes.  All problems could be solved with no more than
a standard high school mathematics background, but most of them
require considerably more ingenuity.  Don't let this scare you off
though, if you try, you are a winner. For information on the current
contest, email me.


====================
IV.  Discussions etc.

Feel free to post questions, articles, and puzzles.  That's why we are
here.  Keep the good discussions.  Once in a while I will post a POD
(Problem of the Day).

To post solutions to problems or puzzles, please put a SPOILER sign in
the subject line.  Do NOT post solutions to contest questions.

Articles for iams should be written in a self-contained manner, i.e.
that it'll be possible to understand them without looking to any other
sources.


=========================
V.    How to post to IAMS

Do "mail IAMS@quack.kfu.com".  When you try to reply a message,
hitting "r" (in whatever mail software you use) will send your message
to the sender of the original message only.  To do a follow-up, add
IAMS@quack.kfu.com on the Cc: line.

When responding to someones post, please do write explicitly what
you're responding to; e.g. when solving someones problem, please
restate it; when proving someone's argument wrong, please state the
relevant part; etc.


=============
VI.   Credits

David Wagner helped me on storing newsletters and digests, as well as
many other things (Thanks, Dave).  I am still looking for a telnet
site for IAMS



From: Van@cup.portal.com
Subject: Prob#1 (x<y)

 I posted a letter about 2 numbers x < y to the wrong place. (It was meant to 
go to Watson on Genie). 
 It wasn't finshed, and was full of mistakes and confusion anyway--please 
ignore it.
 
 I apologize for any personal remarks.
 
 van@cup.portal.com      Van


From: David Michael Tuller <tulled@rpi.edu>
Subject: Function puzzle‾.




From: David Michael Tuller <tulled@rpi.edu>
Subject: Function puzzle




From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Pi Mu Epsilon Problems



Pi Mu Epsilon Volume 7 No.1
Fall 1979

453.  Proposed by Jack Garfunkel, Queens College, Flushing, New York.
Given two intersecting lines and a circle tangent to each of them,
construct a square having two of its vertices on the circumference of the
circle and the other two on the intersecting lines.

454.  Proposed by Marian Haste, Reno, Nevada.
The point within a triangle whose combined distances to the vertices is a
minimum is (or should be) known as the Fermat-Torricelli point,
designated by T.  In a triangle ABC, if AT, BT, CT form a geometric
progression with a common ratio of 2, find the angles of the triangle.  

455.  Proposed by Kenneth M.  Wilke, Topeka, Kansas.  
Young Leslie Morley noticed that the perimeter of a 6 x 4 rectangle
equals the area of a 2 x 10 rectangle while the area of the 6 x 4
rectangle equals the perimeter of  the 2 x 10 rectangle also.  Show that
there are an infinite number of pairs of rectangles related in the same
way and find all pairs of such rectangles whose sides are integers.



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



Round 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:
Part 1

		x^4 + 64 = x^4 + 16x^2 + 64 - 16x^2
		         = (x^2 + 8)^2 - (4x)^2
		         = (x^2 + 4x + 8)(x^2 - 4x + 8)


Part 2

	Since a and b has to be odd integers,
		a = 1,3,5,7  mod 8   or  
		a = 1,3,-3,-1  mod 8
	Same thing goes for b,
		b = 1,3,-3,-1  mod 8

	Therefore,  a^2 = 1, 9 mod 8  or  a^2 = 1 mod 8
		    b^2 = 1, 9 mod 8  or  b^2 = 1 mod 8

	So a^2 - b^2 = 1 - 1 mod 8 = 0 mod 8  
	Therefore, 8 divides all a^2 - b^2 for odd positive a, b.  
	
	Since a and b are positive, the smallest combination would
	be 1 and 3.  But 3^2 - 1^2 = 8.  Therefore 8 is the largest
	integer that divides all a^2-b^2 for odd positive a and b.


Correct Solutions Were Sent In By

tulled@rpi.edu
radcliff@csd4.csd.uwm.edu
algebra@leland.Stanford.EDU 
alanm@efi.com   
Benjamin.J.Tilly@Dartmouth.EDU
martino@rob.csata.it 
mau@beatles.cselt.stet.it
c0465193@techst02.technion.ac.il
jhardin@gandalf.pnl.gov
sstrklnd@oyster.smcm.edu


Congrats!

Benjie


From: Android <benjie@quack.kfu.com>
Subject: SPOILER -- SOLUTION TO DICE POD -- SPOILER


SPOILER

























SPOILER


Here are the Bradley Efron's Nontransitive Dice   layout

   0              3                  2                5
 4 0 4          3 3 3              2 2 2            1 1 1
   4              3                  6                5
   4              3                  6                5


Try it out.  

Enjoy

Benjie


From: Android <benjie@quack.kfu.com>
Subject: Round 8 Contest 2


Here is the last round/problem of contest #2.  I personally hope that
everyone has enjoyed the contest problems.  Please email me your
feelings about these problems, too hard?  too easy?  good?  or bad?
All suggestions are welcome.  Email me your ideal questions as well, I
am running out of contest problems (to submit a contest problem, email
it to me only!).  What do you think about the contest format?  Is it
good?  If not, email me your suggestions.

Enjoy the problem, and happy mathing,

Benjie
P.S.:  If you missed it, the solutions to the last contest problem is
available from the mail server iams-request.  Email iams-request with
SOLUTION at the subject line.

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

For how many paths consisting of a sequence of horizontal and/or
vertical line segments, with each segment connecting a pair of
adjacent letters in the diagram below, is the word CONTEST spelled out
as the path is traversed from the beginning to end?


                         C
                        COC
                       CONOC
                      CONTNOC
                     CONTETNOC
                    CONTESETNOC
                   CONTESTSETNOC



From: "David Michael Tuller" <tulled@rpi.edu>
Subject: Function Puzzle (last try)

This is the absolute last time that I will try to mail this. Anyone who
can help me figure out how to use the mail command on unix please let
me know.

I am thinking of a function that maps the integers to the integers and
follows the following 2 rules:

1. f(f(f(x)))=x

2. f(f(x)+1)=x+1

What is my function?

David M. Tuller

tulled@rpi.edu



From: josephy@ee.ubc.ca (joseph yan)
Subject: Function Puzzle --- Spoiler

Spoiler alert for function problem (this may not have gotten through
the first time cuz' I sent it to iams@quack.kfu.edu):








































> I am thinking of a function that maps the integers to the integers and
> follows the following 2 rules:
> 
> 1. f(f(f(x)))=x
> 
> 2. f(f(x)+1)=x+1
> 
> What is my function?
> 
> David M. Tuller
> 
> tulled@rpi.edu


This seems too easy...the answer is:

f(x)=x

(ie:  it is the identity function).

This solution seems valid to me...although I don't know about uniqueness.


-----------------------------------------------------------
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: "David Michael Tuller" <tulled@rpi.edu>
Subject: function puzzle correction

I forgot one thing about the function puzzle. You have to find all
functions and prove that there are no others.

David M. Tuller

tulled@rpi.edu



From: ramana@mgv01.svl.cdc.com
Subject: Math. basis for a puzzle


Let us consider the following problem:

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, and
iii) sum of cubes of numbers in A = sum of cubes of numbers in B


The solution is A = {1,4,6,7,10,11,13,16}
                B = {2,3,5,8,9,12,14,15}

Let X+k be a set formed by adding k to all elements of X.
Then A+k and B+k have the property of satisfying i,ii and iii.
That means, any 16 numbers in A.P can be partioned in such a way to
satisfy i,ii and iii.

How do we arrive at the above solution without using a computer?

By the preceding discussion,


        B1 = B-1 = {1,2,4,7,8,11,13,14}

have the property of satisfying i,ii and iii.
Notice that all numbers of A1 have even number of 1's in binary and
all numbers of B1 have odd number of 1's in binary. Essentially the
above partition is a partition based on parity.

Observation:


groups A and B (each consisting of 2^n elements) satisfies

 sum of kth powers of elements of A = sum of kth powers of elements of B

for k=1,2,...,n. (The above puzzle is a special case n=3).


The above observation also holds for any radix. In radix r we will have
r groups.

Infact,

That means, any 16 numbers in A.P can be partioned in such a way to
r^n elements) such that sum of kth powers of all r groups is same (k=1,2,...,n)

Finding such groups with minimal number of elements (less than r^n) appears to
be more difficult!

ALL THIS APPEARS TO BE INTERESTING. IS IT A CONSEQUENCE OF A SIMPLE THEOREM OF
NUMBER THEORY? HOW DO I PROVE THIS?

Thanks in advance for any clues,

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


From: David Michael Tuller <tulled@rpi.edu>
Subject: Function Puzzle




From: kubo@math.harvard.edu (Tal Kubo)
Subject: partition of 16-element progression


Someone posted a solution to the 16-element progression problem and asked
if it could be generalized.  It can be done for a 2^n-element progression
and polynomials of degree less than  n, by partitioning according to whether
the number of 1's in the binary expansion of position in the progression is
even or odd.  This follows from the formal identity
 
  (I-T)(I-T^2)(I-T^4)(I-T^8).... (I-T^2^(n-1)) f(x) = 0,

valid for polynomials  f(x) of degree < n,  where  I is the identity
map on polynomials  p(x)--->p(x),  and   T is the translation map
sending  p(x)--->p(x+1).

(Because each I-T^k  lowers the degree, etc)



From: a_rubin@dsg4.dse.beckman.com (arthur rubin)
Subject: Re: Function Puzzle (SPOILER)

Problem:  find all integer functions such that:

1. f(f(f(x)))=x

2. f(f(x)+1)=x+1
(Solution below):
































Assume:

2. f(f(x)+1)=x+1

Then:

3. f(x)=y -> f(y+1)=x+1 (rewriting 2.)

4. f(x)=y -> f(y+1)=x+1 -> f(x+2)=y+2 (using 3. twice)

Using 4 repeatedly, we get that f(x)-x depends only on whether x is odd or
even.

Let y=f(x).  If y-x is odd, then y+1 and x have the same parity, but
f(y+1)-(y+1)=(x+1)-(y+1) = x-y, not equal to f(x)-x = y-x, a contradiction.

Hence f(0) = 2n for some integer n, and it follows from using 3. repeatedly
that:

f(2m) = 2m+2n
f(2m+1) = 2m-2n

These all satisfy 2., but f(f(f(0)))=6n, so if 1. is to be satisfied, n=0,
and f is the identity function.



From: vhansen@ipf.bau-verm.uni-karlsruhe.de (Wolfgang von Hansen)
Subject: Re: Function Puzzle dfAA08247 dfAA08895 dfAA09415 dfAA10207 dfAA10566 dfAA11937 dfAA12581 dfAA12733 dfAA13413 dfAA14483 dfAA15076 dfAA15411 dfAA20550 dfAA21611 dfAA24045 qfAA08247 qfAA08895 qfAA09415 qfAA10207 qfAA10566 qfAA11937 qfAA12581 qfAA12733 qfAA13413 qfAA14483 qfAA15076 qfAA15411 qfAA20550 qfAA21611 qfAA24045 xfAA24045 SPOILER dfAA08247 dfAA08895 dfAA09415 dfAA10207 dfAA10566 dfAA11937 dfAA12581 dfAA12733 dfAA13413 dfAA14483 dfAA15076 dfAA15411 dfAA20550 dfAA21611 dfAA24045 qfAA08247 qfAA08895 qfAA09415 qfAA10207 qfAA10566 qfAA11937 qfAA12581 qfAA12733 qfAA13413 qfAA14483 qfAA15076 qfAA15411 qfAA20550 qfAA21611 qfAA24045 xfAA24045

> I am thinking of a function that maps the integers to the integers and
> follows the following 2 rules:
> 
> 1. f(f(f(x)))=x
> 
> 2. f(f(x)+1)=x+1
> 
> What is my function?

f(x) = x

Wolfgang


From: Van@cup.portal.com
Subject: Watson's address

 Any member of IAMS who wants to discuss Watson's posts (which I forwarded to 
IAMS), can send mail to him directly. His address is
 
 J.MCGOWAN15@genie.geis.com
 
 (He is not an IAMS member, so he only sees what I forward to Genie).
 
 Please send anything for other Genie people to me and I will post it. If you 
want to correspond with them via 1-1 email, please ask me to forward the 
request to see if its OK. (One person asked me not to give out his GE Mail 
address).
 
 van@cup.portal.com                Van


From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Spider on the n-cube


What is the length of the shortest path in the 2-skeleton of
a unit n-cube which connects two opposite vertices?

This question was discussed on this list several weeks ago.
We concluded that the length is n/sqrt(2) if n is even.
If n is odd, then there is a path of length (n-3)/sqrt(2) + sqrt(5),
and it was conjectured that this is minimal.

Unfortunately, this conjecture is false.
I believe that I can prove the following:

  If n is odd, then there is a path of length sqrt((n^2 + 1) / 2)
  joining opposite vertices of the 2-skeleton of a unit n-cube, and 
  there is no shorter path with this property.

I leave this as a challenge to you the reader, because I don't want
to write up the proof.  I will post a solution in a week if nobody
else does, and if anybody is still interested.

Dave Racliffe
radcliff@csd4.csd.uwm.edu

 





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


Here is one I can't solve.

Let S={1,11,31,51,71} and suppose {a_n} be a sequence of numbers satisfying the following conditions (1),(2),(3):

	(1) a_1 is an element of S
	(2) (a_(n+1) - 1)/(a_n + 1) is an element of S.
	(3) There exists a positive number n <= 10 with a_n = 1993
List up a_4 for all such sequence {a_n}


I don't think it's possible (please point out if I am wrong) because from
two, a_n - 1 must be a multiple of one of the elements of S, which means 
1993-1=1992 is a multiple of one of the elements of S.  But 1992 is not
a multiple of 11 nor 31 nor 51 nor 71.  And 1 wouldn't work because it
is too small for us to get to 1993.

What do you guys think?

Benjie


From: t-davidw@microsoft.com
Subject: Two Questions


     Ok, I've been thinking a little about Benjie's earlier
post where he was trying to look at the relationship between the
roots of a polynomial and it's derivative.  Some experimenting
has convinced me that the average of the roots of p(x) and the
average of the roots of p'(x) are the same - but I can't prove
it or even see why it should be true.  Can anyone offer me some
justification?

     Lemme be a little clearer about what I'm trying to say.
If p(x)=c(x-a_1)(x-a_2)...(x-a_n) for some complex a_1, ... a_n
then "the average of the roots of p(x)" is (a_1+a_2+...+a_n)/n.
So repeated roots are counted multiple times.  For example, if
p(x)=x^3-3x^2+2x=x(x-1)(x-2) then "the average of the roots of
p(x)" is (0+1+2)/2=1.  Also, p'(x)=3x^2-6x+2 with roots 1-sqrt(3)/3,
1+sqrt(3)/3, so "the average of the roots of p'(x)" is also 1.
You can repeat one more time - p''(x)=6x-6, with root 1.

     So, there's the first question I've been wondering about.
(And getting nowhere on... :-)  Now for the other question.
(Drumroll please! :-)  I learned in my math class last year that
there's a bijection from Q (the rationals) to Z (the integers).
Is there a bijection from R (the reals) to R^2?

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


From: erickw@sfu.ca
Subject: Re: Two Questions

>      Lemme be a little clearer about what I'm trying to say.
> If p(x)=c(x-a_1)(x-a_2)...(x-a_n) for some complex a_1, ... a_n
> then "the average of the roots of p(x)" is (a_1+a_2+...+a_n)/n.

This is because the sum of the roots of a_n x^n + a_(n-1) x^(n-1) + ... + a0
is equal to -a_(n_1)/a_n.  A little calculation shows that the average of the
roots is preserved by differentiation.  This is a neat fact, I never noticed
it before!

This reminds me of a question from the 1991 Putnam:

Find all polynomials p(x) with degree n >= 2, with n distinct real roots
r_1 < r_2 < ... < r_n, such that p'(x) has roots (r_1 + r_2)/2, (r_2 + r_3)/2,
..., (r_n-1 + r_n)/2.

In other words the derivative of p must have roots that lie halfway between the
roots of p...Incidentally, can you see why p' will always have exactly one root
(somewhere, not necessary halfway) in between any two consecutive roots of p?

> (Drumroll please! :-)  I learned in my math class last year that
> there's a bijection from Q (the rationals) to Z (the integers).
> Is there a bijection from R (the reals) to R^2?

Yes there is...Why?  Well, let's see I think this might work as a surjection
from R onto R^2...If we have two real numbers, we can take the digits and
"splice" them together.  For instance (1.3,23.87) -> 213.3807.  Any more
elegant ideas?

 -- Erick



From: a_rubin@dsg4.dse.beckman.com (arthur rubin)
Subject: Re: Jp. Olympiad Problem (SPOILER)

Problem:

Let S={1,11,31,51,71} and suppose {a_n} be a sequence of numbers satisfying the following conditions (1),(2),(3):

	(1) a_1 is an element of S
	(2) (a_(n+1) - 1)/(a_n + 1) is an element of S.
	(3) There exists a positive number n <= 10 with a_n = 1993
List up a_4 for all such sequence {a_n}



((Spoiler))






















































The only such sequence (by a computer exhaustion) is:

1, 23, 25, 27, 1989, 1991, 1993


From: kubo@math.harvard.edu (Tal Kubo)
Subject: Japan Olympiad problem [partial SPOILER]




Partial SPOILER follows. 


From: David Michael Tuller <tulled@rpi.edu>
Subject: Jap. Math Olympiad

Problem 9: Let S={1,11,31,51,71} and suppose {an} be a sequence of numbers
satisfying
(1) a1 is in S
(2) (a sub n+1 -1)/(an+1) is in S
(3) There exists an n<=10 with an=1993.

SPOILER

























Let a10=1993. In order to find all such sequences, we work backwards. Well,
a9 can only be 1991 since 1992 is divisible by 1 and not 11, 31, etc. 
Continuing, I got only the following 2 sequences:

1, 23, 25, 27, 1989, 1991, 1993
1, 63, 1985, 1987, 1989, 1991, 1993

Please correct me if I missed any.

David M. Tuller
tulled@rpi.edu

I think I have e-mail working!! Thanks for the help.



From: kubo@math.harvard.edu (Tal Kubo)
Subject: Jp. Olym. problem [partial SPOILER]


OK, 2nd attempt to post this.  

Partial SPOILER follows.


































A computer search is unnecessary.  Because each element of  S is 1 mod 10,
the second condition implies  a(n+1)=a(n)+2 mod 10, which cuts down the
possibilities considerably.



From: PENRICES@SNYCORVA.bitnet
Subject: humor

From:   SCORVA::KENTJ        23-JUL-1993 18:02:15.18
Subj:   fyi- Math hooligans on the loose?


The attached news story has been circulating on the nets for a few days; we
are not sure where it originated [the name attached *may* be the right one,
but it's not always easy to establish the provenance of an oft-reposted
e-mail text].  We thought C18-L readers might be interested... --KB
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>From: "Charles A. Bigelow" <bigelow@cs.stanford.edu>
>Subject: Take That, Fermat!
>-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>News Item (June 23)-Mathematicians worldwide were excited and pleased
>today by the announcement that Princeton University professor Andrew
>Wiles had finally proved Fermat's Last Theorem, a 356-year-old problem
>said to be the most famous in the field.
>
>Yes, admittedly, there was rioting and vandalism last week during the
>celebration. A few bookstores had windows smashed and shelves
>stripped, and vacant lots glowed with burning piles of old
>dissertations. But overall we can feel relief that it was nothing-
>nothing- compared to the outbreak of exuberant thuggery that occurred
>in 1984 after Louis deBranges finally proved the Bieberbach
>Conjecture.
>
>"Math hooligans are the worst," said a Chicago Police Department
>spokesman.  "But the city learned from the Bieberbach riots. We were
>ready for them this time."
>
>When word hit Wednesday that Fermat's Last Theorem had fallen, a
>massive show of force from law enforcement at universities all around
>the country headed off a repeat of the festive looting sprees that
>have become the traditional accompaniment to triumphant breakthroughs
>in higher mathematics.
>
>Mounted police throughout Hyde Park kept crowds of delirious wizards
>at the University of Chicago from tipping cars over on the midway as
>they first did in 1976 when Wolfgang Hakel and Kenneth Appel cracked
>the long-vexing Four-Color Problem. Incidents of textbook-throwing and
>citizens being pulled from their cars and humiliated with difficult
>story problems last week were described by the university's math
>department chairman Bob Zimmer as "isolated."
>
>Zimmer said, "Most of the celebrations were orderly and peaceful, But
>there will always be a few-usually graduate students-who use any
>excuse to cause trouble and steal. These are not true fans of Andrew
>Wiles."
>
>Wiles himself pleaded for calm even as he offered up the long elusive
>proof that there is no solution to the equation x^n + y^n = z^n when n
>is a whole number greater than two, as Pierre de Fermat first proposed
>in the 17th Century. "Party hard but party safe," he said, echoing the
>phrase he had repeated often in interviews with scholarly journals as
>he came closer and closer to completing his proof.
>
>Some authorities tried to blame the disorder on the provocative
>taunting of Japanese mathematician Yoichi Miyaoka. Miyaoka thought he
>had proved Fermat's Last Theorem in 1988, but his claims did not bear
>up under scrutiny of professional referees, leading some to suspect
>that the fix was in. And ever since, as Wiles chipped away steadily at
>the Fermat problem, Miyaoka scoffed that there would be no reason to
>board up windows near universities any time soon; that God wanted
>Miyaoka to prove it.
>
>In a peculiar sidelight, Miyaoka recently took the trouble to secure a
>U.S.  trademark on the equation "x^n + y^n = z^n" as well as on the
>now-ubiquitous expression, "Take that, Fermat!" Ironically, in defeat,
>he stands to make a good deal of money on cap and T-shirt sales.
>
>This was no walk-in-the-park proof for Wiles. He was dogged, in the
>early going, by sniping publicity that claimed he was seen puttering
>late one night doing set theory in a New Jersey library when he either
>should have been sleeping, critics said, or focusing on arithmetic
>algebraic geometry for the proving work ahead.
>
>"Set theory is my hobby, it helps me relax," was his angry
>explanation. The next night, he channeled his fury and came up with
>five critical steps in his proof. Not a record, but close.
>
>There was talk that he thought he could do it all by himself,
>especially when he candidly referred to University of California
>mathematician Kenneth Ribet as part of his "supporting cast," when
>most people in the field knew that without Ribet's 1986 proof
>definitively linking the Taniyama Conjecture to Fermat's Last Theorem,
>Wiles would be just another frustrated guy in a tweed jacket teaching
>calculus to freshmen.
>
>His travails made the ultimate victory that much more explosive for
>math buffs.  When the news arrived, many were already wired from
>caffeine comsumed at daily colloquial teas, and they took to the
>streets en masse shouting, "Obvious!  Yessss! It was obvious!"
>
>The law cannot hope to stop such enthusiasm, only to control it.
>Still, one has to wonder what the connection is between wanton
>pillaging and a mathematical proof, no matter how long-awaited and
>subtle.
>
>The Victory Over Fermat rally, held on a cloudless day in front of a
>crowd of 30,000 (police estimate: 150,000) was pleasantly peaceful.
>Signs unfurled in the audience proclaimed Wiles the greatest
>mathematician of all time, though partisans of Euclid, Descartes,
>Newton and C.F. Gauss and others argued the point vehemently.
>
>A warmup act, The Supertheorists, delighted the crowd with a ragged
>song, "It Was Never Less Than Probable, My Friend," which included
>such gloating, barbed verses as- "I had my proof all ready/But then I
>did a choke-a/Made liberal assumptions/Hi! I'm Yoichi Miyaoka."
>
>In the speeches from the stage, there was talk of a dynasty,
>specifically that next year Wiles will crack the great unproven
>Riemann Hypothesis ("Rie-peat!  Rie-peat!" the crowd cried), and after
>that the Prime-Pair Problem, the Goldbach Conjecture (Minimum
>Goldbach," said one T-shirt) and so on.
>
>They couldn't just let him enjoy his proof. Not even for one day. Math
>people.  Go figure 'em.


From: David Michael Tuller <tulled@rpi.edu>
Subject: Finding a function

Can you find a function f such that if n is a positive integer, f(n) is the
nth nonsquare? For example, f(1)=2, f(2)=3, f(3)=5, f(4)=6, etc. You can use
+ - * / roots powers ceiling floor etc. Good luck!

David M. Tuller
tulled@rpi.edu


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


Imagine a cylinder whose radius increases at a constant rate of
2cm/sec., while its height decreases at 3 cm/sec.  When the radius is
4cm., the height is 5cm.  What is the height of the cylinder when its
volume is at its maximum?

Enjoy

Benjie


From: greg_jamison@csufresno.edu (Greg Jamison)
Subject: Re: P.O.D.*spoiler*

> 
> Imagine a cylinder whose radius increases at a constant rate of
> 2cm/sec., while its height decreases at 3 cm/sec.  When the radius is
> 4cm., the height is 5cm.  What is the height of the cylinder when its
> volume is at its maximum?

 



















If the radius increases at a constant rate of 2 cm/sec, then dr/dt=2,
and r(t)=2t+C.  r(0)=4, so that C=4, and r(t)=2t+4.  Similarly,
h(t)= -3t+5.  V=pi*r^2*h, so that V(t)=pi*(2t+4)^2*(-3t+5).  Since
neither the radius nor the height can be less than zero, -2<=t<=5/3.
The problem now reduces to maximizing the function V(t) over the interval
[-2,5/3].  
V(t)=pi*(2t+4)^2*(-3t+5)
    =-4*pi*(3t^3+7t^2-8t-20)

V'(t)=-4*pi*(9t^2+14t-8)=0
             (9t-4)(t+2)=0
              t=9/4 or t=-2
Therefore the maximum must occur at t=-2, 9/4, or 5/3.
V(-2)=V(5/3)=0
V(9/4)=pi*21296/243=275.322457...

Therefore the maximum occurs at t=4/9.  The height of the cylinder at
time t=4/9 is 11/3 cm.


From: kubo@math.harvard.edu (Tal Kubo)
Subject: Re: P.O.D.*spoiler*


>> 
>> Imagine a cylinder whose radius increases at a constant rate of
>> 2cm/sec., while its height decreases at 3 cm/sec.  When the radius is
>> 4cm., the height is 5cm.  What is the height of the cylinder when its
>> volume is at its maximum?

Someone just posted a calculus-based solution.  This problem is an example
of something I mentioned recently on sci.math, namely, exactly solvable
polynomial extremum problems in calculus books are easier to do with 
inequalities.  Let's see how this works for the problem above:

The given data imply 3R + 2H  is constant; plugging in the given 
values R=4, H=5, we find  3R+2H = 22.  
We want to maximize volume, which is proportional to  R*R*H, which is 
also proportional to  (3/2 R)(3/2 R)(2H).  But this is
a product of terms with fixed sum  25, so it attains its maximum when all
factors are equal, i.e.  3/2 R = 2H  ---> (3R,2H) divide 22 in the ratio 2:1,
i.e. 2H=22/3, so H=11/3  when the volume is maximum.  This seems a lot
easier than the calculus based solution which requires extra variables and
case checking.





From: mokie@cco.caltech.edu (Michael L. Brundage)
Subject: Re: Solution to Two Questions

Sorry, I deleted the response of someone (?) before I could reply

I too, thought about "splicing" numbers together, but I think you run into
problems with .9999.... = 1.00000...., because then (for example),
if f(a,b) is the "splice" of a and b, then we have
for m=.999999....  and n=1.0000000....,  (note m=n)
1=.99999....=f(m,m)=f(n,m)=1.909090909090... = 21/11 =/= 1
So....



From: alanm@efi.com
Subject: Re: Solution to Two Questions


The question was if there was a 1-1 onto (I can't remember what this
is called, surjective?) mapping from R^2 to R.

> I too, thought about "splicing" numbers together, but I think you run into
> problems with .9999.... = 1.00000...., because then (for example),
> if f(a,b) is the "splice" of a and b, then we have
> for m=.999999....  and n=1.0000000....,  (note m=n)
> 1=.99999....=f(m,m)=f(n,m)=1.909090909090... = 21/11 =/= 1

Since this is the technique that Cantor used to show that the numbers
of points on a plane is of the same magnitude as the number of points
on a line I suspect there is some technique to eliminate this little
problem.

Alan



From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Re: Solution to Two Questions

> The question was if there was a 1-1 onto (I can't remember what this
> is called, surjective?) mapping from R^2 to R.
> 
> > I too, thought about "splicing" numbers together, but I think you run into
> > problems with .9999.... = 1.00000...., because then (for example),
> > if f(a,b) is the "splice" of a and b, then we have
> > for m=.999999....  and n=1.0000000....,  (note m=n)
> > 1=.99999....=f(m,m)=f(n,m)=1.909090909090... = 21/11 =/= 1
> 
> Since this is the technique that Cantor used to show that the numbers
> of points on a plane is of the same magnitude as the number of points
> on a line I suspect there is some technique to eliminate this little
> problem.
> 
> Alan

For definiteness, let us always choose the decimal representation
which does not end in an infinite string of zeros.  So 2 should be 
represented as 1.999999.... , not as 2.000000... .

The trick is to attach to each nonzero digit all of its 
immediately preceding zeros, and then "splice" the numbers together. 
(Digits to the left of the decimal point are simply alternated)

For example, if the numbers are 1234.120340005... and 567.06007809...,
then you combine them to form 10253647.10620070384090005... .
It is possible to reverse this process, so we have a 1-1 correspondence
(bijection) between R^2 and R.

Dave



From: erickw@sfu.ca
Subject: Re: Finding a function (SPOILER)


> Can you find a function f such that if n is a positive integer, f(n) is the
> nth nonsquare? For example, f(1)=2, f(2)=3, f(3)=5, f(4)=6, etc. You can use
> + - * / roots powers ceiling floor etc. Good luck!

This is an application of a nice discovery of J. Lambek and Leo Moser...You can
find it in "Ingenuity in Mathematics" by Ross Honsberger (full of good stuff...
he also has a number of similar books: Mathematical Morsels and Mathematical
Gems and their sequels).

SPOILER follows:
























The discovery concerns so-called complementary sequences, that is, a pair of
sequences of positive integers that together go through each positive integer
exactly once.  A beautiful example due to Beatty is if X is irrational, then
the sequences {floor(n*(1+X))} and {floor(n*(1+1/X))} are complementary!

Another example, and one which pertains to this question, is if we have an
non-decreasing sequence f(n) of positive integers, construct the sequence
f*(n) = {# of m such that f(m) < n}.  Notice that f**(n) = f(n).  It turns
out that {f(n)+n} and {f*(n)+n} are complementary sequences, and furthermore
every pair of complementary sequences has this form.

So, we partition the positive integers into the squares and the complementary
sequence of non-squares.  Since f(n)+n = n^2, f(n) here is n^2 - n.  All we
have to do now is find f*(n), i.e. the largest m such that m^2 - m < n.  It's
easy to work out that this m is floor(sqrt(n)+1/2) = round(sqrt(n)).  So the
nth non-square is given by n + round(sqrt(n)).

 -- Erick



From: Susan Schwartz Wildstrom <ssw@umd5.umd.edu>
Subject: POD - Solution (spoiler?)


One can make this problem as hard as one likes, but it can be solved using 
fairly straightforward techniques in algebra coupled with simple calculus.
























Suppose that we regard the "time" when the radius is 4 cm and the height is
5 cm to be time zero (Since we are interested in the value of the height
at a particular stage in the "development" of the cylinder, time becomes
parametric and the frame of reference in which we measure it is our choice.

Both the radius and the height change at a constant rate based on time and
thus can be expressed as functions of time.

               r(t) = 4 + 2t     and h(t) = 5 - 3t

Since volume = pi*r squared * h,  we merely substitute.

        V = pi (4+2t)^2(5-3t)

We are interested in the height of the cylinder "at the time when the
volume is a maximum"  To find out when the volume is at a maximum, one
needs to know more about the rate at which the volume is changing over
time  (dV).  Differentiating the volume formula will give an expression
for changes in V over time.  When dV is positive the cylinder's volume is
growing.  When dV is negative it is shrinking.  Thus, the maximum volume
is achieved at the instant when growth ceases and before shrinkage begins
ie, dV = 0.  Solving that equation we have the time (from our own selected frame
of reference) and substituting that value of t into any of our functions
to find whatever we want to.

       dV = pi * 2 * 2 *(4 + 2t)(5 - 3t) + pi * (4 + 2t)^2 * (-3)

            = pi * (4 + 2t)*[2(5 - 3t) + (-3)(4 + 2t)]

                    steps deleted due to clunkiness!

                    t = 4/9

               thus the desired height is 5 - 3(4/9) = 11/3 cm