1. 100 cars are spread out on a single lane road. All cars have independently assigned positive random speeds from some continuous distribution. Cars drive at their initial speed until they run into a car in front of them at which point they will adjust their speed down to the car in front and follow that one. After a while this will result in several "clumps" of cars with each clump moving slower than the one before it. What is the expected number of clumps?
2. Let n be an odd number. Consider the complete graph on n vertices. Using n colors we want to color the vertices
and
edges of this graph such that (i) every vertex has a different color, (ii) any two edges that meet at a vertex have different colors, and (iii) every vertex is colored differently from all its edges. Can this be done? What if n is even?
3. Let n be any positive number. Find the product over all n-th roots of unity of (1 + root). Find the product over all n-th roots of unity that are not 1 of (1 - root).
#1: regardless of the distribution, every pair of consecutive cars has equal likelihood of the front or rear car going faster. So initially, there will be 100 individual cars, and each of the 99 pairs of consecutive cars has probability .5 of eventually meeting and merging into one, so the expected number of clumps is 100 - .5 * 99 = 50.5.
Spoiler: 2
#2: every vertex necessarily has one incident edge of each color.
So looking at this from a first instinct kind of deal, if n=3 then it's obviously doable and if n=2 then it's obviously not, so odds are it works with odd n and not with even n :p
There are n(n-1)/2 edges and n colors, meaning there must be on average (n-1)/2 edges of each color; if n is even, then by the pigeonhole principle there must be some color that colors n/2 edges. But none of these can be incident on the same vertex by (ii), so they must together be incident on every vertex, which violates (iii). So it's impossible in the even case.
In the odd case, there will be exactly (n-1)/2 edges of each color. One way to construct this is to place the vertices in the shape of a regular n-gon in the cartesian plane.
Then, to place the edges of color c, rotate the n-gon so that there is an edge at the bottom parallel to the x-axis and the vertex at the top is the color c. Then for every pair of vertices that are horizontally aligned, join them with an edge of color c. Doing this for every vertex should result in a completely connected n-gon which corresponds to the desired graph.
I'll look at the actual proofs in the morning. I think your answer for 2 works out (although it's very different from how I did it). Answer for 1 is incorrect though.
New logic: since it's a continuous distribution the speeds are all distinct with probability 1. Wherever the slowest car is, it will lead a clump of it and everything behind it. If EV(n) is the expected number of clumps if there were n cars, then EV(n) = ((1 + EV(n-1)) + (1 + EV(n-2)) + ... + (1 + EV(n-n))) / n, which can be seen by considering each possible position of the slowest car. The base case is EV(0) = 0. All of the ones can be factored out to get that EV(n) is 1 plus the average of EV(k) over all integers k with 0 ≤ k < n.
So at this point, this is obviously the harmonic numbers and i definitely didn't look at a spoiler that said that was what it was so we're going to blindly proceed with an induction attempt that might or might not work yep. This is probably some well-known property of the harmonic numbers that I just haven't seen before.
The actual formal logic of the induction is sort of trivial. The interesting part is just showing that the average of the first n harmonic numbers plus one is the next harmonic number. Laying things out visually (the logic works the same in the general case but this is how it would work for one small case of n=5):
0
1
1 + 1/2
1 + 1/2 + 1/3
1 + 1/2 + 1/3 + 1/4
When we take the average of these and add one, we need to end up with 1 + 1/2 + 1/3 + 1/4 + 1/5. The 1 will come from the 1 that we're adding, so we need the average of these five numbers to be 1/2 + 1/3 + 1/4 + 1/5. We group the numbers as follows: put one of the 1s on its own. Put one of the 1s with all of the 1/2s. Put one of the 1s with all of the 1/3s. And so on.
When we do this, we note that there are exactly n-k copies of 1/k for each k, for a total value of (n-k)/k = (n/k) - 1, so when we add a 1 to the sum of all of those we get (n/k). So by grouping the numbers this way, we get a bunch of sums that each sum to n/k, and when we take the average we add them all up and divide by n, which gives us exactly the sum that we need.
Forgive me for going from a specific example to general logic but i'm too lazy to actually go back formalize the argument completely. Pretty neat though.
(also it's 1:30 am and i've been nerd sniped so i take full liberty of having this proof be mostly train-of-thought)
That works. Even easier is to realize that unless the very last car is the slowest car then EV(n) = EV(n-1) because it will just join the earlier clump. If the last car is the slowest then EV(n) = EV(n-1) + 1. Since the probability of the last car being the slowest is 1/n we get EV(n) = EV(n-1) + 1/n. Then induct from EV(1) =1
First, it's true in R. This is because any polynomial in R is eventually mostly just its highest power, and is eventually either increasing, or decreasing fast enough to go below zero. Since the latter is impossible, we need only look at the former, thus we only need to look at it over some closed bounded interval, and it must obtain its minimum over that interval.
We can parametrize the two dimensional polynomial into a one-dimensional polynomial in terms of t by taking a line going out from the origin. Thus by the fact that its true in R, all of these lines obtain their minima.
Call the polynomial p. f maps theta to min_{t\in\R}(p(t\cos\theta, t\sin\theta) is continuous. This is because at the t-value for any given min, nearby you'll have a point nearby, making f(nearby thetas) less than or equal to nearby f(theta). Since this applies in both directions, this means that f(nearby thetas) are nearby f(theta). Thus, f has a minimum on [0,2\pi]. This minimum is the minimum of the entire function.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
In post 3974, Mitillos wrote:It had bloody better be, I'm teaching undergrad linear algebra this semester. (Yes, it's cheating a bit, I know.)
I should consider putting that question in an exam.
In post 3983, Who wrote:Call the polynomial p. f maps theta to min_{t\in\R}(p(t\cos\theta, t\sin\theta) is continuous
An example for a general polynomial is xy. Along the line x = 0 this has a minimum of 0 but along any line close to it it doesn't have a minimum. There's a counter example thats a positive polynomial as well but it also spoils the whole problem...
Maybe I'm misreading your claim. But consider the polynomial (1-xy)^2 + x^2. This is positive because both of the squared terms can't be 0 simultaneously. But can be made arbitrarily small along the curve xy = 1. Along the line x = 0 this polynomial has a minimum of 1 but the map from [0,2\pi] \to R you're describing is discontinuous at this point because at angles arbitrarily close to 0 the minimum is arbitrarily small.
I was misreading your counterexample. By "along any line close to it it has no minimum" I thought you meant "for any given line close to it, on that line it has no minimum"
Who said that?
Chamber. It's all a conspiracy.
Or is it?
@Sob: (Cool choice of name, by the way.) For the first question in 3, your wording is any positive number n. I'm not sure about that, but I think that for positive integers n, the product is 1 + (-1)^(n-1), so it's 0 for even n, and 2 for odd n. The derivation can be done separately for odd and even n. I haven't looked at the second part, yet.
To Question 3, for the first part the answer is 2 for odd n and 0 for even n. For the second part it's n. I have a proof for both parts but it is rather lengthy and I will post it later.
"one of these days i'll read you correctly" - Transcend, Micro 714
Let P(k) be the sum of the products of all combinations of k nth roots of unity. P(0) = 1.
Lemma: P(k) = 0 for 1 <= k <= n-1.
I will give the proof later.
Anyway, for the first part expanding the product (1+root) over all roots gives P(0) + P(1) + ... + P(n). P(0) = 1 and all other P(k) are 0 except P(n).
P(n) is the product of all nth roots of unity. Let z be any primitive nth root of unity. The nth roots are z, z2, z3... zn. Their product is zn(n+1)/2. For odd n we have n(n+1)/2 is a multiple of n so this is a power of zn=1 and for even n we have n(n+1)/2 is a multiple of n/2 but not n so this is an odd power of zn/2=-1.
Thus, as the product is 1+P(n), it is 2 for odd n and 0 for even n.
For part 2, let Q(k) be the sum of the products of all combinations of k nth roots of unity that do not include 1. Q(0) = 1.
Now, consider all combinations of k nth roots of unity. Those that do not contain 1 are included in the sum Q(k). For those that do, the 1 can be removed, leaving k-1 terms that do not include 1, and the sum of their products is Q(k-1). Thus, for k >= 1, Q(k) = P(k) - Q(k-1).
Since, for 1 <= k <= n-1, P(k) = 0, Q(k) = -Q(k-1). Thus, as Q(0) = 1, Q(k) = (-1)k.
Now consider Q(n) = P(n) - Q(n-1). If n is odd then this is 1-1 = 0 and if n is even this is -1-(-1) = 0. Thus Q(n) = 0.
The product is the product of (1-root) for all roots other than 1. This is Q(0) - Q(1) + Q(2) ... + (-1)nQ(n). Since Q(k) = (-1)k for all k <= n-1, this is 1+1+1...+1 with n 1s and is thus n.
Now try some of these problems.
1. Cover the real line with a set of disjoint open intervals such that their total length is finite and every rational number is in an interval.
2. Suppose that each rational was coloured either red or blue such that the set of red rationals and the set of blue rationals are both dense.
Find a one-to-one mapping from the set of all rationals to the set of all rationals excluding 0 which preserves the order of the rationals such that any red rational is mapped to a red rational and any blue rational is mapped to a blue rational.
3. Find a function f(x) from the reals to the reals such that the image of any interval is the entire real numbers.
"one of these days i'll read you correctly" - Transcend, Micro 714
Enumerate the rationals q_1, q_2, ... Now take the union over all n of the open intervals (q_n - 0.5^n, q_n + 0.5^n). By countable subadditivity of measure this set has total measure less than 2, and also contains all rational numbers.
Spoiler: 2
Kind of sloppy construction but here's what I have. Enumerate the rationals again but in such a way that q_1 = 0 and q_1 and q_2 have the same color. Now we'll construct our function f inductively. Start with f(q_1) = q_2. Now when we have f(q_1),...,f(q_(n-1)) defined we define f(q_n) as follows. Find the smallest q_i with i < n such that q_n < q_i and find the largest q_j with j < n such that q_j < q_n (if q_n is on one of the outer edges let q_i = infinity or q_j = negative infinity). Now let Q_n be the set of all rationals q such that f(q_j) < q < f(q_i) excluding 0. Define f(q_n) to be the earliest (in terms of the enumeration) rational with the same color as q_n in Q_n. This is well-defined because the colors are dense. It preserves order, color, and is a bijection from Q to Q minus {0} by construction.
Spoiler: 3
The Conway 13 function has this property.
Some gambling problems:
1. You and a friend play a game where every day you flip a coin. If the coin lands heads you give your friend a dollar, if it lands tails your friend gives you a dollar.
a) If you and your friend play this game for the entirety of 2017 what is the probability you will end with a net gain/loss of exactly 0?
b) If you and your friend play this game for the entirety of 2020 what is the probability you will end with a net gain/loss of exactly 0? Give your answer to within a 1% chance without using a calculator.
c) If you and your friend play this game for the entirety of 2020 what is the probability you will end with a net gain/loss of exactly 0 and at no point during the year have you given your friend more money than you've received. Give an exact closed form solution.
Spoiler: Hint for part c
Use generating functions
2. It's the World Series! The Cubs are playing the Yankees and you want to place a $1000 bet on the Cubs winning the series with 1:1 odds. The problem: there is no market for this kind of bet in the entire world. But, there are markets for bets on each individual game with 1:1 odds on each game. Can you construct a strategy for betting on each game with your $1000 (where you bet on each game after seeing the result of the last one) that gives you the result you want ($2000 if the Cubs win, $0 if they lose the series)?
1a. Trivially the probability is 0. (There are 365 days to the final number of dollars is odd).
1b. You need 183 heads and 183 tails. Thus it should be 366C183/2^366. If you use Stirling's formula for factorials and simplify, you get 1/(sqrt pi n) or 1/(sqrt 183pi).
1c. The number of ways to get a net gain/loss of exactly 0 is 366C183. The number of ways to get a net gain/loss of exactly 0 and at some point give more money is 366C182, which is also (183/184)366C183. Thus the probability you do not give more money than you receive given that you make a net gain/loss of 0 is 1/184. Thus the exact closed form solution is 366C183/(184*2^366).
It looks like for 2 you could just recursively work backwards from 6-6, where you have $1000 and bet $1000, to work out how much you have and bet at each stage.
"one of these days i'll read you correctly" - Transcend, Micro 714
So, three men rent a hotel room for a night. They each pay $10 for a total of $30. But the hotel's owner is generous and gave a $5 discount, making the total cost only $25.
So, the owner ordered a service boy to return the $5 leftover to the three men. The service boy, unfortunately, kept $2 to his own and return only $1 to each of the three men.
Wait, that means each of the three men paid $9, for a total of $27, plus $2 that the boy kept and that's $29.
3. Suppose that there are 5 guards in front of you. 3 are guaranteed to answer truthfully to any yes/no question. 2 will say yes or no arbitrarily to any question. Each guard knows who the others are. If you ask a guard a question they are unable to answer, they kill you, which you want to avoid. To pass, you need to ask the minimum number of yes/no questions that allow you to identify the three truth tellers for certain.
a. Prove that you need at least 5 yes/no questions in the worst case scenario.
b. Find a method that is guaranteed to identify the three truth tellers with at most 5 yes/no questions.
c. Now suppose there were 2 truth tellers and 2 arbitrary guards. Prove that no matter how many yes/no questions you ask, you are never guaranteed to identify the truth tellers.
4a. Suppose you have a line segment and you pick two points independently at random. You break the line segment at these points. What is the probability that the three new segments can be rearranged to form a triangle?
4b. Now suppose you picked three points independently at random from another line segment. You break the line segment at these points. What is the probability that the four new segments can be rearranged to form a quadrilateral?
"one of these days i'll read you correctly" - Transcend, Micro 714
Ask the following questions to the following guards in order. If they say "Yes", go with the yes:. If they say no, go to the next guard.
1 2 3 4 5 ("lies" means arbitrary, not lies)
1: Is 5 truth?
Yes: Ask 5 about everyone else.
2: Is 1 truth?
Yes: 1 is truth, 5 is lies. Ask 1 if 2 is truth, then 3. 4 must be whatever remains.
3: Is 2 truth?
Yes: 2 is truth, 1 is lies. Ask 2 if 3 is truth, then 4. 5 must be whatever remains.
4: Is 3 truth?
Yes: 3 is truth, 2 is lies. If 1 is truth then 5 must be lies, meaning 1/3/4. If 1 is not truth then 3/4/5.
5: Is 4 truth?
Yes: 4 is truth, 3 is lies, if 1 is truth then 5 must be lies, and so is 2, illegal. Thus it's 4/2/5.
No: If all of them said the previous one was lies, there can't be two truths in a row. Thus it's 1/3/5.
3c:
Spoiler:
The arbitrary guards could answer every question as if they were the truth tellers and the real truth tellers were arbitrary. It would be impossible to distinguish between the two groups.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
Well done for 3c, but there are a few errors in 3b.
First, if 1 says 5 is truthful, 5 can pretend that the liars are, for instance, 2 and 3 when the real liars are 1 and 5.
Second, if 1 says 5 is a liar and 2 says 1 is truthful, the real liars could be 1 and 2, and your method does not allow you to work out when this is the case.
Third, you need to distinguish between 1/3/4 and 3/4/5 with one question, although this is a trivial point.
Finally, although this is again a minor point, the last question does not need to be asked as you know that 5 will say Yes and it is 2/4/5. This is because 1 already said that 5 was a liar, which is impossible in 1/3/5.
Try to rethink the follow-up questions if 1 or 2 says Yes. Otherwise the rest of this works.
See if you can prove that 5 is the minimum.
"one of these days i'll read you correctly" - Transcend, Micro 714
(Yes, it's cheating a bit, I know.)![:]](./images/smilies/icon_smiling.png "Cheerful Smile"){kind=icon}
