Source: Donald Knuth, Stanford University
Scenario:
Here is a nice problem which teaches a valuable lesson about induction.
Consider the recursion
| K(0) | = | 1, | K(n+1) | = | 1 + min( 2 * K([n/2]), 3 * K([n/3]) ), n >= 0, |
Problem: Prove or disprove K(n) >= n.
Start-up:
n: 0 1 2 3 4 5 6 7 8 9 K(n): 1 3 3 4 7 7 7 9 9 10
Source: Mitchell Trott, M.I.T.
Scenario: Given an n by n matrix A, where entry
independently, for all i, j.
Problem: What is Pr[det A = 0]?
Source: Thomas Cover, Stanford University
Scenario: Secretly, two real numbers are placed into two identical evelopes and sealed. You are presented with the two envelopes, can choose one to open, and, based on the number you see, may trade evelopes or not. The incentive: if the ultimate envelope you choose contains the number x, you receive x dollars (a negative x means you owe that amount). Assume you want to maximize x.
Problem: Is there a strategy by which you can recieve the maximum more than 1/2 of time? If so, demonstrate one. If not, prove none exists.
Source: Paul G. Kwiat, Los Alamos Labs
Scenario: Secretly, that is without personal or mixed knowledge, to the foreheads of each of N people are attached a symbol (either a 0 or a 1) and a bandage covering it. The N people are then allowed to meet and discuss their respective "strategies" for the upcoming event: they are to go into a room, remove their bandages, and---without communicating to each other in any way---each secretly register a guess as to the "parity" of the entire group (i.e., a 0 if the total number of 1's is even, a 1 if it is odd). The "group answer" is computed by majority [strictly greater than one-half; half-half is undefined] vote of the registered guesses.
Problem: Is there a strategy by which the group can be correct more than 1/2 of time? If so, demonstrate one. If not, prove none exists.