From: Android <benjie>
Subject: P.O.D.

Problem of the Day



	|\		|		
	|  \		|		
	|    \		|		
 	|      \	|		
	|  	\	|		
        |  	a\     /| 		
	|	  \  /  |
	|	 / \	|
	|      /    \ 	|
	|    /b	     \ 	|
	|  /	      \ |
	|/             \|
        -----------------

Two straight ladders laid on two walls as shown in the figure.  The
two ladders have lengths of a and b.  If the distance between their
intersecting point and the ground is c.  What is the distance between
the two walls?

Benjie


From: "David W. Wilson" <wilson@ctron.com>
Subject: SPOILER -- ANOTHER SOLUTION to 2a^2 ......



>   Show that 2a^2+b^2=5c^2 has no integral solutions in a,b,c
>   ('cept for 0,0,0).

    If (a, b, c) is a solution, then so is (|a|, |b|, |c|), so, without
    loss of generality, assume that a, b, and c are all nonnegative.

    If one of a or b is 0, an infinite descent argument shows that the
    other cannot be positive, and a = b = c = 0 quickly follows.  If
    c = 0, a = b = c = 0 also follows quickly.  Thus we can further
    assume that a, b, and c are all positive.

    Suppose

	(1)  2a^2 + b^2 = 5c^2

    has a solution in positive a, b, and c.  We can then choose solution
    (a, b, c) = (p, q, r) such that c is minimal over all solutions in
    positive integers.  Clearly

	2p^2 + q^2 = 5r^2.

    Residues mod 5 establish that p == q == 0 (mod 5).  Therefore, let
    p = 5s and q = 5t.  Then

	50s^2 + 25t^2 = 5r^2  ==>  10s^2 + 5t^2 = r^2.

    Again, mod 5 residues give r == 0 (mod 5).  Thus r = 5u, giving

	10s^2 + 5t^2 = 25u^2  ==>  2s^2 + t^2 = 5u^2.

    Hence (a, b, c) = (s, t, u) solves (1) with 0 < u = r/5 < r.  This
    contradicts the definition of solution (a, b, c) = (p, q, r).  Our
    supposition was therefore wrong, and (1) has no solution in positive
    integers a, b, and c.




From: Android <benjie>
Subject: Algebra in Calculus


Here is a little problem from my Calculus book.  It looks easy, but try it.
My teacher (and us) gave up after solving 3/4 of it.

It's not hard, but ......


Find the unit tangent vector T and the unit normal vector N for the given
value of t.

x = sin t,  y = cos t,  z = 1/2 t^2   ;   t = 0



OK, if you could solve the problem in 5 minutes without the use of computer,
I shall name you the "Equation Simplifier"!

Enjoy

Benjie

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


Just finished my OSURYSP application, and here are some problems they
threw at me.  I thought they were interesting.


1.  Assume that the points of the plane are each colored red or blue.
Prove that one of these colors contains pairs of points at every
mutual distance.

2.  Twelve students use a fraternity dining room which has three
tables with four settings on each table.  How should one vary the
seating arrangement so that in five days, each student would share the
table at dinner with each other student?

3.  Several circles are drawn inside a unit square.  Prove that if the
sum of their circumferences is equal to 10, there exists a straight
line that intersects at least four circles.

4.  Show that three points represented by complex numbers a,b, and c
form an equilateral triangle iff a^2 + b^2 + c^2 - ab - bc - ca = 0.


There were more, but these four stands out, IMHO, as the four most
intrigueing questions of the set.

Benjie


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


P.O.D. stands for Problem of the Day and P.O.W. stands for Problem of the Week.
Here are three POD/POW from my math class, they are interesting, although not
too hard.

1. POW
Integrate	\int_{0}^{pi} sqrt(1-sinx) dx

2. POD1
What's the maximum number of region a rectangle could be divided into
by intersecting circles inside the rectangle?  Find a formula for n
circles.

2. POD2
What's the maximum number of region a triangle could be divided into
by m, n and p lines coming from each vertex to each side.

What do you think?

Benjie

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


Here's another problem of the day:

A circle and one of its diameter are drawn.  Also drawn is a point
outside the circle.  Using only straight edges, how could you draw the
perpendicular segment from the point to the extend of the diameter.


Benjie

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


Here I have an interesting problem.  I thought it was neat:

Find a positive integer m such that 1/2 m is a perfect square and 1/3 m is a
perfect cube.  Can you find a positive integer n for which 1/2 n is a perfect
sqaure, 1/3 n is a perfect cube and 1/5 n is a perfect fifth power?

Benjie

From: Android <benjie@quack.kfu.com>
Subject: Fermat's Last Theorem


I have the Thur. copy of NY Times which has an article on the proof of
FLT, anyone want to see it?  If enough people replies, I will include in
in the next newsletter.

Benjie

From: bboru@lobby.ti.com (B. Borowicz)
Subject: Re: Fermat's Last


> Prove that 2a^2 + b^2 = 5c^2 has no non-trivial integral solutions.

Clearly, if b is odd, then c will be odd, and if b is even, then c will also
be even.  Testing either case (odd-odd) or (even-even) reaches contradictions.

Assume b and c both odd.  b = 2m+1 ; c = 2n+1
	2a^2 + (2m+1)^2 = 5(2n+1)^2
  or
	2a^2 + 4m^2 + 4m = 20n^2 + 20n + 4
  /2
	a^2 + 2m^2 + 2m = 10n^2 + 10n + 2
  which implies that 'a' is even.
a=2k
    	4k^2 + 2m^2 + 2m = 10n^2 + 10n + 2
  /2
	2k^2 + m^2 + m = 5n^2 + 5n + 1
				        The left side is always even, for
				        integral k and m, while the right
					side is always odd for integers.
Therefore: b and c cannot both be odd.

Assume b and c both even.  b = 2m ; c = 2n

	2a^2 + 4m^2 = 20n^2
  /2
	a^2 + 2m^2 = 10n^2
			   so a must be even, a = 2k
	4a^2 + 2m^2 = 10n^2
  /2
(k, sorry)   2k^2 + m^2 = 5n^2
				 which implies infinite descent, that every
				 integral solution implies smaller integral
				 solutions which just doesn't work for
				 finite numbers.

Therefore: b and c cannot both be odd.  If b cannot be odd and cannot be
even either, it must not be an integer.

Hope this wasn't the long way.

	Brian Borowicz
	bboru@lobby.ti.com


From: Android <benjie@quack.kfu.com>
Subject: Problem of the Day

If r is the remainder when each of the numbers 1059, 1417 and 2312 is divided by
d, where d is an integer greater than one, then what is d-r?

Hint:  Prime table is useful, unless you remember all the prime numbers up to 300.

Benjie

From: "David W. Wilson" <wilson@ctron.com>
Subject: SPOILER -- ANOTHER SOLUTION to 2a^2 ......

>   Show that 2a^2+b^2=5c^2 has no integral solutions in a,b,c
>   ('cept for 0,0,0).

    If (a, b, c) is a solution, then so is (|a|, |b|, |c|), so, without
    loss of generality, assume that a, b, and c are all nonnegative.

    If one of a or b is 0, an infinite descent argument shows that the
    other cannot be positive, and a = b = c = 0 quickly follows.  If
    c = 0, a = b = c = 0 also follows quickly.  Thus we can further
    assume that a, b, and c are all positive.

    Suppose

	(1)  2a^2 + b^2 = 5c^2

    has a solution in positive a, b, and c.  We can then choose solution
    (a, b, c) = (p, q, r) such that c is minimal over all solutions in
    positive integers.  Clearly

	2p^2 + q^2 = 5r^2.

    Residues mod 5 establish that p == q == 0 (mod 5).  Therefore, let
    p = 5s and q = 5t.  Then

	50s^2 + 25t^2 = 5r^2  ==>  10s^2 + 5t^2 = r^2.

    Again, mod 5 residues give r == 0 (mod 5).  Thus r = 5u, giving

	10s^2 + 5t^2 = 25u^2  ==>  2s^2 + t^2 = 5u^2.

    Hence (a, b, c) = (s, t, u) solves (1) with 0 < u = r/5 < r.  This
    contradicts the definition of solution (a, b, c) = (p, q, r).  Our
    supposition was therefore wrong, and (1) has no solution in positive
    integers a, b, and c.




From: Van@cup.portal.com
Subject: Re: subcubes of a N-cube

I have come across a very interesting problem:

Given an N dimensional cube, [0,1]^N, how many M-dimensional cubes does
it contain, for any M = 0,1, ... ,N?

There are several interesting ways to do this problem.

Perhaps this has already been done here, as I am a new member.

van@cup.portal.com

Van


From: Van@cup.portal.com
Subject: faces, edges, and corner of an N-cube

 Re:
Given an N dimensional cube, [0,1]^N, how many M-dimensional cubes does
it contain, for any M = 0,1, ... ,N?
==========
I received a couple of questions as to

 "What does contain mean?"

Maybe I should have said "How many M-dimensional subcubes, or faces does it hav
e?"
Here a "face" can be any dimension less than N.

This is the analog of the question for a 3D cube of

"how many faces does a 3D cube have (M = 2), how many edges (M = 1),
and how many corners (M = 0)".

A 3D cube has 6 2D faces, 12 edges (1D), and 8 corners (0D).

van@cup.portal.com

Van


Subject: 2a^2 + b^2 = 5c^2

Assume that not all the integers are divisible by 5.  Then
if 5|a and 5|b we get that 25 | 5c^2 and that 5|c.  This
is a contradiction.  Now 2a^2 + b^2 can be one of 0+1,
0+4, 2+0, 2+1, 2+4, 8+0, 8+1, or 8+4 mod 5 (since all
squares are 0,1 or 4 mod 5).  5c^2 is neither of these
forms.

You can find this argument in page 10 of Miles Reid's
"Undergraduate Algebraic Geometry."  I thought there
might be a nicer way, and Brian Borowicz supplied that
splendidly!  David Wagner came closest to the mod 5 argument.


 Somebody recently asked for the number of k-dimensional faces of an
 n-dimensional cube.  (I am rephrasing the question, because I no longer
 have this article.)  My solution is "overkill" in some sense, but I think
 it is interesting nevertheless.

                            - - - - - - -

 A polyhedron has vertices, edges, and faces.  For the sake of generality, I
 will call all of these things "faces", and I will distinguish them by their
 dimension.  For example, a cube has 1 3-face, 6 2-faces, 12 1-faces, and 8
 0-faces.

 If A and B are sets, then their product is AxB = {(a,b) : a in A, b in B}.
 If C is an m-face of A, and D is an n-face of B, then CxD is an (m+n)-face
 of AxB.  Furthermore, every face of AxB is the product of a face of A and a
 face of B.

 Let C=AxB.  Let a(k), b(k), and c(k) denote the number of k-faces of A, B,
 and C, respectively.  The previous argument shows that

   c(n) = a(0)*b(n) + a(1)*b(n-1) + . . . + a(n-1)*b(1) + a(n)*b(0).

 This formula should look familiar, because it is exactly how you multiply
 polynomials!  If A is an n-dimensional polyhedron, define a polynomial PA by
 PA(x) = a(n)*x^n + a(n-1)*x^(n-1) + . . . + a(1)*x + a(0), where a(k) is the
 number of k-faces of A.  Then P(AxB)(x) = PA(x) PB(x).

 We can use this formula to find the number of k-faces of an n-cube.  Let J
 be the interval [0,1].  J has 1 1-cell and 2 0-cells, so PJ(x) = x + 2.  The
 n-cube is J^n, and P(J^n)(x) = (x + 2)^n.  The number of k-faces of the
 n-cube is equal to the coefficient of x^k in (x + 2)^n.  By the binomial
 theorem, this number is (2^(n-k) n!) / (k! (n-k)!).

 This idea of associating a polynomial to a polyhedron has some interesting
 consequences.  The Euler characteristic of a polyhedron A is
 chi(A) = (# of vertices) - (# of edges) + (# of faces) - ... .
 This can be re-written as chi(A) = PA(-1).  It follows from this formula
 that chi(AxB) = chi(A) chi(B).


This is a problem that we did in a course I took last semester...It's from a
book by Babai and (I forget) called "Linear Algebra methods in Combinatorics".
The solution is really neat, for those of you who've done some linear algebra,
so I decided (at David Wagner's suggestion) to post it to IAMS:

There is a town with 32 citizens, who love to form clubs (a club is just a set
of people, possibly empty or full).  To prevent there from being *too* many
clubs, the mayor decrees that the following two rules must be followed:

a) Every club must have an odd number of members;
b) The number of common members between two different clubs (i.e. intersection)
   must be even.

The townspeople quickly realize that they can form at least 32 clubs: for
instance each person could have their own club with one member.  But it turns
out that 32 is the most they can form!

Proof:  Let C_1, C_2, ..., C_m be m clubs which satisfy the rules a) and b).
For each C_i, let x_i be its (0,1)-characteristic vector, i.e. a 32-dimensional
vector, where each component corresponds to a citizen, and has value 1 if the
citizen is in the club, and 0 if not.

