1. Let n and k be given non-negative integers. Consider all strictly increasing sequences of k integers in the range 1..n. For each sequence, multiply all its members together, and then add all these products. Call the result A(n,k). Now do the same for all weakly increasing sequences, and call the result B(n,k). Both A(n,k) and B(n,k) are Stirling numbers: the question is, which ones?
2. Let P and Q be the two tableaux of the same shape corresponding to the permutation g under the Robinson-Schensted-Knuth correspondence. Prove that the length of the first row of P and Q is equal to the longest increasing subsequence of g.
* Can you find an interpretation of the length of the first column of P and Q?
(I am grateful to Kurt Johansson for this exercise.)
3. If you have lunch in the sandwich bar described below five days a week, fifty weeks a year, how long could you go without repeating an order?
The miserable wasteland of multidimensional space was first brought home to me in one gruesome solo lunch hour in one of MIT's sandwich shops. "Wholewheat, rye, multigrain, sourdough or bagel? Toasted, one side or two? Both halves toasted, one side or two? Butter, polyunsaturated margarine, cream cheese or hoummus? Pastrami, salami, lox, honey cured ham or Canadian bacon? Aragula, iceberg, romaine, cress or alfalfa? Swiss, American, cheddar, mozzarella, or blue? Tomato, gherkin, cucumber, onion? Wholegrain, French, English or American mustard? Ketchup, piccalilli, tabasco, soy sauce? Here or to go?"From a review by Myles Aston of Life without Genes: the History and Future of Genomes by Adrian Woolfson, in the Balliol College Annual Record 2001.
4. A car park has n spaces, numbered from 1 to n, arranged in a row. n drivers each independently choose a favourite parking space in the park. As each driver enters the park, he drives to his favourite space. If it is empty, he parks there. Otherwise, he continues along the line and parks in the first free space. If all spaces between his favourite and n are taken, he leaves in disgust.
5. The following algorithm for constructing a magic square of order divisible by 4 was given by Ibn Qunfudh in the 14th century, in his book Lifting the Veil from the Operations of Calculation. The case n=4 is illustrated.
| Let n be a multiple of 4. Begin with an empty n x n grid. |
|
||||||||||||||||
Step 1. Mark some of the squares, so that the following condition
are satisfied:
|
|
||||||||||||||||
| Step 2. Count the squares, starting at the top right, and proceeding from right to left along each row, and down the rows from top to bottom. Insert the corresponding number in each marked square. (Unmarked squares are counted but numbers are not entered.) |
|
||||||||||||||||
| Step 3. Count the squares, starting at the bottom left, and proceeding from left to right along each row, and up the rows from bottom to top. Insert the corresponding number in each unmarked square. |
|
Prove that the resulting square is magic, that is, that all rows, columns, and diagonals have the same sum.
6. The following problem arises in the theory of clinical trials.
A new drug is to be tested out. Of 2n subjects in the trial, n will receive the new drug and n will get a placebo. To avoid bias, it is important that the doctor administering the treatments does not know, and cannot reliably guess, which treatment each patient receives. The patients enter the trial one at a time, and are numbered from 1 to 2n.
If the treatments were allocated randomly with probability 1/2, the doctor's guesses could be no better than random (so that the expected values for the numbers of correct and incorrect guesses are both n); but then the numbers of patients receiving drug and placebo would be unlikely to be equal. Given that they must balance, the doctor can certainly guess at least the last patient's treatment correctly.
If we allocated the drug and the placebo randomly to patients 2i-1 and 2i for i=1,...,n, then the doctor can correctly guess the treatment for each even-numbered patient.
Suppose that instead we choose a random set of n patients to allocate the drug to, and the remaining n get the placebo; each of the 2nCn sets is equally likely. Suppose also that the doctor guesses according to the following rule. If the number of patients so far having the drug and the placebo are equal, he guesses at random about the next treatment. If the drug has occurred more often than the placebo, he guesses that the next treatment is the placebo, and vice versa if the placebo has occurred more often than the drug.
Find a formula, and an asymptotic estimate, for the expected value of the difference between the number of correct guesses and the number of incorrect guesses that the doctor makes.
Peter J. Cameron
26 August 2003.