Mathematical Food for Thought

Problem: A coin is repeatedly flipped. What is the expected number of flips to get two heads in a row? heads in a row?

——————–

I will be out of town for the next four days, so have fun with the problem!

Problem: (2007 AIMEI – #6) A frog is placed at the origin on the number line, and moves according to the following rule: in a given move, the frog advances to either the closest point with a greater integer coordinate that is a multiple of , or to the closest point with a greater integer coordinate that is a multiple of . A move sequence is a sequence of coordinates which correspond to valid moves, beginning with , and ending with . For example, is a move sequence. How many move sequences are possible for the frog?

Solution: Let be the number of possible move sequences starting from and ending up at . Clearly it is only interesting when is divisible by or . So let’s try to construct the sequence.

is our base case. There is only one way to get to the value from , so . Similarly, , , and . But how many ways can we get to ? Well, if we start at any of the previously mentioned numbers there we can go straight to from them (by using the next multiple of move). So

.

Now how about ? Well we can get there from either or , so

.

Continuing, we have because we can only get to these from the previous multiples of . Then

.

In this similar fashion, we obtain and finally . QED.

——————–

Comment: This is a cool problem, though they could have made it harder to brute force (i.e. have the answer be ) to really weed out the people who did not actually know how to intelligently count it. It is based on a nice recursive concept known as “dynamic programming,” which is one of the coolest computer science techniques ever. The idea is to use solutions of subproblems to construct the solution to a larger problem, like in this case using smaller values of to calculate .

——————–

Practice Problem: (2007 AIMEI – #1) How many positive perfect squares less than are multiples of ?

Problem: Let be the probability of choosing a positive integer from the interval such that the binary representation of does not contain three consecutive ’s. Evaluate the infinite summation .

Solution: First, let be the number of positive integers in the interval that do not contain three consecutive ’s in their binary representations – note that it is equivalent to the number of binary strings of length starting with a that satisfy that property. By testing, we have , , , , , . You can construct a certain type of table to make these calculations easier. We notice that the recurrence seems to hold, so we want to try and prove this.

We categorize the strings of length based on the last occurence of . It must either be in the last, second to last, or third to last spots. If it is in the last spot, the string is where has length so there are of those. Similarly, the other possibilities are or , where the ’s have length and , respectively, giving the recurrence. Now it remains to sum it.

We want to evaluate since there are binary strings of length that begin with .

Luckily, we know a cool way to evaluate recurrences over a geometric sequence. Let . Then

.

Notice, now that if we take a lot of terms cancel due to the recurrence. In fact, all of the summations do! So

.

QED.

——————–

Comment: Both parts of this problem are pretty classical. The first, finding a recurrence for a string satisfying a certain property, and the second, evaluating an infinite summation of the terms of a sequence divided by a geometric series. These two techniques are very useful, however, in approaching many problems. It would not be fun to solve a problem and get to the last step only to find that you do not know how to evaluate the summation to get the final answer.

——————–

Practice Problem: Evaluate , where is a positive integer and is the Fibonacci sequence (i.e. and for all positive integers ).

Problem: (1983 Canada – #5) Show that the geometric mean of a set of positive numbers equals the geometric mean of the geometric means of all non-empty subsets of . [Reworded]

Solution: Let , so the geometric mean is . We will show that the geometric mean of the geometric means of all non-empty subsets of is equivalent to this. It suffices to show it is true for an arbitrary . Consider dividing the subsets of that contain into groups based on the number of elements it contains. We will count how many of them there are:

-element subsets containing – clearly just the set . There is only ;

-element subsets containing – the set for any . There are of these;

-element subsets containing – there are of these.

It’s pretty clear that if we want a -element subset containing we are free to choose the other elements from the remaining elements of . If we take the geometric mean of these subsets, however, we find that

-element subsets give a full power of ;

-element subsets give a power of ;

-element subsets give a power of ;

and so on. So when we multiply these all together, we get an exponent of

.

It remains to evaluate this sum, but we can do that through generating functions. Since , we integrate both sides to get

.

Using , we obtain , so .

Finally, by the substitution , we get the desired summation:

.

So prior to the last geometric mean, we have , but we know that there are non-empty subsets of , which means the last geometric mean is a power of , and we have

,

the same power as the original geometric mean we computed. QED.

——————–

Comment: A very nice problem because it branched together several aspects of mathematics all into a single problem, which is always cool. There is probably a non-calculus method of evaluating that sum, but basically any time you see a sum like that you can use generating functions and then apply derivatives/integrals to make it what you want. Apparantly a symmetry argument can also be made, but that’s probably just the lazy way to do this problem…

——————–

Practice Problem: (1983 Canada – #4) Given an arbitrary prime , show that we can find infinitely many positive integers such that is a multiple of .

Problem: (2002 Putnam – B4) An integer , unknown to you, has been randomly chosen in the interval with uniform probability. Your objective is to select in an odd number of guesses. After each incorrect guess, you are informed whether is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than .

Solution: We first prove that, in the interval , we can guess with a strategy that allows us to get the desired number in an even number of guesses with probability. This is easy by induction.

Base case: . Pick . If , it’s an odd number, but if , we can get it in the subsequent guess. So there is a chance.

Induction step: Suppose it’s true for the interval . We want to show it is true for the interval . Start by choosing . If , it’s an odd number of guesses, but if , it’s even. Then guess (if we find that ) on the second guess. So if , we can get it in an even number of guess. If we find that , it's just choosing from the interval in an even number of guesses, so by the inductive hypothesis this is . Hence the probabability in the interval is

completing the induction.

So now we have the interval . Choose . If , we're done in an odd number of guesses. Otherwise, we want to guess which is in in an even number of guesses. By the lemma above, the probability of this is .

Therefore, the total probability is , as desired. QED.

——————–

Comment: This was a pretty neat problem. The way I figured out the solution was by an interesting recursion that find the best strategy for based on optimizing the best strategies for with in trying to get an even and odd number of guesses. The pattern revealed the first lemma, which lead directly to the solution. It seems like some of the later problems on the test were a little easier than the earlier problems.

——————–

Practice Problem: (2002 Putnam – A3) Let be an integer and be the number of non-empty subsets of with the property that the average of the elements of is an integer. Prove that is always even.