It easy to see that the dot product x.y of two of these vectors is exactly the
size of the intersection of the corresponding sets!  So we can restate the
conditions a) and b) as:

a) (x_i).(x_i) is odd;
b) (x_i).(x_j) is even, for i \neq j.

To simplify things, we will work in GF(2) (if you haven't heard of this, don't
worry...it's just arithmetic modulo 2; in other words we have just two elements
0 and 1, with 1+1 = 0.  The important thing is that most of the laws of linear
algebra still hold).  Now, the conditions may be restated again as follows:

a) (x_i).(x_i) = 1,
b) (x_i).(x_j) = 0, for i \neq j.

Here comes the trick.  We will show that these vectors are linearly independent
(over GF(2)).  Then, since they are 32-dimensional, there can be at most 32!!!
(those are not factorials ;-)

So, suppose that for some scalars c_1, c_2, ..., c_m (remember that we're
working over GF(2), so the only scalars in town are 0 and 1):

   c_1 x_1 + c_2 x_2 + ... + c_m x_m = 0.

Now, for any i, take the dot product of both sides with x_i.  Because of
condition b), everything cancels out, except for:

   c_i (x_i).(x_i) = c_i = 0.

Therefore all the c_i's are 0, and the vectors are linearly independent!

An interesting fact: if you change condition a) from "odd" to "even", and also
restrict the clubs to have distinct memberships (which we didn't need before,
because condition b) would have ruled out any clubs with the equal membership),
the maximum number of clubs attainable grows dramatically, to 2^16 = 65536!

Again the proof of this uses linear algebra...But it's a little different
(still a very nice argument!)

So, that was the very first problem in the book...In fact, we only ever got
up to Section 1.3 (this one is about dissection puzzles, as in Hilbert's 3rd
problem), but the book kept us busy enough with the exercises...There is one
that I still have not figured out :-).



From: bboru@mkcase1.dseg.ti.com (Brian Borowicz)
Subject: N-cube


Just by inspection, you can see that every time you move up from dimension
n to n+1, you create twice as many vertices (dimension 0), twice as many
edges plus as many edges as new vertices, etc... and finally one new
cube of dimension n+1.  Recursively, this can be expressed:

                   d(m,n) = 2*d(m,n-1) + d(m-1,n-1)

where d(n,n) = 1 and d(n+1,n) = 0.
It looks like:
                                m
                |_0___1___2___3___4___5___6___...
              0 | 1   0   0   0   0   0   0
	      1 | 2   1   0   0   0   0   0
	      2 | 4   4   1   0   0   0   0
	  n   3 | 8   12  6   1   0   0   0
	      4 | 16  32  24  8   1   0   0
	      5 | 32  80  80  40  10  1   0   etc.

which, pretty clearly, resembles Pascal's triangle multiplied by some
powers of two.  The iterative solution comes easily:

                d(m,n) = 2^(n-m)*n!/[m!*(n-m)!]


Interestingly, the sum of any row is 3^n:

           sum{m=0,n}[2^(n-m)*n!/[m!*(n-m)!]] = 3^n

And the alternating sum of any row is 1:

           sum{m=0,n}[(-1)^m*2^(n-m)*n!/[m!*(n-m)!]] = 1


        Brian Borowicz
        bboru@lobby.ti.com




From: Android <benjie@quack.kfu.com>
Subject: projection -> object


I know that you could project a 3d object to 2d (could someone explain to me how?) , but I was wondering if you could do the reverse, transform a 2d equation to
the equation of the object in 3d.  If so, could you do 3d->4d?

BEnjie

From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly)
Subject: Spoiler 1,2-Three aggravating problems

Here is a spoiler for 2 of the three problems that David G Radcliffe
proposed.

1.  Prove that for every positive integer n, there is an integer x
    so that x^2 + 3x + 5 is divisible by 15^n.

Solution: For n=1 the solution is x=2. Suppose that there is a solution for n
of the form 2+15k. We can generate a solution for n+1 as follows. What
happens if we take x=2+15k+(15^n)l? Well then x^2+3x+5 is congruent mod
15^(n+1) to the previous solution plus 7*15^n*l. Since 7*13 is congruent to 1
mod 15 we can choose l such that x^2+3x+5 is congruent to 0 mod 15^(n+1).
Therefore 15^(n+1) divides x^2+3x+5. Now by an easy induction we are done.


2. Let f(x) = 1 + x + (x^4 / 4!) + (x^9 / 9!) + (x^16 / 16!) + . . .
    Prove or disprove that (f(x)/e^x) converges to 0 as x goes to infinity.

