Conference rusure::math

> Problem A-1
> How many primes among the positive integers, written as usual in base
> 10, are such that their digits are alternating 1's and 0's, beginning
> and ending with 1?

If A(n) is the n'th one of these numbers (with n ones in its representation)
then
		   n		    n        n
		100   - 1	 (10  - 1)(10  + 1)
	A(n) = -----------   =   ------------------
		   99			99

For n > 2, the denominator cannot completely cancel either factor in the
numerator, so A(n) is composite [if n is even its factors are A(n/2) and
10^n+1, if n is odd its factors are (10^n-1)/9 and (10^n+1)/11].

A(2) = 101 is prime so the answer is one.

>	B-4. Can a countably infinite set have an uncountable collection of
>	non-empty subsets such that the intersection of any two of them is
>	finite?
 
Yes.  Take subsets of the nonnegative integers as follows:       

	For each nonegative real R, take the subset

		[R], [10R], [100R], [1000R], ...

	where [.] means "greatest integer in".

Any two different reals will yield subsets that are different and have a
finite intersection.

John

    (.2) is better if you restrict R to
    
    	.1 < R < 1
    
    Then
    
    	R = .abcd...
    
    yields subset
    
    	a, ab, abc, abcd, ...
    
    John

If you draw the diagonals of the square, you will see that the figure whose
area needs to be calculated (set of points closer to the center than to a side)
is symmetric in the four triangular quadrants. The actual shape of the boundary
of the figure in each quadrant is a parabola (the locus of points equidistant
from a point and a line). It is easier to calculate the area outside the curve
than inside it, as this area consists of two right triangles plus the area
under the parabolic curve. A little integration then yields the answer for the
probability of hitting the center piece:

		4*sqrt(2) - 5
		-------------
		     3

I knew I should have gone to my Complex Variables class instead of playing
touch football...

If you substitute w = conj(z) OR w = 1/z into the given equation you
get the same resulting polynomial, namely:

	    10        9
	11*w   - 10i*w  - 10i*w - 11 = 0

But, just because conj(z) and 1/z are roots of the same polynomial doesn't
mean they are equal, does it? (If so, we are done, because 1/z = conj(z)/|z|).
I mean, the 10 roots of this polynomial could be in pairs {a,b} such that
conj(a) = 1/b - what am I missing?

>	Problem A-4
>	If \alpha is an irrational number, 0 < \alpha < 1, is there a finite
>	game with an honest coin such that the probability of one player winning
>	the game is \alpha? (An honest coin is one for which the probability of
>	heads and the probability of tails are both 1/2. A game is finite if
>	with probability 1 it must end in a finite number of moves.)
 
Let alpha = . a1 a2 a3 . . . as a binary fraction.  The alpha game is a series
of flips f1 f2 f3 . . . that:

	ends in a win if aj = 1 and fj = heads
	continues if aj = 1 and fj = tails
	continues if aj = 0 and fj = heads
	ends in a loss if aj = 0 and fj = tails
    
It's finite because the probability of continuing past K flips is (1/2) ^ K.

The probability of winning is

	sum (j = 1 to infinity) of ((1/2)^j * aj)

or alpha.

John	

    I show this as a consequence of the fact for |z| = 1, 1/z equals its
    complex conjugate.

    Let
	 p(z) = a0 + a1 z + a2 z^2 + ... + an z^n

	      = an PROD(z-z[k])			in factored form

    Define a polynomial with the inverse conjugate roots of p(z)

	p*(z) = a0* z^n + a1* z^(n-1) + ... + an*

	p*(z) = a0* PROD(z-1/z*[k])		z* = complex congugate

    Now combine these to get

	q(z) = a0* p(z) - an p*(z)

	     = a0* an PROD(z-z[k]) - an a0* PROD(z-1/z*[k])

	     = a0* an (PROD(z-z[k]) - PROD(z-1/z*[k]))

    If |z[k]| = 1, q(z) vanishes.

    Applying this to 11 z^10 + 10i z^9 + 10i z - 11 we find

	-11 (  11 z^n + 10i z^9 + 10i z - 11 ) -
	 11 ( -11 z^n - 10i z^9 - 10i z + 11) = 0

    - Jim

    It occurs to me that there's a problem with the test in .7

    It could happen that the zeroes of p(z) and p*(z) can be paired
    up in such a way that z[i] = 1/z*[j], so the test is not sufficient.

    Something has to be done to rule this out - perhaps by showing that
    the zeroes of the derivative p'(z) lie within the unit circle, or
    that the radius of convergence of 1/p(z) is equal to 1... but this
    may be a bit messy, and it is probably better to use something
    peculiar about the polynomial given in the problem than make a general
    test.

    The problem was clearly posed to trip people up on this point :-)

    - Jim

