Math and Logic Puzzles

[Sobolev Space]

Some questions for y'all:

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).

[Sobolev Space]

This one is also good but very hard:

4. Does every positive real polynomial in 2 variables attain its minimum somewhere in R^2?

[Sobolev Space]

Positive means f(x,y) > 0 for all x and y. Just x^3 doesn't meet that.

[Sobolev Space]

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.

Spoiler: The value you should get is

the 100th harmonic number

[Sobolev Space]

Spoiler: #1

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

[Sobolev Space]

@Who

Spoiler: #4

Incorrect.This claim is false.

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...

[Sobolev Space]

Spoiler:

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.

[Sobolev Space]

Spoiler: 1

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)?