Solution: Note that if m is fixed and x is sufficiently large then
2x^(n+m)/(n+m)! > x^n/n! if x>=n and 2x^(n-m)/(n-m)! > x^n/n! if x<n.
Therefore let m be fixed and look at 2e^x-(m+1)f(x). Expand into power series
and note that the series is absolutely convergent so we may rearrange the
terms into any order that we like. But if x>m^2 then all but the first m/2
terms of (m+1)f(x) can be paired off with terms in 2e^x into groups that look
like
(2x^n/n!-x^n/n!) + (2x^(n+1)/(n+1)!-x^n/n!)+...+(2x^(n+m)/(n+m)!-x^n/n!) if
n=<x
and
(2x^n/n!-x^n/n!) + (2x^(n-1)/(n-1)!-x^n/n!)+...+(2x^(n-m)/(n-m)!-x^n/n!) if
n>x.
There will also be a large number of positive terms left over from 2e^x, some
of which for large x will easily cancel out the first few terms that were not
paired off. Therefore we have shown that 2e^x-(m+1)f(x)>0 for sufficiently
large x. But since that holds for all m we now can easily show that the limit
as x goes to infinity of f(x)/e^x is 0.

Ben Tilly


From: bk@pro-palmtree.socal.com (Bruce Kravets)
Subject: Re: problem

Here is an easy (I think ) problem for your group
What is the length of the diagonal of a hypercube in terms of a side?



-----
UUCP: hatch!pro-palmtree!bk                    The Palmtree BBS
Inet: bk@pro-palmtree.socal.com                310-453-8726 v.32



 *** SPOILER ***
 > Find the unit tangent vector T and the unit normal vector N for the given
 > value of t.
 > 
 > x = sin t,  y = cos t,  z = 1/2 t^2   ;   t = 0
 
 Using s(t) [the length of the curve] as a natural parameter the solution
 is:
 
 T(s(t)) = X'(s(t))
 N(s(t)) = T'(s(t))
                                           .   .     ..  ..
 in the following formulas I use s = s(t), s = s(t), s = s(t)
 
         / sin s \
 X(s) = |  cos s  |
         \1/2 s^2/
 
         /       .\
        |cos s * s |
 T(s) = |         .|
        |-sin s * s|
        |      .   |
         \ s * s  /
 
         /        .          ..\
        |-sin s * s + cos s * s |
 N(s) = |         .           ..|
        |-cos s * s - sin s * s |
        |      .         ..     |
         \     s^2 + s * s     /
 
 Now we need to know what s(t) is:
 
         t   .
 s(t) = Int |X(t)| dt
         0
 
 .       /cos t\      .               2       2     2              2
 X(t) = |-sin t | => |X(t)| = sqrt(cos t + sin t + t ) = sqrt(1 + t )
         \  t  /
 
         t            2
 s(t) = Int sqrt(1 + t ) dt => s(0) = 0
         0
 .                2            .
 s(t) = sqrt(1 + t )        => s(0) = 1
 
 ..           t                ..
 s(t) = -------------       => s(0) = 0
        sqrt(1 + t^2)
 
 Inserting this in T(s) and N(s) yields
 
         /1\
 T(0) = | 0 |
         \0/
 
         /0\   _         1    /0\
 N(0) = |-1 |, N(0) = ------ |-1 |
         \1/          sqrt(2) \1/
 
 Wolfgang
 



From: Leigh Blue Caldwell <gaps05@udcf.gla.ac.uk>
Subject: Solution to hypercube problem.



Okay here's another

SPOILER

in case you didn't read the Subject: line.











Firstly the definition of a hypercube, in case anyone's not familiar with
them.  Effectively, a hypercube is a 4- (or more-) dimensional cube.  Think
of a line as a 1-dimensional cube (it's rather difficult to envisage any
other 1-dimensional object than a line actually :), then a square, the next
step up, as a 2-dimensional cube, then an ordinary cube, the next step up,
as a 3-dimensional cube, then try to imagine the next step...
What you're really doing is extending the shape by a constant distance in
a direction perpendicular to itself.
Some diagrams, with the side of the cube having length L.

1-dimensional cube (line):

             L
  ----------------------

2-dimensional cube (square):
             L
  ----------------------
  |                    |
  |                    |
  |                    |
  |                    |
  |                    | extended downwards by L.
  |                    |
  |                    |
  |                    |
  V                    V
  ----------------------

3-dimensional cube:
            L
  ----------------------
  |\                   |\
  | \                  | \  extended by L in a direction
  |  \                 |  \ perpendicular to the square.
  |   .                |   .
L |    ---------------------          
  |   |                |   |
  |   |                |   |
  |   |                |   |
  |   |                |   |
  ----|-----------------   |
   \  |                 \  |
    \ |                  \ |
     \|                   \|
      .                    .
       ---------------------

If you can envisage extending the cube in a direction perpendicular to
all of the other three, then that is your first hypercbe (the 4-dimensional
one).

Some people claim to be able to visualize a hypercube, but I can't.


Anyway, now onto the problem as stated.  What is the length of the diagonal
of a hypercube in terms of the length of its side?

This is simply Pythagoras.  I'm sure [ :-) ] that you all remember the old
x^2 + y^2 = r^2 formula.  If you want to work out the length of the
diagonal of a square, this is in the form:
  1^2 + 1^2 = diag^2
i.e. diag = sqrt(2).
To work out the diagonal of a cube, take the diagonal of the square at its
base as one of the sides of a triangle...something like this:

       Z
       |
       | 
       |     /
      L|    /
       |   / C
       |  /
       | /
       |/_____________X
       /\         L
      /  \
    L/    \
    /      \ S
   /        \
  Y
each side of the cube is length L, S is the diagonal of the base square,
and C is the diagonal of the cube.
  L^2 + L^2 = S^2
Again from Pythagoras, applied to S, Z and C:
  S^2 + L^2 = C^2
Substituting:
  L^2 + L^2 + L^2 = C^2
  3.L^2 = C^2
or
  C = sqrt(3).L

This can be extended to as many dimensions as you like.

  L^2 + L^2 + ... + L^2 = H^2
where H is the length of diagonal of a hypercube with n dimensions.
  n.L^2 = H^2
  H  =  sqrt(n).L

For a cube in n dimensions, its diagonal will be sqrt(n).L
if L is the length of a side.
So we get the familiar sqrt(2) and sqrt(3) results for a
square and cube respectively, and in the case of a 4-dimensional
hypercube, the diagonal is length sqrt(4).L = 2L exactly.

Now for a couple more problems to keep you all occupied :) I don't know
the answer to these, but I'm sure they've been done before somewhere...

  1) What is the volume of a hypersphere (the n-dimensional
     equivalent of a sphere) in terms of its radius?
     (an n-hypercube's volume is simply L^n).
  2) What is the 'surface area' of a hypersphere in terms of its radius?
     - for example the surface area of a 3-hypersphere (a sphere) is
     4.pi.r^2 - note that a 4-dimensional hypersphere has a 3-dimensional
     'surface', so what I am looking for in this case is a volume.  In
     general, an n-dimensional object has an (n-1)-dimensional surface.

Thank you for your attention...
	leigh



From: Van@cup.portal.com
Subject: SPOILER

SPOILER for diagonal of a hypercube.

For a 2-cube (a square) of unit side, the diagonal is d = sqrt(2).
For a 3-cube, d^2 = sqrt(2)^2 + 1^2 = 3, so 
d = sqrt(3).

Obviously, we can extend this to any dimension, and the n-cube
[0,1]^n has diagonal

d(n) = sqrt(n).

van@cup.portal.com

Van


	id AA24606; Tue, 6 Jul 1993 12:38:03 -0400
From: Van@cup.portal.com
Subject: problem:spider in cube

 Another simple 3D cube problem:

 Consider a spider crawling on inside of a 3D cube from (0,0,0)
  to (1,1,1), taking the shortest path.
 What route does he take, and what is the length of the path.
 
 van@cup.portal.com

Van


From: ag@cs.duke.edu (Arman Glodjo)
Subject: Re: problem:spider in cube


-----------------------------------------------------------------
Another simple 3D cube problem:

 Consider a spider crawling on inside of a 3D cube from (0,0,0)
  to (1,1,1), taking the shortest path.
 What route does he take, and what is the length of the path.
-----------------------------------------------------------------

Answer: 1+sqrt(2), provided spider cannot fly.


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


Problem of the Day

1)  simplify  (write w/o radicals inside radicals):

	sqrt(38+12sqrt(10))

2)  evaluate the limit

	limit as x approaches infinity of (xsqrt(x^2 + 9)-sqrt(x^4 + 81))

Enjoy

Benjie


From: Android <benjie@quack.kfu.com>
Subject: SPOILER -- SOLUTION TO THE SERIES PROBLEM

SPOILER

I had no clue about the first four numbers, so here is my solution.

Step 1, set the first four numbers as   1,4,9,10

