PA-4 / Lesson 4
Problem 1.
A usual deck of 52 cards is randomly split into two groups of equal size. What is the probability that both of them have the same number of red and black cards? What is the probability that the second group has more black cards than the first one?
Problem 2.
Two ice hockey teams plan to play until one of them wins three times (each game ends in one of the teams winning). The teams are of equal strength. What is the mathematical expectation of the total number games?
Problem 3.
There are $n$ people at a conference, all of them are of different age and they do not know each other in the beginning of the conference. By the end of the conference, each pair of them will become friends with probability $p$. Moreover, right before leaving the conference, each of them will give some unique and useful advice to all of his/her friends who are younger. Find the mathematical expectation of the number of people who will not receive any advice at the end of the conference.
Problem 4.
Two people, Leonard and Howard, play a game where each of them does the following: he tosses a fair coin until there are two different tosses (so e.g if Leonard starts with tossing heads, then he will be tossing until he gets tails. Similarly with Leonard). If both of them tossed the coin the same amount of time, they call it a draw. Find the probability that this game will end in a draw.
(Remark: One of the solutions requires you not to be afraid of an infinite probability space. However, there is another solution that does not require even this, but it might be a bit tougher to come up with.)
Problem 5.
There are 25 boys and 25 girls who sat at the round table randomly. What is the maths expectation of the number of blocks consisting of people of the same sex (male/female) sitting consecutively?
If you want to understand this remark, you must know what a graph is (and recall what is a cycle in it).
Let's examine the following problem: "Does there exist a graph such that
1) the length of the shortest simple cycle is at least 1000, and
2) the chromatic number of this graph is 1000?"
The chromatic number is the minimum number of colors needed to color the vertices of a graph so that no edge connects vertices of the same color.
Before we delve into the interesting part, let's quickly consider why this is not an easy problem. Without the first condition, it wouldn't be that difficult; indeed, just choose a graph with 1000 vertices where each pair of vertices is connected. However, with the first condition in place, such a simple example won't work. Moreover, note that the chromatic number for a single cycle, regardless of its size, is just 2 or 3, which is quite small. And if you try to draw a graph where the smallest simple cycle is 1000 (good luck "drawing" such a graph, by the way ;-)), you are likely to get a graph with a chromatic number of 5-10, far from 1000. So anyone who thinks the answer to the problem is "Yes" needs to come up with a rather clever construction... Or do they? Or perhaps the answer is simply "No"?
We won't bore you too much — the answer is actually "Yes", i.e such a graph does exist. However, no one knows how to construct it! Even computers are of no help... Soo how do we know such a graph exists? Well, it turns out that using some probabilistic methods, we can prove its existence. I.e "by discussing probabilities and uncertainties, we can prove that something completely non-obvious is certain". Isn't that fascinating?
By the way, you'll have the chance to apply this idea to fully solve a problem from the Extra Problem set! Try it.