Problem of the day:

1. March 05: This is a problem used in today's programming contest. See if you can solve it (no proofs are needed in the contest, but we need to prove our answer). [source]

   Problem: Snoopy has three coins. One day he tossed them on a table then and tried to flip some of them so that they had either all heads or all tails facing up. After several attempts, he found that regardless of the initial configuration of the coins, he could always achieve the goal by doing exactly two flips, under the condition that only one coin could be flipped each time and a coin could be flipped more than once. He also noticed that he could never succeed with less than two flips.

   Snoopy then wondered, if he had n coins, was there a minimum number x such that he could do exactly x flips to satisfy his requirements?
   Find the number x when it exists and prove that your answer is correct.

   Hint: For some n there are no solutions.

   Solution:

   There can be no solution in the case when the number of coins is even. If the number of coins is odd, either the number of heads or the number of tails must be even. If the even number is zero, keep flipping the same coin n-1 times. Otherwise the strategy is to identify coins with an even number of same faces (say those showing heads) and keep flipping them until they all turn tails and we have used n-1 flips. Of course there are at most n-1 heads so this is sufficient. If the even number is less than n-1 we keep flipping a tail until we have used all n-1 flips.

   Proof of correctness: The proof uses a parity argument. First note that we need an odd number of flips to change parity of the number of heads or tails. That is if we flip heads to tails an odd number of times the parity of the number of heads changes. On the other hand an even number of slips preserves parity.

   Therefore if there are an even number of coins, the number of heads and tails have the same parity. If this parity is even, we need an even number of flips to change them to all heads or all tails and if the parity is odd, we need an odd number of flips to change them to all heads or all tails. Therefore there can be no solution in the case when the number of coins is even.

   If the number of coins is odd, then the the number of heads and tails have opposite parity. Thus a solution is possible.

   If one thinks about the problem one realizes that using an even number of flips always works (odd number of flips fail when all coins already show heads or all show tails). In fact the number must be n-1 to handle the case 1 is heads and n-1 tails or vice versa. In general this works because one applies n-1 flips to coins showing heads (respectively tails) initially if there are an even number of heads (respectively tails) initially. Even if there are less than n-1 heads the number is even and even number of flips can preserve parity.

2. March 11:
   I was not well, hence no problems until today.

   Problem: Prove that the set of all binary strings is countable. (This was sketched in class, but try to complete the proof).

   Solution:

   We know that all we have to do is define a bijection from the set of binary strings to the natural numbers. We define the mapping from a binary string to a natural number as follows. Take the binary string, add a leading 1 and interpret the new string as the binary representation of a natural number. The inverse mapping is as follows. Given a natural number, convert it to binary and remove the most significant digit (always a 1). Output the remaining string. You can check that this is a bijection between the set of binary strings and the set of natural numbers. Hence the former set is countable.

3. March 12:
   

   Problem: Consider the following alternate definition of an infinite set: "A set S is infinite if there exists a function f:S -> S that is one-to-one but not onto".
   Are the set of natural numbers and the set of real numbers infinite by this definition? Why?

   Solution:

   Consider the function f(n) = 2n on the natural numbers. It is one-to-one but not onto (no odd numbers are output by the function.

   However this does not work on the reals. Why?

   However we can use the function 2^x on the reals as an example of a function that is one-one but not onto (never produces negative numbers.

4. March 13:
   

   Problem: We proved in class that the real interval [0,1) is not countable. Argue that the interval [0,0.2) is uncountable.

   Solution:

   Consider the function f(x) = 5x from [0,0.2) to [0,1). It is one-to-one and onto. Therefore the two sets have the same cardinality.
5. March 18:
   

   Problem: This is a challenge problem. Prove that for every natural number greater than 1, 2^(3n)-1 is not a prime. Solution:

   The statement to prove using induction is not the given one but one that is more powerful. Prove using induction that 2^(3n)-1 is divisible by 7 for all n. The given statement follows.