for example, when n = 9, a_9 = 8^2 - 13 = 64-13 = 51

--------------------------------------------------
From: ttgrq@info.win.tue.nl (Andreas Gammel)

Elaborate the following series:

1,4,9,10,19,24,31,40,51,64,79,90,.......


this really a nice one!
If you find it, there's more where this came from!
answers to iams or ttgrq@info.win.tue.nl

Bye, Andreas



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




> 1)  simplify  (write w/o radicals inside radicals):
>       sqrt(38+12sqrt(10))


    Let

        sqrt(38 + 12 sqrt(10)) = sqrt(a) + sqrt(b)
        ==>  38 + 12 sqrt(10) = a + b + 2 sqrt(ab)

    which is true when

        a + b = 38, ab = 360

    This is easily solved to yield

        a = 18, b = 20  or  a = 20, b = 18

    either or which gives 

        sqrt(38 + 12 sqrt(10)) = 3 sqrt(2) + 2 sqrt(5).

    Equality is easily verified, and uniqueness of solution follows
    from the definition of sqrt.

> 2)  evaluate the limit as x approaches infinity of
>       x sqrt(x^2 + 9) - sqrt(x^4 + 81)

    we have

         lim   x sqrt((x^2 + 9) - sqrt(x^4 + 81)
        x->inf

                              9x^2 - 81
        =    lim   --------------------------------
            x->inf x sqrt(x^2 + 9) + sqrt(x^4 + 81)

                              9 - 81/x^2
        =    lim   ----------------------------------
            x->inf sqrt(1 + 9/x^2) + sqrt(1 + 81/x^4)

                              9 - 81/x^2
        =    lim   ----------------------------------
            x->inf sqrt(1 + 9/x^2) + sqrt(1 + 81/x^4)

        =   9/2

    Also:

	Concerning a newsgroup, I prefer the name sci.math.iams over
    sci.math.recreational because (1) it is shorter, (2) IAMS does
    not necessarily restrict its concerns to recreational math, and
    (3) sci.math.recreational is a pseudonym for rec.math.

	I also agree that the group should be moderated.  We have all
    suffered the garbage that spews out of sci.math when idiots lock
    horns.  I would like to see sci.math.iams avoid this.




From: williamw@ee.ubc.ca (william wong)
Subject: Re: SPOILER to POD #2

	
	From: "David W. Wilson" <wilson@ctron.com>
	
	> 2)  evaluate the limit as x approaches infinity of
	>       x sqrt(x^2 + 9) - sqrt(x^4 + 81)

	    we have

	         lim   x sqrt((x^2 + 9) - sqrt(x^4 + 81)
	        x->inf

	                              9x^2 - 81
	        =    lim   --------------------------------
	            x->inf x sqrt(x^2 + 9) + sqrt(x^4 + 81)

	                              9 - 81/x^2
	        =    lim   ----------------------------------
	            x->inf sqrt(1 + 9/x^2) + sqrt(1 + 81/x^4)

	                              9 - 81/x^2
	        =    lim   ----------------------------------
	            x->inf sqrt(1 + 9/x^2) + sqrt(1 + 81/x^4)

	        =   9/2


Alternative solution:

  lim   x sqrt((x^2 + 9) - sqrt(x^4 + 81)
 x->inf

= lim   x^2 ( sqrt(1+9/x^2) - sqrt(1+81/x^4) )
 x->inf

Using the expansion  sqrt(1+u) = 1 + u/2 - u^2/4 + . . .  for small u, 
we have (since 1/x^2 and 1/x^4 are small):

  lim   x^2 ( 1 + 9/(2x^2) - 81/(4x^4) +  . . .
 x->inf  
		- 1 - 81/(2x^4) + 81^2/(4x^8) -  . . . )

= 9/2


William Wong
University of British Columbia
Vancouver, Canada


From: t-davidw@microsoft.com
Subject: Apples and oranges


     Here's a pretty easy one for ya.  I'm told this is one of the
questions that has been asked at Microsoft's summer intern interviews.

     I've got three boxes.  One of 'em has some apples in it, one
has some oranges in it, and a third has a mix of both fruits.  Each
box has a label on it saying either "apples" "oranges" or "mixed",
but unfortunately they're all wrong.  I'd like to find out the correct
labeling for all the boxes, and I'm allowed to close my eyes and put
my hand in one box and grab a fruit from it.  How can I figure out
which labels belong on which boxes?

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


From: Van@cup.portal.com
Subject: 2 probability problems: solution to #1?

 re: Two probability problems:
 
 This only talks about the first, I haven't done the 2nd.
 
 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?
 =======
 
 All I can think of is that this might relate to the fact that
 the probability that any number begins with N (N = 1,2, ... ,9) is
 P(N) = log10(N+1) - log10(N).
 ============
 (Has this problem been discussed here yet? If not, its a good one.
 
 What is the probability that ANY integer > 0 begins with
 N, where N = 1,2, ... ,9 ?
 Answer is given above.)
 ======
  Since P(1) = log10(2) - log10(1) = log10(2) = .301
   P(2) = log10(3) - log10(2) = .477 -.301 = .176,  etc.
 
 Thus the probability that number begins with 1 or 2 is .477 < .5, and it
 is likely to be the smaller number.
 The probability that number begins with 4, ... , 9 is 1 - log10(4) = .4 <.5,
 so it is likely to be the larger number.
 If we look for the number x such that log10(x) = .5, x = sqrt(10) = 3.162.
 
 I don't think the decimals mean anything.
 
 I think if the first digits of the number are < sqrt(10), then it is
 likely to be the smaller number, and vice versa.
 
 van@cup.portal.com       Van


From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Re: 2 probability problems: not really a spoiler.


>  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?

I will assume that the numbers are positive integers.  

The probability is 100% that the other number is larger.  Let's say that the
number you gave me is N.  There are only a finite number of numbers less
than N, but there are infinitely many numbers greater than N.  Therefore,
the other number is larger with 100% probability.  :-)

P.S.  I earlier asked whether there is an infinite sequence of
1s, 2s, and 3s, such that no digit or sequence of digits appears
twice in succesion.  This is apparently a famous problem, and a
solution appears in the book "Challenging Mathematical Problems
with Elementary Solutions" by Yaglom and Yaglom.  This is a very
nice book, and it is published by Dover (so it is cheap).
Thanks to Tal Kubo for bringing this to my attention.

Dave  



From: t-davidw@microsoft.com
Subject: RE: 2 probability problems: solution to #1?


>
>> 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?
>
> All I can think of is that this might relate to the fact that
> the probability that any number begins with N (N = 1,2, ... ,9) is
> P(N) = log10(N+1) - log10(N).
>

     No, I think this only holds under certain assumptions about the
distribution of those random numbers - namely, that the distribution is
exponential.  N is exponentially distributed on the positive integers
if there's some constant k such that Pr{N>m} = exp{-km} for all integer
m>=0.

     I hope I've got that right...  I might have screwed things up
there, since I've always fallen prey to those `trick' probability
problems.  :-)

     I've also seen a somewhat similar puzzle: you pick one random
number N.  Then, you either give me N or 2N (randomly choosing one of
those two).  I'm supposed to guess what your other number is.  I saw
a proposed solution to that puzzle, so here it is:
*SPOILER*






































































     Here's the method: if you tell me an odd number, I'll guess that
it's the lower of the two numbers, and if you tell me an even one, I'll
guess that it's the higher.

     Let's work out how often I guess correctly.  There are four
cases here:    (1) N is odd, I get N
          (2) N is odd, I get 2N
          (3) N is even, I get N
          (4) N is even, I get 2N
I will guess correctly in cases (1), (2), and (4).  I'll be wrong in
case (3).  So the probability that I guess correctly is
          Pr{N is odd} + .5 Pr{N is even}.
Since Pr{N is odd} + Pr{N is even} = 1, we can rewrite that as
          ( Pr{N is odd} + 1 ) / 2.
So this will work better than randomly guessing `higher' or `lower'
whenever Pr{N is odd} > 0!  Hmm, I didn't remember that last little
bit there: I wonder if that means I did something wrong along the way?
:-)

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


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


OK, math-type people.  I don't know if this kind of series is new or not,
but I think its rather nice.  What's the next term of:

	    1, 1, 0, 1, 0, 7, 28, 79, ...

Or, in a vaguely similar vein:

	    5, 7, 11, 17, 29, 47, 83, ...

If you figure out one, the other should probably be easy.

	Brian Borowicz
	bboru@lobby.ti.com


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

>	    5, 7, 11, 17, 29, 47, 83, ...

I think I found the pattern for this one.
7-5  =2
11-7 =4 = 2*2
17-11=6 = 2+4
29-17=12= 2*6
47-29=18=12+6
83-47=36= 2*18

So next term is 137 because

137-83=54=18+36


Benjie


From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Re: Two Probability Problems (solution to first problem)

