Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 1. A big product

Prove that, for all integers n greater than 1,

# 2. A feudal tax system

Every day, a peasant earns 1 copper farthing. His landlord comes to him at the end of the day and taxes him for exactly 1/4 of his total wealth (including any money left over from previous days). Assuming that the two start with nothing and that neither person has any other source of income or expenditures, how much much does the landlord have after n days?

# 3. A counting game

Two small children are playing the game "I know a bigger number." The first player must name a natural number less than or equal to n, where n happens to be the largest number known to either child. Then the second player must name a larger number that is still less than or equal to n. The players continue to alternate with larger and larger numbers until one of them names n, at which point the game ends.

Given n, exactly how many different sequences of moves could the two children play?

# 4. Sets of functions

Given sets A and B, let AB be the set of all functions f:Bâ†’A.

1. Prove or disprove: |âˆ…B| = 0 for any set B.

2. Prove or disprove: |1B| = 1 for any set B, where 1 = {âˆ…}.

3. Prove or disprove: If A has at least two elements, then there exists an injection from B to AB.

2014-06-17 11:57