Problem 47

ThePerfectHacker · #1 $Old$ March 1st, 2008, 07:13 PM

1a)Let $n$ be an odd positive integer. Let $\zeta = e^{2\pi i/n}$ prove that $x^n - y^n = \prod_{k=0}^{(n-1)} (x\zeta^k - y\zeta^{-k})$ .
1b)Let $f(z) = 2i\sin (2\pi z)$ and $n$ an odd positive integer. Prove that $f(nz) = f(z)\prod_{k=1}^{(n-1)/2} f\left( z + \frac{k}{n} \right) f\left(z - \frac{k}{n} \right)$ .

2)Each man of $n\geq 2$ men throws his wallet on the table, then every one picks up a wallet randomly. Find the probability the every person takes the wrong wallet.

3)Let $\text{C}_1$ and $\text{C}_2$ be circles with $\text{C}_1$ inside $\text{C}_2$ and tangent at a point on $\text{C}_2$ . Let $c_1,c_2,...,c_k$ ( $k\geq 3$ ) be circles in between $\text{C}_1$ and $\text{C}_2$ and tangent to $\text{C}_1$ and $\text{C}_2$ and to eachother adjacent circle. Let $a_1,a_2,...,a_{k-1}$ be the points of tangency of these circles with their neighbors. Prove that $a_1,a_2,...,a_{k-1}$ all lie on a common circle.
(Note: The solution I know does not use elementary geometry).

TwistedOne151 · #2 $Old$ March 1st, 2008, 09:50 PM

3. This proof isn't entirely rigorous, but contains all the major steps:

Let D be the point where $C_1$ and $C_2$ are tangent. Now let us define a Möbius transform $z'=M(z)$ that maps D to infinity, and let us indicate images under M by primes. Now, M maps $C_1$ and $C_2$ to parallel lines $C_1'$ and $C_2'$ . Thus $c_1',c_2,'\ldots,c_k'$ are circles tangent to the lines $C_1'$ and $C_2'$ and to the adjacent circles in the sequence. As they are tangent to both $C_1'$ and $C_2'$ , they are all the same size, and their centers lie on the line $C_3'$ parallel to $C_1'$ and $C_2'$ and halfway between them. We see also that $a_1',a_2,'\ldots,a_{k-1}'$ must lie on $C_3'$ as well. Thus if we have the circle $C_3=M^{-1}(C_3')$ in the pre-image, we see $a_1,a_2,\ldots,a_{k-1}$ all lie on $C_3$ .

--Kevin C.

ThePerfectHacker · #3 $Old$ March 1st, 2008, 10:06 PM

Excellent job. I would just be more specific, if $a$ is the tangency point, define $1/(z-a)$ be the the Moebius transformation, the rest follows as you said.

heathrowjohnny · #4 $Old$ March 1st, 2008, 11:06 PM

2. There are $n!$ total permutations of the $n$ wallets. Now number the wallets from $1$ to $n$ . The first person has a $\frac{n-1}{n}$ probability of picking a wrong wallet. You would have to use a computer for this "brute force" approach.

Or let $P(n,k)$ be the probability that given $n$ people with $n$ wallets, $k$ of them choose the wrong wallet. Then we want $P(n,n)$ . This is our "black box" case.

We know that $P(n,0) = \frac{1}{n!}$ (i.e. probability all people get their wallets). Also by axiom 3 (commonly in textbooks) $\sum_{k=0}^{n} P(n,k) = 1$ . So $P(n,k)$ is the probability that there are $k$ incorrect wallets chosen and $n-k$ correct wallets chosen. These are independent events, so we can multiply probabilities. We get $P(n,k) = \frac{1}{(n-k)!}P(k,k)$ . But this doesn't really give us $P(n,n)$ . So $\sum_{k=0}^{n} \frac{P(k,k)}{(n-k)!} = 1$ . Plugging in values, we get the following formula (there is a pattern, I suppose you could prove it by induction): $P(k) = \sum_{i =0}^{k} \frac{(-1)^{i}}{i!}$ .

So $P(n,k) = \frac{1}{(n-k)!} \sum_{i=0}^{k} \frac{(-1)^{i}}{i!}$ .