On Wed, 7 Jul 1993, Benjamin J. Tilly wrote:

> 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?

This sounds like it is impossible.  Let me see if I can prove that it
is impossible!  A strategy for this game will consist of the following:
given a number x, then with probability P(x) I will state that my
number is larger, and with probability 1 - P(x) I will state that the
other number is larger.

Suppose the numbers are {x,y}, with x < y.  There are two ways I can win:
  (1)  I am given x, and I state that the other number is larger, or
  (2)  I am given y, and I state that my number is larger.

The probabilities of these two events are (1/2) (1 - P(x)) and
(1/2) P(y) respectively, so my total probability of winning is
(1/2) (1 - P(x) + P(y)).

This probability has to be greater than 1/2 for any choice of x,y
with x < y.  This means that 0 < P(x) < P(y) < 1 for all x,y with
x < y.  Is this possible?  Of course it is!  For example,
P(x) = 1/2 + (1/pi) arctan(x) is one such function.

So, there is a winning strategy after all.  Notice, however, that
the probability of winning can be made arbitrarily close to 1/2 by
an appropriate choice of x and y.




From: claxnes@sandia.gov
Subject: Re:Spider on n-cube


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: williamw@ee.ubc.ca (william wong)
Subject: SPOILER: Apples and oranges

>	From: t-davidw@microsoft.com
>
>
>	     Here's a pretty easy one for ya.  I'm told this is one of the
>	questions that has been asked at Microsoft's summer intern interviews.
>
>	     I've got three boxes.  One of 'em has some apples in it, one
>	has some oranges in it, and a third has a mix of both fruits.  Each
>	box has a label on it saying either "apples" "oranges" or "mixed",
>	but unfortunately they're all wrong.  I'd like to find out the correct
>	labeling for all the boxes, and I'm allowed to close my eyes and put
>	my hand in one box and grab a fruit from it.  How can I figure out
>	which labels belong on which boxes?
>
>	David Wagner
>	t-davidw@netmail.microsoft.com or dawagner@princeton.edu


At first sight, it did not seem to me that there is a solution (Matter of fact,
I thought it was a stupid puzzle).  Then one of us (Joe) noticed the statement
about mislabeling of boxes, which made me jump out of my chair.
Here is our solution.


Fact #1
--------
	Since ALL the boxes are mislabeled, there are only two possible scenarios.
	I am using

		A   to denote a box of only apples
	       AAA 

		O   to denote a box of only oranges
	       OOO

		O   to denote a box of apples and oranges
	       OOO


	Scenario #1

	Label		"oranges" 	"mixed"		"apples"

			 A		 O		 O
	Content		AAA		OOO		AOA

        -------------------------------------------------------------

	Scenario #2

	Label		"mixed" 	"apples"	"oranges"

			 A		 O		 O
	Content		AAA		OOO		AOA


Fact #2
--------
	If you go to a box labeled "mixed",  from Fact #1, you know for sure
that it actually contains fruits of a single kind.  
For example, if you pick a fruit from the box labeled "mixed", you get an orange
from Scenario #1 and an apple from Scenario #2.


To solve the puzzle,
Step I
--------
	Go to the box labeled "mixed" and pick out a fruit.   Assume that Scenario
#1 holds and you draw out an orange.  Therefore, you know that that box contains
oranges only.

	Label		"oranges" 	"mixed"		"apples"

			 		 O		 
	Content		??		OOO		??

Step II
--------
	Look at the box with a label that bears the name of the fruit you just
picked.  In this case, you'll look at the box labeled "oranges".  Because of
mislabeling, it can contain either apples or mixed fruits.  But it cannot
contain mixed fruits, otherwise the box labeled "apples" will contain only 
apples!!

Therefore, you know that the box labeled "oranges" contains only apples:

	Label		"oranges" 	"mixed"		"apples"

			 A		 O		 O
	Content		AAA		OOO		AOA

Remark:  If you repeat the above procedure with Scenario #2, you'll get
a consistent answer.


William Wong and Joseph Yan
University of British Columbia
Vancouver, Canada


From: t-davidw@microsoft.com
Subject: Another Microsoft interview question


     Ok, a few people got the previous puzzle I posted right, so I
thought I'd post another one.  It's kinda contrived, but hey, it may
prove some entertainment value.  :-)  These are all phrased as computer
questions, but you can think of them as math questions: the only
special operations you'll really need to use are boolean ANDs, ORs,
NOTs, XORs, etc.

     I guess I should briefy state how boolean operations work?
The NOT operation looks at the binary representation of a number and
changes all the 1s to 0s, and all the 0s to 1s.  So 01001110 would
become 10110001 (in binary).  The OR operation looks at the binary
representation of two input numbers; the output number has a bit set
in a certain position iff at least one of the input numbers has a
bit set there.  So 00001011 OR 10000000 is 10001011.  The AND operation
is like OR, except it sets a bit in the output number iff both of
the input numbers have bits set in the corresponding position.  Thus
00001011 AND 10000000 is 00000000.  Finally, XOR is like both OR and
AND; it sets a bit in the output number iff exactly one of the input
numbers has a bit set in the corresponding position.  So XORing with
all 1s (11111111 for example) is equivalent to doing a NOT.  Ok, I
think that's all the background you need to know...  And most likely
everyone here knew all that already :-)  Now come up with a method
to do each of the problems listed below:

[1] Given a data word X, test if it is a power of 2.

[2] Given a data word X, return the number of bits set in the binary
representation of X.

[3] Do [1] and [2] above without any conditionals or loops; try and
find one short expression that works.  (The answer is a trick, sorta.)

[4] Ok, now for a little trickier one.  You're given a data word X and
a mask word M.  The mask word M will have exactly two bits set in it's
binary represenatation.  The two bits that are set in M are used to
select a corresponding pair of bits in the data word X.  Your task is
to exchange those two bits in X, leaving all the other bits undisturbed,
and return the result.  An example may make this a little clearer; let
M=00100001.  If X=00001111, you should return 00101110.  If X=11111111,
you should return 11111111.  If X=10101010, you should return 10001011.
Does that make sense?

[5] Now try and do [4] above without any conditionals or loops; the
original reasoning was that including conditionals and loops makes for
slower code, if they're not needed - but it's still interesting, just
on theoretical grounds, to do [5] without worrying about the speed or
the representation inside the computer.  Just try and find some neat
and interesting improvement of your solution for [4].  (How's that for
a nice and well-defined puzzle problem? :-)

     I have answers for the first four, by the way - though you guys
shouldn't have too much trouble doing them on your own.  I *think* I may
have found a semi-interesting way to do [5] (ie without using any 
conditionals
or loops), but I'm not sure yet.  I'd love to see what you guys come up
with!  And oh yes - I've yet to find a practical application for these in
the programs I've written so far.  So that MUST make them a valid math
question, right?  :-)

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


From: Van@cup.portal.com
Subject: random numbers > 0

How many of those in the IAMS group have run into the following:
 
In the decimal system, if you take a set or table of completely random numbers 
greater than 0, log10(2) of them will begin with 1.

This was first noticed by people who looked at tables of lengths between towns 
or populations of cities (towns, villages) of all sizes, or any other type of 
table where the numbers run over several orders of magnitude.

Someone once said that looking at a slide rule will give you some idea about 
what it going on here.

One can ask what fraction will begin with 1,2,3, ... , 9,
 as I did in a previous post.

van@cup.portal.com      Van


	id AA29523; Fri, 9 Jul 1993 06:06:01 -0400
From: s.virtes@genie.geis.com
Subject: binary problems

David,
 
   Your binary problems were interesting.  After some playing
around, I found the following ....
 
   Since folks may still be working on this, I'll post a