> B-5. Label the vertices of a trapezoid T (quadrilateral with two
> parallel sides) inscribed in the unit circle as A, B, C, D so that AB is
> parallel to CS and A, B, C, D are in counterclockwise order.  Let s_1,
> s_2 and d denote the lengths of the line segments AB, CD and OE, where E
> is the point of intersection of the diagonals of T, and O is the center
> of the circle.  Determine the least upper bound of (s_1 - s_2)/d over
> all such T for which d is nonzero, and describe all cases, if any, in
> which it is attained.

The trapezoid T consists of two parallel chords AB and CD, as well as the
chords AD and BC. If you align the circle so that AB and CD are parallel to
the x-axis, they hit the y-axis at (0,a) and (0,b) respectively. Now...

		  2			   2
s_1 = 2 * sqrt(1-a ),  s_2 = 2 * sqrt(1 - b )

A little analytic geometry results in:

		      2				       2	      2
	(b-a)*sqrt(1-a )		     b*sqrt(1-a ) + a*sqrt(1-b )
d = ---------------------------- + a  =  ----------------------------------
		2	     2				2	     2
	sqrt(1-a ) + sqrt(1-b )			sqrt(1-a ) + sqrt(1-b )


d is zero only when the numerator is zero, which only happens when b = -a.

If you expand out (s_1 - s_2)/d and use the equality

 2    2		      2		     2		    2		   2
b  - a   = (b*sqrt(1-a ) + a*sqrt(1-b ))*(b*sqrt(1-a ) - a*sqrt(1-b ))

you get:
			     2		    2
(s_1 - s_2)/d = 2*(b*sqrt(1-a ) - a*sqrt(1-b )) except when b = -a

							      2
This attains its least upper bound of 2 whenever a = -sqrt(1-b ). In terms
of the original problem, the least upper bound is attained whenever AB and
CD lie on opposite sides of the diameter parallel to them both, and when

				  2
		s_1 = sqrt(4 - s_2 ), s_1 not equal to s_2

> Problem A-2
> Evaluate \int_0^a \int_0^b \exp(\max{b^2 x^2, a^2 y^2}) dy dx where a and
> b are positive.

This one is pretty easy if you draw the diagonal of the rectangle you are
integrating over, notice that the max collapses to one of its terms in
each triangle, and do the separate triangular integrations (reversing the
order of integration in the upper triangle). I got:

	   2 2
	  a b 
	 e     - 1
	-----------
	    ab

    Here I demonstrate that I'm an electrical engineer.

    By rotating the complex plane by 90 degrees we can transform
    the polynomial into the form

	    10      9 
	11 z  + 10 z  + 10 z + 11

    Consider more generally polynomials of the form

	               n      n-1
	p(z) = 	(n+1) z  + n z    + n z + (n+1)

    This is a reflexive polynomial and has roots symmetric with
    respect to inversions in the unit circle and the real axis (for the
    reasons in my first attempt...)  FWIW it could be the characteristic
    polynomial of a symplectic transformation, but that's of no real use.

    Let z be the ratio of a complex number and its conjugate

			   i t
	z = s / s*, s = r e	(in polar form)

    Then we have another polynomial after clearing the s* denominators

		n      n-1            n-1           n
	(n+1) s  + n s    s* + n s s*    + (n+1) s*

    Or, in polar form

	  n	     i n t    -i n t          i (n-2) t    - i (n-2) t
	r  [ (n+1) (e     + e        ) + n (e           + e           ) ]

    Or, in trigonometric form

	  n
	r   [ 2(n+1) cos(n t) + 2 n cos((n-2)t) ]

    The expression

	(n+1) cos (n t) + n cos((n-2)t)

    is that of modulated carrier, and has exactly n zero crossings per
    period.  Therefore, the n roots of the polynomial must lie on the
    unit circle.

    - Jim

    re: .11
    
    It appears to me that you have assumed what you are trying to prove. To
    say that z is the ratio of a complex number and its conjugate is
    equivalent to saying that |z| = 1 which is what one was supposed to
    prove.

    Re .12

	No, not quite... since there exist 10 principal values of theta
    that satisfy the trigonometric equation then there do exit 10 (different)
    values where |z| = 1 that satisfy the origional equation, and that is
    enough via the fundemental theorem of algebra.  It's OK to guess
    the existance of something and show it's consistant - that's how
    mathematical induction is used, after all...

	Note that we know no roots are zero, so it was permissable to
    assume r <> 0.

	I do think there may be a less armwave way of doing it but don't
    really see it offhand.

	There are general tests to see if a polynomial has all roots on
    the unit circle (or on the real axis) but these are kind of messy,
    involving sets of determinants, or continued fractions (when p(z)
    has real coefficients.)  More generally, one can find if a polynomial
    has roots in the lefthand plane to see if a transfer function is
    stable or not - but it's a lot of calculation to do it by brute force.
	
    - Jim

