Mein gott what have you done to my coat
by cjquines0, Nov 3, 2016, 1:19 PM
A warm-up problem first:
Solution
Now for the meat:
Solution
Tidbit
Tidbit 2
Engel, PSS wrote:
There are several circles of total circumference
inside a square of side length
. Prove that there is a line that intersects at least
of the circles.



Solution
Let the circles have diameters
. Then we have
. Consider a random horizontal line. The probability it passes through the circle with diameter
is simply
. Thus the expected number of circles it passes through, by linearity of expectation, is
; as this only takes on integral values there exists a line which passes through at least 4 circles.





Now for the meat:
Engel, PSS wrote:
A tramp has a coat of area
with
patches. Each patch has area at least
. Prove that two patches exist with common area at least
.




Solution
If all ten pairs of patches have a common area less than
, the total area would be less
and thus there must be some point on the coat that lies on only one patch. Pick a random point, suppose it lies on
patches. We use the fact that if
. Then take the expected value,
, contradiction.




![$\mathbb{E}\left[\binom{i}{2}\right] \geq 2\mathbb{E}[i] - 3 \geq 2$](http://latex.artofproblemsolving.com/5/e/7/5e754b52ad5c322952558ed67e033864ea32142a.png)
Tidbit
Yes this is extremely easy, but I’ve been in a probabilistic mood lately. This reminds me of
Solution
whoops wrote:
Let
be a random permutation of the numbers
. Let
be the number of fixed points. Find
.
This is the variance of
. If
is the mean value of
, then the variance is the mean value of
.




This is the variance of




Solution
We want to find
. Let
be the indicator variable for
being a fixed point in
, then clearly
. Linearity,
, probably the most classic of all the expected value results. Also note
and for
,
, we’ll use this later.
Then we want to find
, linearity, this is
. We just need to find
. Use the multinomial theorem then linearity:
The answer we want is thus
.
![$\mathbb{E}[(X - \mathbb{E}[X])^2]$](http://latex.artofproblemsolving.com/e/a/0/ea0dc397dbe463e231cca5541f38f4b4930e66fe.png)



![$\mathbb{E}[x_i] = \frac{1}{n}$](http://latex.artofproblemsolving.com/3/6/a/36a44dee4cb0508e338f642e5a2f799ccad872cc.png)
![$\mathbb{E}[X] = 1$](http://latex.artofproblemsolving.com/5/6/7/567d191a7794462967ccaf6e7f61b5597efcce95.png)
![$\mathbb{E}[x_i^2] = \frac{1}{n}$](http://latex.artofproblemsolving.com/d/c/f/dcf95463323e65afad7562a43d29277aae9a72ca.png)

![$\mathbb{E}[x_ix_j] = \frac{1}{n(n-1)}$](http://latex.artofproblemsolving.com/6/0/4/604e9f9ec5022da930f1c958a4e57b773441df1e.png)
Then we want to find
![$\mathbb{E}[(X - 1)^2]$](http://latex.artofproblemsolving.com/3/a/a/3aafc0407d25ac84ac926103c4e9ff97c012ff3e.png)
![$\mathbb{E}[X^2] - 2\mathbb{E}[X] + 1$](http://latex.artofproblemsolving.com/9/a/7/9a7d116f61caecd7a287fcaa3be0bfdd264bb788.png)
![$\mathbb{E}[X^2]$](http://latex.artofproblemsolving.com/a/7/2/a7287adc779aec7bd291ac31f33ae82d1a8f904e.png)
![\begin{align*}\mathbb{E}[X^2] &= \mathbb{E}\left[\left(\sum x_i\right)^2\right] \\ &= \mathbb{E}\left[\sum x_i^2 + 2\sum_{i\neq j} x_ix_j\right] \\ &= \sum \mathbb{E}[x_i^2] + 2\sum_{i \neq j} \mathbb{E}[x_ix_j] \\ &= (n)\left(\frac{1}{n}\right) + 2\binom{n}{2}\left(\frac{1}{n(n-1)}\right) \\ &= 2.\end{align*}](http://latex.artofproblemsolving.com/1/9/2/1928f0344dbc9bac52916dbccd9040ad09f45c72.png)

Tidbit 2
Okay, sorry. Yes, it’s not hard. Sorry.