MA375: Extra Credit Questions
Fall 2008, Prof. Walther
Extra Problem 1:
Suppose 2n people sit on a round table and are shaking hands in pairs. Suppose that etiquette is observed and no 2 shakes cross. Let S_n be the number of possible shaking hands arrangements of this sort.
Determine S_10.
Extra Problem 2:
10 disgruntled first rate mathematicians have decided to change career and became pirates of the Caribbean. They have taken a Spanish galleon with 100 pieces of gold and came up with the following scheme of distributing the money: the oldest makes a proposal on who gets how much, and the proposal is voted on. If the proposal gets half or more of the votes (everybody must vote), the propsal is adopted and the gang goes for the next ship. If the proposal does not get 50%, the proposer is thrown overboard for his mathematical deficiency, and the next oldest makes a proposal...
How will the money be distributed?
Extra Problem 3:
Let n be an integer. We consider the following collection M_n of matrices. A matrix M belongs to M_n if and only if a) it is a 2 by n matrix with entries 1,2,...,2*n (no repetition); b) from left to right in each row, and from top to bottom in each
column, numbers increase and never decrease.
An example of an element of M_3 is (1 2 5)
(3 4 6)
and an example of a 2x3 matrix that is not in M_3 is (1 4 5)
(2 3 6)
Question: find a recursion for the number of elements in M_n.
Extra Problem 4:
We know (soon) that the complete graph K_5 cannot be drawn in the plane without crossing edges. This is equivalent to the fact that K_5 cannot be drawn on a sphere without crossing.
Imagine now that we are trying to draw graphs on a "torus", which is the technical name for the surface of a doughnut. (Note that the "torus" is just the surface of the doughnut, it does not include the filling.)
Is it easier to draw graphs on the torus or on the sphere? In particular, what is the largest complete graph that can be drawn on a torus without crossing edges? (Hint: find a formula that looks much like Euler's formula but works on the torus.)
If you are truly adventurous, find out what the largest complete graph
is that can be drawn on a double torus without crossing. (That is, on
the surface of the solid that results from drilling 2 holes through a rock.)
Can you generalize to more holes?
Extra Problem 5.
Number 46 in 8.5.
Extra Problem 6.
n politicians have been accused of immoral behavior and filibustering (see http://www.m-w.com/dictionary/filibuster). After a short, secret, trial that did involve plenty of hearsay but no torture in or after the year 2005 the following verdict was given:
The next morning all n prisoners will be lined up, in random order, one after the other. They are not allowed to speak, or look in any direction but straight ahead. The executioner will then place one hat, either red or blue, one each prisoner (without that person knowing whether it's red or blue). Starting with the last prisoner in line, each of the prisoners (who sees all the hats of people in front of him, but not his own and not the hats of people behind him) then must say exactly one word, either "red" or "blue". When all prisoners have spoken, all those who correctly indicated the color of the hat on their own head will live. All else will perish.
If anyone does not follow the rules, he is executed and the process starts anew.
Question: assuming the politicians know what they are doing, what is a) the expected value of their survival rate, b) the number of people they can definitely save?
(Note: by making random announcements, a) is 50% but b) still 0%.)
Hints: 0. try to get b) to 50%.
1. try to get b)= 2/3 if n=3.
--Jahlborn 14:56, 24 October 2008 (UTC)
When do we submit these extra credit questions?
I have no idea I was wondering that myself. Maybe we should ask Uli in class next lesson. I'm pretty sure I need to do this prob. set though.
--Jahlborn 08:54, 10 November 2008 (UTC)
We should find out when these are due, because it would be bad to miss the due date.--Podarcze 17:05, 16 November 2008 (UTC)--Podarcze 17:05, 16 November 2008 (UTC)
