Math and Logic Puzzles

[BTD6_maker]

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.

[BTD6_maker]

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, z², z³... zⁿ. Their product is z^n(n+1)/2. For odd n we have n(n+1)/2 is a multiple of n so this is a power of zⁿ=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 z^n/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)ⁿQ(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.

[BTD6_maker]

Well done on solving my problems!

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.

[BTD6_maker]

Here are some interesting ones.

1. Let |x| stand for the floor of x. Let a and b be positive reals. Show that the following statements are equivalent:

|a|, |2a|, |3a|, |4a|... and |b|, |2b|, |3b|, |4b|... contain every positive integer greater than 1 exactly once between them.

a and b are irrational, and 1/a + 1/b = 1.

2. Let a and b be positive integers. (a²+b²+1)/ab = n, where n is a positive integer. Prove n = 3.

[BTD6_maker]

Here are some more.

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?

[BTD6_maker]

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.