Problem A-3
Prove that if 11z^10 + 10iz^9 + 10iz - 11 = 0, then |z| = 1. (Here z is
a complex number and i^2 = -1.)
 
-----
I am new at this, but heres a thought... since z is not a root we can
divide by z^5 giving:

11z^5 + 10iz^4 + 10iz^-4  + 10iz^-5  = 0

letting z= r e^iw  and substituting we get

11 r^5 e^5iw + 10 r^4 e^(4iw+pi/2) + 10 r^-4 e^(-4iw +pi/2) -11 r^-5 s^(-5iw) =0

Taking the real and imaginary parts to equal zero we get two equations:

1.)  11 cos(5w) (r^5-r^-5) - 10 sin(4w) ( r^4-r^-4) =0
2.)  11 sin(5w) (r^5+r^-5) + 10 cos(4w) ( r^4+r^-4) =0

Multiply each equation by r^5 (r <> ) then
r-1 is a factor of 1 and not two, so r=1 and from 2

11 sin(5w) + 10 cos(4w) = 0 are solutions to the equation, with the
second one specifying 5 roots symetric with the real axis. 

(note e^iw= cos(w) + isin(w)) and cos(w+pi/2) = -sin(w) and sin(w+pi/2)= cos(w)
                                  sin(-w)=-sin(w) cos(-w)=cos(w) )

I did not understand the other notes so please forgive if this
is a duplication...

>> B-2. Let S be a non-empty set with an associative operation that is left
>> and right cancellative (xy = xz implies y = z, and yx = zx implies
>> y = z).  Assume that for every a in S the set {a^n: n = 1, 2, 3, ...}
>> is finite.  Must S be a group?

	Yes.

	Technically, a^n is first defined, say, by

		a^1     = a
		a^(n+1) = (a^n)a for n >= 1.

	But then since the operation is associative you can prove
	by induction that (a^n)(a^m) = a^(n+m).

	Now you prove that for each a there is an m such that there
	is an n such that a^n is an identity element for a^m, i.e.,
	(a^m)(a^n) = (a^n)(a^m) = a^m.  Then you prove that this a^n
	is in fact an identity element for all powers of a, i.e.,
	for a^k for all positive integers k and not just for k=m.
	Finally you show that there can be at most one identity element
	for powers of a.  So for each a, let e(a) be this unique
	identity element for powers of a.

	Note that in the above, if n > 1 then a^(n-1) is an inverse
	for a relative to its unique identity e(a), i.e., a(a^(n-1))
	= a^n = e(a), and that if n = 1 then a is its own inverse
	relative to its unique identity, since aa = a = e(a).

	Now consider different elements a and b, and consider e(a)
	and e(b), and prove that e(a) = e(b), establishing that S
	contains a unique identity element e (i.e., ec = ce for all c).

	At this point one has a unique identity element e and inverses
	for every element a relative to e, so S must indeed be a group.

	Dan