Thus $P(n,n) = \sum_{i=0}^{k} \frac{(-1)^{i}}{i!}$ . This is about $\frac{1}{e}$ .

Then the probability that not all the people take their wrong wallets is $1 - \frac{1}{e}$ (some people could take wrong wallets, while other people take correct wallets).

ThePerfectHacker · #5 $Old$ April 11th, 2008, 11:45 AM

Quote:

1a)Let $n$ be an odd positive integer. Let $\zeta = e^{2\pi i/n}$ prove that $x^n - y^n = \prod_{k=0}^{(n-1)} (x\zeta^k - y\zeta^{-k})$ .

Note that $z^n - 1 = \prod_{k=0}^{n-1} (z - \zeta^k)$ . Let $z=x/y$ and we get $x^n - y^n = \prod_{k=0}^{n-1} (x-y\zeta^k)$ . Since $0,1,...,n-1$ and $0,-2,-4,...,-2(n-1)$ are both a complete system of residues, since $n$ is odd it means, $\prod_{k=0}^{n-1} (x - \zeta^k y) = \prod_{k=0}^{n-1} (x-\zeta^{-2k}y) = \zeta^{-0-1-...-(n-1)}\prod_{k=0}^{n-1} (x\zeta^k - y\zeta^{-k})$ . But $\zeta^{-0-1-...-(n-1)} = 1$ the proof is complete.

Quote:

1b)Let $f(z) = 2i\sin (2\pi z)$ and $n$ an odd positive integer. Prove that $f(nz) = f(z)\prod_{k=1}^{(n-1)/2} f\left( z + \frac{k}{n} \right) f\left(z - \frac{k}{n} \right)$ .

This function has the property that $f(-z) = -f(z)$ and $f(z+1)=f(z)$ . Also, $f(z) = e^{2\pi i z} - e^{-2\pi i z}$ .
In the identity, $x^n -y^n = \prod_{k=0}^n (x\zeta^k - y\zeta^{-k})$ let $x=e^{2\pi i z}$ and $y=e^{-2\pi i z}$ . Thus, we get, $f(nz) = e^{2\pi i n z} - e^{-2\pi i n z} = \prod_{k=0}^{n-1} \left( e^{2\pi i z} \zeta^k - e^{-2\pi i z} \zeta^{-k} \right)$ . Note that, $e^{2\pi i z} \zeta^k - e^{-2\pi i z} \zeta^{-k}= e^{2\pi i z} e^{2\pi i k/n} - e^{-2\pi i z} e^{-2\pi i k/n} = e^{2\pi i \left( z + \frac{k}{n} \right)} + e^{-2\pi i \left( z + \frac{k}{n} \right)} = f\left( z + \frac{k}{n}\right)$ . This means, $f(nz) = \prod_{k=0}^{n-1}f\left( z + \frac{k}{n} \right)$ . Split the product to get, $f(nz) = f(z) \prod_{k=1}^{(n-1)/2} f\left( z + \frac{k}{n} \right) \prod_{k=(n-1)/2}^{n-1} f\left( z + \frac{k}{n} \right)$ . We know that $f(z) = f(z-1)$ (a property mentioned above) thus $f\left( z + \frac{k}{n} \right) = f\left( z + \frac{k}{n} - 1\right) = f\left( z - \frac{n-k}{n} \right)$ . Thus, $f(nz) = f(z) \prod_{k=0}^{(n-1)/2} f\left( z + \frac{k}{n} \right) \prod_{k=(n-1)/2}^{n-1} f\left( z - \frac{n-k}{k} \right)$ . But $\prod_{k=(n-1)/2}^{n-1} f\left( z - \frac{n-k}{k} \right) = \prod_{k=1}^{(n-1)/2} f\left( z - \frac{k}{n}\right)$ because the products run through the same values. And we have proven that $f(nz) = f(z) \prod_{k=1}^{(n-1)/2} f\left( z + \frac{k}{n} \right) f\left( z - \frac{k}{n}\right)$ .
----

This identity belongs to Leopold Eisenstein. With it we can give a very nice short proof of the Quadradic Reciprocity Law. In fact, Enrst Kummer called this (Eisenstein's) proof to be the most beautiful of all reciprocity proofs (Taken from my Number Theory book).

If anybody wants I can post Eisenstein's proof.