# Problem 47

• Mar 1st 2008, 05:13 PM
ThePerfectHacker
Problem 47
1a)Let $\displaystyle n$ be an odd positive integer. Let $\displaystyle \zeta = e^{2\pi i/n}$ prove that $\displaystyle x^n - y^n = \prod_{k=0}^{(n-1)} (x\zeta^k - y\zeta^{-k})$.
1b)Let $\displaystyle f(z) = 2i\sin (2\pi z)$ and $\displaystyle n$ an odd positive integer. Prove that $\displaystyle 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 $\displaystyle 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 $\displaystyle \text{C}_1$ and $\displaystyle \text{C}_2$ be circles with $\displaystyle \text{C}_1$ inside $\displaystyle \text{C}_2$ and tangent at a point on $\displaystyle \text{C}_2$. Let $\displaystyle c_1,c_2,...,c_k$ ($\displaystyle k\geq 3$) be circles in between $\displaystyle \text{C}_1$ and $\displaystyle \text{C}_2$ and tangent to $\displaystyle \text{C}_1$ and $\displaystyle \text{C}_2$ and to eachother adjacent circle. Let $\displaystyle a_1,a_2,...,a_{k-1}$ be the points of tangency of these circles with their neighbors. Prove that $\displaystyle a_1,a_2,...,a_{k-1}$ all lie on a common circle.
(Note: The solution I know does not use elementary geometry).
• Mar 1st 2008, 07:50 PM
TwistedOne151
3. This proof isn't entirely rigorous, but contains all the major steps:

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

--Kevin C.
• Mar 1st 2008, 08:06 PM
ThePerfectHacker
Excellent job. I would just be more specific, if $\displaystyle a$ is the tangency point, define $\displaystyle 1/(z-a)$ be the the Moebius transformation, the rest follows as you said.
• Mar 1st 2008, 09:06 PM
heathrowjohnny
2. There are $\displaystyle n!$ total permutations of the $\displaystyle n$ wallets. Now number the wallets from $\displaystyle 1$ to $\displaystyle n$. The first person has a $\displaystyle \frac{n-1}{n}$ probability of picking a wrong wallet. You would have to use a computer for this "brute force" approach.

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

We know that $\displaystyle P(n,0) = \frac{1}{n!}$ (i.e. probability all people get their wallets). Also by axiom 3 (commonly in textbooks) $\displaystyle \sum_{k=0}^{n} P(n,k) = 1$. So $\displaystyle P(n,k)$ is the probability that there are $\displaystyle k$ incorrect wallets chosen and $\displaystyle n-k$ correct wallets chosen. These are independent events, so we can multiply probabilities. We get $\displaystyle P(n,k) = \frac{1}{(n-k)!}P(k,k)$. But this doesn't really give us $\displaystyle P(n,n)$. So $\displaystyle \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): $\displaystyle P(k) = \sum_{i =0}^{k} \frac{(-1)^{i}}{i!}$.

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

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

Then the probability that not all the people take their wrong wallets is $\displaystyle 1 - \frac{1}{e}$ (some people could take wrong wallets, while other people take correct wallets).
• Apr 11th 2008, 09:45 AM
ThePerfectHacker
Quote:

1a)Let $\displaystyle n$ be an odd positive integer. Let $\displaystyle \zeta = e^{2\pi i/n}$ prove that $\displaystyle x^n - y^n = \prod_{k=0}^{(n-1)} (x\zeta^k - y\zeta^{-k})$.
Note that $\displaystyle z^n - 1 = \prod_{k=0}^{n-1} (z - \zeta^k)$. Let $\displaystyle z=x/y$ and we get $\displaystyle x^n - y^n = \prod_{k=0}^{n-1} (x-y\zeta^k)$. Since $\displaystyle 0,1,...,n-1$ and $\displaystyle 0,-2,-4,...,-2(n-1)$ are both a complete system of residues, since $\displaystyle n$ is odd it means, $\displaystyle \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 $\displaystyle \zeta^{-0-1-...-(n-1)} = 1$ the proof is complete.

Quote:

1b)Let $\displaystyle f(z) = 2i\sin (2\pi z)$ and $\displaystyle n$ an odd positive integer. Prove that $\displaystyle 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 $\displaystyle f(-z) = -f(z)$ and $\displaystyle f(z+1)=f(z)$. Also, $\displaystyle f(z) = e^{2\pi i z} - e^{-2\pi i z}$.
In the identity, $\displaystyle x^n -y^n = \prod_{k=0}^n (x\zeta^k - y\zeta^{-k})$ let $\displaystyle x=e^{2\pi i z}$ and $\displaystyle y=e^{-2\pi i z}$. Thus, we get, $\displaystyle 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, $\displaystyle 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, $\displaystyle f(nz) = \prod_{k=0}^{n-1}f\left( z + \frac{k}{n} \right)$. Split the product to get, $\displaystyle 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 $\displaystyle f(z) = f(z-1)$ (a property mentioned above) thus $\displaystyle f\left( z + \frac{k}{n} \right) = f\left( z + \frac{k}{n} - 1\right) = f\left( z - \frac{n-k}{n} \right)$. Thus, $\displaystyle 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 $\displaystyle \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 $\displaystyle 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.
• Jan 30th 2009, 08:13 AM
chiph588@
Wow, I found these same identities with these exact proofs... I wonder if we have the same number theory book?
• Jan 30th 2009, 09:17 AM
ThePerfectHacker
Quote:

Originally Posted by chiph588@
Wow, I found these same identities with these exact proofs... I wonder if we have the same number theory book?

I seen these identities in my number theory book by Ireland and Rosen.
I thought they were nice and posted them here.
• Jan 30th 2009, 01:59 PM
chiph588@
Yep, that's one of my books this semester.
• Jan 31st 2009, 01:40 PM
ThePerfectHacker
Quote:

Originally Posted by chiph588@
Yep, that's one of my books this semester.

That is a very awesome book (Smile).