standard-looking
 
 
 
   **************** SPOILER WARNING ************************
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    ( I think that's enough space! )
 
    [1]:  How to identify a power of 2.
          If X = 2^n, then  X AND (X-1) = 0.
 
    [2]:  I didn't get a general loopless algorithm for counting
          the number of bits set, but I found it interesting
          that:
          If the number of bits ON is 2, then:  X AND (X-2) = 2^n.
          Or:  X AND (X-2) AND (X-3) = 0.
 
    [5]:  I was primarily interested in #5.  I'll use X MASK M
          to represent this masking operation. The quickest thing
          I could find (so far!) was:
 
          If X AND M = 2^n then X MASK M = X XOR M, else
             X MASK M = X.
 
    Thanks for the ideas.  I drew up some quick assembly
routines to check the results for bytes and unsigned integers.
Wish I had more time to work on them!
 
    - scott


From: Van@cup.portal.com
Subject: Two Probability Problems

 Re: Two Probability Problems (solution to first problem)

 David G Radcliffe <radcliff@csd4.csd.uwm.edu> wrote:

>On Wed, 7 Jul 1993, Benjamin J. Tilly wrote:
>
>> 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?
>
>Suppose the numbers are {x,y}, with x < y.  There are two ways I can win:
  >(1)  I am given x, and I state that the other number is larger, or
  >(2)  I am given y, and I state that my number is larger.

>This probability has to be greater than 1/2 for any choice of x,y
>with x < y.  This means that 0 < P(x) < P(y) < 1 for all x,y with
>x < y.  Is this possible?  Of course it is!  For example,
>P(x) = 1/2 + (1/pi) arctan(x) is one such function.

 ============

I don't think you can just pick any probability out of the air.

Using this argument, there are 2 ways to win and 2 ways to lose,
 all of which have equal probability, so I don't see how knowing one
number gives you any advantage in this situation.

I'm not sure that my solution, using the fact that numbers which
 begin with N appear with a probability

 P(N) = log10(N+1)-log10(N) = log10[(N+1)/N]

works either, but it looks to me like it could give you some info on
whether you have been shown the larger number.

I could very well be mistaken though.

van@cup.portal.com


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


Problem 5: Assume there are two containers, A and B, of marbles: the
first (A) containing 15 black marbles and the second (B) containing 10
white marbles.  If a person is blind folded and selects 5 marbles from
A and places them into container B, mixes them throughly and then draw
5 marbles from container B and places them back into container A and
then do these two transfers one more time, what would be the ratio of
the number of white marbles in container A to the number of black
marbles in B?

-----------------------
This problem came out to be an easy one.  I guess I didn't give it a
thought when I found it in my problem book.  Here is a solution from
David Wagner.
-----------------------
Solution: From David Wagner

     The ratio is one.  In fact, it doesn't matter how many times
you repeat the of those two transfers - the number of white marbles
in A is the same as the number of black marbles in B.

     How do I prove that?  I'll do it by induction.  I wish I had
a real clear way to show just how obvious this claim is, but I don't,
so I'll cloud the issue in notation, and then solve it.  :-)  Denote
the state of either jar by a 2-vector: (blacks, whites) which tells
the number of (you guessed it!) black marbles and white marbles in
that jar.

     Ok, so our inductive assumption is that to start with, the
number of white marbles in A is the number of black marbles in B.  So
A=(15-n, n) B=(n, 10-n) in my notation.  In the A->B transfer, we take
away (5-j, j) from A and put it in B.  [j could be any number from 0
and 5; we don't care what.  Actually j is constrained to be in the
range 0<=j<=15-n also, but that's nitpicking. :-]  So after the A->B
transfer, A=(10-n+j, n-j) B=(5+n-j, 10-n+j).

     Then we do the second transfer: take (5-k, k) away from B and
put it in A.  [The restrictions on k are similar to those on j.]  Then
the state is A=(15-n+j-k, n-j+k) B=(n-j+k, 10-n+j-k).  We could, of course,
calculate the probability distribution for j (it's easy) and then calculate
the probability distribution for k (not quite so easy).  But there's no
need - look what marvelous things just happened!  No matter what values
of j and k we picked, we'll still have n-j+k = n-j+k (that is, the number
of white marbles in A is the same as the number of black marbles in B)!
So this completes the inductive step.

     Since the base case is stipulated in the problem, we get that no
matter how many times we apply that double transfer, it remains the case
that the number of white marbles in A is the same as the number of black
marbles in B.  So the ratio remains one.

     Here's one way to make the solution a little clearer, and for
it to make a little more sense (ie be a little less surprising).  Look
at the case when A starts out with the same number of marbles as B does.
So pretend A starts out with 10 black marbles, and B starts out with 10
white ones.  Now it should be fairly obvious after a second's thought
that the total number of white marbles in the two jars is always conserved;
this leads immediately to the conclusion that the number of white marbles
in jar A is the same as the number of black marbles in jar B, no matter
how many double transfers you apply.

     This last problem (with each jar starting out with the same number
of marbles) was posted to the rec.puzzles newsgroup a few weeks ago.
I like the generalization that you posted for the contest quite a bit
better, to tell you the truth. :-)  Thanks for a neat problem!


--------------------
Correct Solutions Were Sent In By:

alanm@outage.efi.com 
gaps05@udcf.gla.ac.uk 
jhardin@gandalf.pnl.gov 
radcliff@csd4.csd.uwm.edu 
"ENG::LPOMEROY"@gemini.sim.es.com 
bboru@mkcase1.dseg.ti.com
a_rubin@dsg4.dse.beckman.com 
t-davidw@microsoft.com
arodgers@dcs.qmw.ac.uk 
martino@rob.csata.it


Congrats

Benjie


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


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).


Enjoy

Benjie


From: Van@cup.portal.com
Subject: probability of the first digit

 I have been met with disbelief with my presentation about the probability of 
the first digit. I know there are problems with it, but here is my first post 
from long ago.

As suggested below, anyone curious enough about this may want to consult

Volume two of Knuth's "Semi-Numerical Algorithms".

 ========
 Here is an interesting, non-intuitive puzzle I found on Usenet sci.math.
 =========
 Here is an old gem along these lines.  A positive integer, in its decimal
representation, begins with one of nine possible digits.  What proportion of
them begin with the digit '1'?

 Here is an exercise (alleged to work, I haven't done it...): Take the front
page of the New York Times.  Write down in decimal form all of the numbers
mentioned.  Then about 30% of the numbers will begin with the digit '1'.

Or, take an atlas, and look up the lengths of the rivers (in km). About 30% of
them begin with the digit '1'.  Repeat, using miles. Still 30%.

In what sense can the answer 'about 30%' be made precise?

If you have seen this before, wait a few days before posting answers, so that
others have some time to think about it...
 
  Gerald A. Edgar                Internet:  edgar@mps.ohio-state.edu

===============

J.MCGOWAN15@genie.geis.com

(a hint for the last question, as regarding the relative probs. of the first
digit in any base, consider logs! Volume two of Knuth's "Semi-Numerical
algorithms" has a nice approach to making the result concrete... that is
proving it in some sense.. unfortunately just averages does not have a limit)
================


From: Van@cup.portal.com
Subject: Probability of the first digit

J.MCGOWAN15@genie.geis.com

       The frequency of occurrence of real numbers starting with "1".


There is a difficulty in considering reals (or large integers) written in
floating point format (0.xxxxx*10^(exponent)) (first "x" non-zero) and
wondering about the fraction of those numbers from zero to one that have the
first non-zero "x" being one... for what probability distribution do they
have?... if uniform, then the prob is 1/9!

                                    +-+-+

Consider the following heuristic argument (base 10, looking at first
digit=1)...

Let us assume there is some probability function P(x) being the probability
that one picks a number from 0 to x.

Let us restrict to picking numbers (with some probability distribution, which
we want to discover) from the positive real numbers. Let P(x) be the
probability of picking one between zero and "x". We would like to consider,
P(10y)-P(10x)... for example, if x=.01, y=.03 what is the probability of
picking a number from .1 to .3? As these are real numbers, it should not
matter where the decimal place is! that is,
 P(10y)-P(10x)=P(y)-P(x)...

let us replace 10 by 1+c (for other bases) and rewrite as

  P(x+cx)-P(x)=P(y+cy)-P(y) or:

 (P(x+cx)-P(x))/(cx)*(x)=(P(y+cy)-P(y))/(cy)*(y)

Now suppose we could let c tend to zero (heck we cannot, be want integral
bases, but let's do it anyhow) to get:

 P'(x)*x=P'(y)*y... or P'(x) is a constant over "x" (i.e. is proportional to
1/x, or P(x) is a constant plus a constant times the natural logarithm of
"x").

What is the prob that a number starts with a "one"? It is

 P(1.9999999)-P(.9999999)=P(2)-P(1)

 (same as P(.2)-P(.1), same as P(.002)-P(.001) as we assumed P(10x)-
P(10y)=P(x)-P(y))...

 the prob that a number starts with a two is P(3)-P(2), etc..... and
P(x)=r*LN(x)+some unimportant constant of integration...

 this gives

 r(LN(2)-LN(1)+LN(3)-LN(2)+LN(4)-LN(3)+...+LN(10)-LN(9))=1

(sum must be one) or r*LN(10)=1,

 r=1/LN(10) and P(x)=LN(x)/LN(10)+a constant of integration (as we only want
P(y)-P(x), this constant is unimportant)=log10(x)+unimportant constant.

with the prob that a number starts with a "one" of P(2)-P(1)=log10(2).

                                    +-+-+

Why did I call it a heuristic argument? We wanted to have P(10x)-P(x)=P(10y)-
P(y) a constant... but then P(10)-P(1)=P(100)-P(10) etc. to we have the sum of
P(10^n)-P(10^(n-1))=infinity (unless P(10)-P(1) is zero!)... we have ignored
the fact that there are infinitely many intervals that have a starting digit
of one, and instead just have heuristically compressed them to one (in real
numbers, the probability of picking a number from 1 to 10^100 is zero!) and
have just compressed these infinitely many terms of prob=0 into one term
without any deep understanding of how it was done... (but using P(10y)-
P(10x)=P(y)-P(x))... the work in Knuth's book (taking averages of averages of
averages ad infinitum and limits) IS the justification for doing this
"compression"... but the heuristic argument may satisfy some sense of
"rightness" that the formal limiting process does not.

(I believe that Knuth's "Semi-Numerical Algorithms", Vol. 2, has a similar
heuristic argument along with the formal argument)

(I have a vague recollection that the problem originated among calculators who
noticed that the early pages of table of logarithms got dog eared faster than
the later pages, back when logs were used, and that a heuristic argument was
soon found... but took awhile for a formal argument to come along to verify
the heuristics)
 ============
 
Note, there is also a formal proof if anyone wants to see it.

van@cup.portal.com


From: Van@cup.portal.com
Subject: prob of 1st digit

J.MCGOWAN15@genie.geis.com
Respond to van@cup.portal.com

The frequency of occurrence of real numbers starting with "1".

OK... look at numbers up through "n"... and look at the frequency of occurence
of numbers starting with a "one".

 For n=1 we have   1/1
     n=2 we have   1/2
     n=3 we have   1/3
 ...
     n=9 we have   1/9
     n=10 we have  2/10
     n=11 we have  3/11
 ..
     n=19 we have  11/19

 ..  n=19999xx999 we have about 1/2 (all numbers from 10000xx000 to
 19999xx999) and some of the lower numbers) but for numbers up to:
 ..  n=99999xx999 we have about 1/9 (only numbers less than 19999xx999).

 Let F(1,n) be the percentage of numbers from 1 through n with start with a
 "1"... and we have:

 LIM(n increases without bound) F(1,n) does NOT exist... but has a limit
 superior (limsup) of 1/2, and a limit inferior (liminf) of 1/9.

 NOW IF the limit existed we would call it P, the percentage of numbers that
 start with a "one"... well, let's call the limsup=A(1) and the liminf B(1).

 Now if we were to talk about P, it must be between A(1) and B(1)... but as
 the limit does not exist... what is P?

 So we let:

 F(2,1)=(F(1,1))/1
 F(2,2)=(F(1,1)+F(1,2))/2
 F(2,3)=(F(1,1)+F(1,2)+F(1,3))/3

 F(2,n)=average of F(1,j) for j up to n.

 If F(1,n) does not have a limit, we may look at the limit of F(2,n) (as n
 increases without bound) and IF this limit exists, call it P, the percentage
 of numbers starting with a "one"... but F(2,n) does NOT have a limit, but
 has a limsup (called A(2)) and a liminf (called B(2))... drats....

 So we look at F(3,n)=average of F(2,j) for j up to n.

 Does it have a limit... answer, NO... but it has a limsup=A(3) and
 liminf=B(3)...

 and F(m,n)=average of F(m-1,j) for j up to n with limsup=A(n) and
 liminf=B(n).

 Now if ever there were something we could talk about as the "percentage" of
 numbers starting with "one", it would have to be between A(1) and B(1) and
 between A(2) and B(2) and between A(3) and B(3) etc..

 But A(m) is a decreasing sequence with a limit=A and B(m) is increasing with
 limit=B=A=log(base10)(2).

 The calculations are done in Knuth's Semi-Numerical Algorithms (vol. 2) with
 the result that for people that use base K, the percentage of real numbers
 that start with the digit J (0<J<K) is:

 P(K,J) = log(base K)(J+1) - log(base K)(J)

 with sum of P(K,J) for J=1 to K-1 being:

 log(base K)(K)-log(base K)(1) = 1-0 = 100%

                                    +-+-+

 This is a very formal result (see Knuth for the details of the calculation),
 but there IS a heuristic argument that leads to the same result! (that is
 for another post, however).

(A note... above I talk about the limsup and liminf if F(m,n) as n increases
without bound and called them A(n) and B(n).... of course that should have
been A(m) and B(m)!... sorry about that)


From: David G Radcliffe <radcliff@csd4.csd.uwm.edu>
Subject: Re: Two Probability Problems (spoilers ahead)

On Fri, 9 Jul 1993 Van@cup.portal.com wrote:

>  Re: Two Probability Problems (solution to first problem)
> 
>  David G Radcliffe <radcliff@csd4.csd.uwm.edu> wrote:
> 
> >On Wed, 7 Jul 1993, Benjamin J. Tilly wrote:
> >
> >> 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?
> 
> I don't think you can just pick any probability out of the air.
> 
> Using this argument, there are 2 ways to win and 2 ways to lose,
>  all of which have equal probability, so I don't see how knowing one
> number gives you any advantage in this situation.

Recall my strategy:  I have a function P such that if x < y then
0 < P(x) < P(y) < 1.  When I get a number x, I will make a random decision:

  With probability P(x),     I will say "mine is bigger."
  With probability 1 - P(x), I will say "the other one is bigger."

The two numbers are x and y.  x is less than y.  There are 4 possibilities:

(A)  I get x.  I say "mine is bigger."               I lose.
(B)  I get x.  I say "the other one is bigger."      I win.
(C)  I get y.  I say "mine is bigger."               I win.
(D)  I get y.  I say "the other one is bigger."      I lose.

The probability of each event is

(A)  (1/2) P(x)
(B)  (1/2) (1 - P(x))
(C)  (1/2) P(y)
(D)  (1/2) (1 - P(y))

My probability of winning is (1/2) (1 - P(x) + P(y)), and my probability
of losing is (1/2) (1 + P(x) - P(y)).  Since P(x) < P(y), my odds of
winning are better than 1/2.

> I'm not sure that my solution, using the fact that numbers which
>  begin with N appear with a probability
> 
>  P(N) = log10(N+1)-log10(N) = log10[(N+1)/N]
> 
> works either, but it looks to me like it could give you some info on
> whether you have been shown the larger number.
> 
> I could very well be mistaken though.
> 
> van@cup.portal.com

You cannot assume that your opponent will choose the two numbers
at random; you only know that he will choose randomly between them.




From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly)
Subject: Re: prob of 1st digit

The only reason that I am sending this to everyone is that the person that I
was talking to on e-mail kept on sending some comments to the mailing list. I
do not intend to respond again on the mailing list, but if he does then I
would ask for people to send him notes saying that this is not the place to
carry on this conversation. I for one do not want others to take their side
of disputes to the mailing list, it just clogs up peoples mail and starts
flame wars which are not what I want out of this list.

It is time to put this topic of the "probability" of the first digit of a
random real being 1 to rest. The calculation that you gave can be formalized
to give an intuitive reason to certain observed phenomena. However it is
_not_ probability theory. If you are interested in probability theory you
should read a book on it, not a computer science book. The way that
probability theory works is that it starts with a probability distribution
and works out the probabilities of various events from that distribution. If
you do not have an actual probability distribution you are not able to talk
about the probability of events in the sense that is accepted in mathematics.
Period. For references I could name any introductory probability theory book,
for example A FIRST COURSE IN PROBABILITY by Sheldon Ross. Read especially
section 3 of the second chapter where the axioms of probability theory are
given. You will see that the concept of a completely random number without
stating what the distribution is does not make sense within probability
theory. Furthermore I wish to repeat that it is a standard result that there
is no uniform distribution on the reals, positive reals, integers, or on the
nonnegative integers. This follows easily from the third axiom which is that
the probability of a countable union of mutually disjoint events is the sum
of the probabilities. Thus the uniform distribution on the integers, for
example, would have the proabability of some integer being picked being the
sum over all of the integers of the probability of that integer being picked,
which is 0. Therefore the probability of picking some integer is 0, contrary
to the second axiom that the probability of picking something is 1. Therefore
there is no uniform distributin on the integers. The other cases all follow
similarly.


And again I am sorry for taking this on the list when it should have been
part of a private conversation.

Ben Tilly


From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly)
Subject: Prob. Spoiler

Here is my promised spoiler.

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?

Solution: David Radcliffe already sent around one solution of this very
strange result. For another solution I can use the following algorithm. I
will pick a random number out of a normal distribution and pretend that it is
the one that you still have. If the one that you gave me is larger then I
will say that you gave me the larger number, otherwise I will say that you
gave me the smaller number. Now I will have better than even odds of getting
the right answer. Why? Well there are 4 cases. The first case in which I
randomly picked one of the two numbers that you started with has probability
0 because the normal is a continuous distribution. The second in which I
picked a number that is smaller than both of your numbers I will think that I
have the larger-and there is a 50% chance that I am right. The third is that
I pick a number that is bigger than both of yours in which case I will think
that I have the smaller-and again I have even odds of being right. The last
case is where I pick a number that is between your two-in which case I am
right. As there is always a positive probability of the last case, and the
others which happen with positive probability give me even odds I have better
than even odds, as a matter of fact they are better by 1/2 the probability
that I pick a number between your numbers. (This can be interesting to model
on a computer.)

2) (The compulsive gambler.) You have some money which you are going to
invest by betting with it. The way that the bet works you place whatever bet
you want and with probability p you win and get r times whatever you bet as a
payoff and if you lose you get nothing. You know what p and r are and pr>1 so
it is worth your while to bet. Your invesment strategy is to bet repeatedly
and each time to bet a porportion x of all of your money. The question is
what your best invesment strategy is.
    a) What strategy maximizes your expected worth after n bets?
    b) With what probability do you go broke eventually playing the strategy
in a)?
    c) Is there a strategy x such that if person one plays strategy x and
another person is playing any other strategy y, then with probability 1 the
first person will eventually be wealthier? If so find it. (Note: probability
1 means 100% chance.)

Solution: It will help if I adopt a little notation. The amount of money that
I start with I will call c. Each bet multiplies my money by a random value. I
will call the amount that it is multiplied on the n'th be X(n). And for those
who do not know, my exepected worth means the weighted average of the
possible amounts of money that I could have, each amount weighted by its
probability.

   a) The answer is to bet everything every time. First think about my
expected worth after the n'th bet. Note that if I am given the outcomes of
the first n-1 bets then I find that the average value after one more bet is
the amount after the first n-1 bets times E(X(n)) = the expected value of
X(n). Thus the expected worth after n-1 bets is multiplied by E(X(n)) to get
the expected worth after one more bet. Therefore the expected worth after n
bets is easily seen to be c E(X(1)) E(X(2)) . . . E(X(n)). Therefore the
strategy to take is to maximize the expected value would be to maximize each
of the E(X(i)). But if we are using strategy x then with probability p we
multiply our money by rpx + 1-x because with probability p we win,
multiplying the money that we bet (x of the total that we had) by r, and no
matter what we keep what was not bet which is 1-x. But it was specified that
pr>1 and so the larger x is the larger the expected value is. As x is at most
1, the best strategy is to bet all of it every time.

   b) The strategy is to bet it all. That means that if we lose any bet, we
go broke. But there is a probability of 1 that we will lose eventually unless
p=1 in which case we cannot lose. Therefore unless p=1 we will go broke
eventually with probability. This seems strange because we wanted a good
method of investing money, but it works because after a lot of bets there may
be a small chance that you have any money, but if you do then you are _very_
rich, so it averages out to be a lot of money.

   c) It is clear from b) that if the strategy that we want exists then it is
not the one in a). But there are nice theorems about what happens when we add
random variables together so let us try to make an addition problem. The easy
way to do that is to take ln of everything. Thus ln(worth after n bets)=ln(c)
+ ln(X(1)) + ln(X(2)) + . . .  + ln(X(n)). By the strong law of large numbers
we know that the limit as n goes to infinity of (ln(X(1)) + ln(X(2)) + . . . 
+ ln(X(n)))/n = E(ln(X(1))) (since all of the X's are identically distributed
and each bet is assumed to not depend on the last one). Therefore the
strategy that maximizes E(ln(X(n))) is the one that does what we want. But
E(ln(X(1))) = p ln(rx + 1-x) + (1-p)ln(1-x) and therefore by a
straightforward max-min procedure we find that the answer is x=(pr-1)/(r-1).


From: kubo@math.harvard.edu (Tal Kubo)
Subject: Probability of the first digit



Contrary to what was stated, the first digit problem has a perfectly
respectable mathematical formulation.  For example, one could choose
real numbers uniformly in [1,...,N], compute the probabilities, and
let N grow to infinity.  Or the same, but with integers instead of
reals. The problem alluded to about not having a uniform measure on a
non-compact set is true, but it's not really important here.

The point is, if nonzero reals are chosen uniformly with respect 
to addition, but are rescaled with respect to multiplication, i.e.

           real ---> (sign,mantissa,exponent)
            R   --->  +/-     M    * 10^E ;    1 < M < 10; E integer

then the mantissa  M  is uniform with respect to multiplication.  The set
of values of the mantissa is a finite interval -- [1,10), so the measure on
this can be normalized to be an actual probability measure.  Logarithms
appear because they translate between addition of reals (and hence, the
addition invariant measure on the reals -- length of interval) into
multiplication (and hence, the multiplication invariant measure on the
interval -- logarithm of ratio of endpoints).  Specifically, the
probability that the decimal expansion of the positive part of  M  lies in
interval  [A,B],  1 < A < B < 10,  is proportional to  log(B/A).
Considering A=1, B=10, the constant of proportionality is  1/log(10). So
the probability that a random real has a mantissa between A and B is log_10
(B/A).   In particular, taking A=1, B=2, the probability that the first
digit is 1  is  log_10 (2); the probability of first digit 2 is log_10
(3/2), etc.

By the way, Knuth's book which was mentioned as a reference, is more
rigorous than most probability books, and contains more math than most 
math books.  It also contains a lot of material in probability and
combinatorics which is (or at least wasn't when the book came out) not
mentioned in most textbooks, the first digit problem being just one
example.







From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly)
Subject: Re: Probability of the first digit

Given the response that I have recieved for my part in the conversation about
this problem I am posting this explanation. The source for my information is
a number of references to this problem, and conversations with several
people. First the usual reaction from people that I know in math to the
question of what the probability is of the first digit in a truly random real
is to ask what you mean by a truly random real since there is no such thing.
However there is a pattern called Zipf's law which has been noticed in a
number of situations which is the answer that has been quoted involving
logarithms. There have been a number of explanations put forth as to why this
works, including the one given by Knuth. Before going into that some
background is in order.

The standardly accepted formulation of probability starts with a set, like
the real line, and a probability distribution. The probability distribution
assigns different probabilities to different subsets of the set and obeys
some basic axioms. Within this formulation there is no uniform distribution
on the reals which is what we would like to mean by "truly random" for the
reason that I explained in another post. However there are procedures that
are sometimes done to try and make sense of what we would want to mean by
that idea. The most common idea is to take uniform distributions over an
arbitrary interval and ask about the probability of some statement. Then take
the limit of the answer as the size of the interval goes to infinity. This is
what people do when they talk about the "probability" that a random integer
is divisible by 7. Firstly you can make sense of some statements, but you are
now not dealing with probability theory because it does not satisfy the
axioms. However with this standard formulation you find that the probability
of the first digit being a 1 is not well-defined. By a much more complicated
construction Knuth uses a limiting process involving averages of averages of
averages...-that does give an answer. And it is the answer involving
logarithms. However what exactly this formal process really does is a little
unclear. Another way to approach the question is to look at the positive
reals as having a group of symmetries involving multiplication. Now there is
a natural version of the uniform probability on an interval, one way to
construct it is to take the uniform distribution on the log's of the values
in the interval. Then take the limit in the same way as before as the
intervals are stretched to cover the positive reals. This again gives the
same answer to our question.

What this means is that out of 4 ways to approach the concept of what the
probability was half gave the log answer, and the other half (including the
stadard formulation) said that it could not be defined. However all of these
beg the question of why the pattern should show up in real life. But first,
does it alwaays hold in real life? The answer is no. There are many
collections of numbers that we call random like peoples grades on a test,
heights, sizes of feet, number of atoms that decay in a raidioac tive
sustance in 1 hr (just to name a few examples) for which this pattern fails.
There are others though for which it works. To see why this is look at the
standard formulation of probability theory. If you specify a "random"
experiment the idea is that there is some probability distribution that
describes the probabilities of possible results that you could have. For many
of the distributions that turn up the pattern about the logs fail. For
example it fails for the bell-shaped curve which is also known as the normal
distribution. For some, however, it works fairly well. In general it will
work well if there are similar probabilities of picking numbers of fairly
diffferent orders of magnitude. For instance look at the numbers that we run
across in computation. The main operations that we do are addition,
subtraction, multiplication, and division. Suppose that the numbers that we
start with are drawn from some fairly reasonable distribution. The first  2
have very little effect on the order of magnitude of the numbers that we are
dealing with. The last two shuffle the orders of magnitude around. Therefore
we expect that there should be some range of orders of magnitude that we run
across with fairly equal frequency. Therefore in computation it is no suprise
that the log rule works fairly well.

So what this means is that the log rule can be given a formal meaning, but
that meaning has little to do with whether it works. In a real life example
where it works we should look at the processes that are going on to
understand why it happens there in particular. There are many areas where it
does not work, but there are others where it does. I do not have a really
good answer to why it works in as many places as it does, but here is my
attempt. In processes which over some range do not really depend on scale for
some range of scales it should work fairly well. Since much of our world is
able to be described using fractals which have a sort of scale invarience it
is not a suprise that it works for as many things as it does. However there
are many places that are also important where it does not work. And the
statement makes no sense in standard probability theory. Therefore when the
problem was stated I think that there should have been some qualification put
in about this state of affairs.

I hope that this summary proves interesting to people.

Ben Tilly