Tuesday, August 12, 2008

Math Problems on vacation

SO, as mentioned in my last post, there were two other math-folks on the bus tour I was taking. So what did we do? Exchange problems to solve on the bus. We alternated.
  1. I asked them: if there are n couples in a resturant, and everyone sits either across from or next to their darling at a rectangular table (nobody sits at the ends) then how many ways can they be seated?
  2. They asked me: A marathon is 26.2 miles. A runner runs in such a way that during EVERY 1-mile interval he averages exactly 10 miles an hour. But his overall time is better than 10 miles an hour. How can this be?
  3. I asked them: Show that if no matter how your 3-color the numbers {1,...,2006} there will be two points, a square apart, the same color.
  4. They asked me: There is a bus where n people have assigned seats. The first person sits randomly instead of in his assigned seat. Henceforth, every person looks for his assigned seat, and if he does not find it, sits in a random seat. What is the prob that the last person sits in his assigned seat?
How did we do on these problems? They got my problems correctly. I basically got theirs (missed some points).

It was interesting coming up with problems that had not well known. I couldn't ask them truth-teller-and-liar problems or hats problems, since these are well known. Some of the problems above have appeared on this blog before. Not sure if that makes them well-known. At least they didn't know them. I tried asking the following problem that I thought was not so well known (I read it in American Math Monthly and told it to Peter Winkler two years ago-- he had not heard of it), but they had already heard it:

Here is a game: There are initially two piles of stones with a in one pile and b in the other. Every move a player removes a multiple of the smaller pile from the larger. If either pile has 0 in it then you cannot move. THe first player who can't move loses. For which (a,b) does player I have a winning stradegy.

Readers- I am not going to post solution. But you can in the comments!

16 comments:

  1. I'm going to do this with {0, ..., 2005} instead of {1, ..., 2006}. We attempt to find a coloring with 3 colors such that all numbers a square apart are different colors, and show that this is impossible.

    First, note that 0, 9, and 25 must be different colors. Without loss of generality color 0 red, 9 blue, and 25 green. Similarly 16 can't be the same color as 0 or 25, so color 16 blue.

    Now, 34 can't be the same color as either 9 or 25, so it's red. And 41 can't be the same color as 16 or 25, so it's red. 50 can't be the same color as 25, 34 or 41, so it's blue.

    1 can't have the same color as 0 or 50, so it's green.

    Finally, note that 1 is green, 9 is blue, and 41 is red. 5 differs from each of these by a square -- so there's no color left for it!

    ReplyDelete
  2. Trying an answer for first question : Fib(n+1)2^n(n!) where fib(n) is n'th number in Fibonacci sequence.

    ReplyDelete
  3. Regarding the two-pile game: This is the game of Euclid! I once wrote a little paper on this game!

    The solution involves the golden ratio. (In my paper the rules are a little different: The piles must always have a positive number of stones, and the game ends when both piles are equal. The player who can't move loses. This makes almost no difference, because from position (a, ka) you win by moving to (a, a) instead of to (a, 0).)

    In my paper I analyze the "Sprague-Grundy function", which is a generalization of the problem. It turns out that the Sprague-Grundy function of this game has an extremely cute formula.

    http://www.cs.tau.ac.il/research/gabriel.nivasch/publications/index.html#euclid

    ReplyDelete
  4. For 2:

    Run the first 0.2 of each mile very fast and the rest slow. More specifically: the first 0.2 in e many hours, and the other 0.8 of each mile in (0.1 - e) many hours. Then the overall time e*27+(0.1 -e)*26 = 2.6+e hours. So the average speed is 26.2/(2.6+e) which is bigger than 10 iff e < .02.

    ReplyDelete
  5. For 4:

    If n>1, then answer is 1/2. Prove this by induction: the first person sits in:

    (1)his own seat
    (2)the last person's seat
    (3)any other seat

    (1) and (2) even each other out, and (3) gives 1/2 by induction.

    ReplyDelete
  6. A slightly nicer way to see 4:

    Look at the first person who either randomly selects their own seat, or takes the last person's seat. Said person is not the last person. Each of the two cases is equally likely. so the probability is 1/2.

    ReplyDelete
  7. I prefer to see Q4 like this:

    Say that instead of being polite and seeking a random seat when his seat is already taken, every person insists that the first person will stand up and find himself another (random) seat.

    This way, everybody except the first person will be seating in their own places when the last person approaches her seat; this seat will be taken by the first person with probability 1/2.

    ReplyDelete
  8. Q3: If (a,b,c) is a Pythagorean triple, then it is easy to see that two points have to have the same color if their distance is b^2-a^2. Let's use the Pythagorean triples (3,4,5) and (20,21,29): the distances are 16-9=7 and 441-400=41, respectively. This means that 0 must have the same color as 42=6*7, and 41. But 42-41=1 is a square.

    This shows that the length of a 3-colorable interval must be less than 43. What is the sharpest value?

    ReplyDelete
  9. The exact answer is 29.
    That is
    (1) For any 3-coloring of
    {1,...,29} there is an
    x < y
    with y-x a square and
    COL(x)=COL(y), and
    (2) there exists a 3-coloring
    of {1,...,28} so that there
    is no x < y with y-x a square
    and COL(x)=COL(y).
    This is part of a paper
    I am writing (with C. Kruskal and J. Kruskal)
    with tentative title
    SANE BOUNDS ON SOME POLYVDW NUMBERS.

    bill g.

    ReplyDelete
  10. My first solution to the VDW problem worked for {1,...,1610}. I also, for laughs, did the tree of partial solutions by hand up to about n=12. Bill, is your result of 28 by exhaustive search? I would think it would work in reasonable time, though an analytic argument would be far more interesting.

    ReplyDelete
  11. The construction that shows 29 is impossible goes as follows:
    Suppose by contradiction, we had such a coloring. Note that 1 and 26 must be different colors; call them red and green. 10 and 17 are then both the same color, blue. A similar argument shows that the pairs (11,18), (12,19), and (13,20) are each the same color, a fact that we will use in a moment. We now note that 13 and 14 are distinct colors, and neither can be blue, since 17-13=4 and 14-10=4. But then 18 must be the same color as 13, since 18-17=1 and 18-14=4. We recall from earlier that 11 and 18 are the same color, and that 13 and 20 are the same color. But then we need 11 and 20 to both be the same color, which completes our contradiction.

    It's not quite as bad as exhaustion, but it isn't extensible. I don't know if Gasarch has a better approach yet. Note that, with this approach, making a valid coloring of 28 is easy.

    ReplyDelete
  12. Former VDW undergrad, that's a very nice argument that's far more informative than the exhaustive search I had in mind. And from the construction of the valid 28-sequence you get that it is unique up to the names of the colors.

    The exhaustive search makes a potentially useful programming exercise, though -- I may use it sometime.

    ReplyDelete
  13. It's not quite unique up to recolorings. Without 29 being required to have a color, 13 and 20 no longer have to be the same color, which yields a unique coloring of everything except {1,2,3,6,7,22,23,26,27,28} up to permuting the color names, and only a handful of allowed colorings on the remainder. I never did develop a particularly intuitive sense for why 4 and 5 should be more constrained than 6 and 7.

    Unfortunately, it's not really clear how to generalize this approach to more colors, let alone other polynomials.

    ReplyDelete
  14. I see, I made a mistake in filling in consequences of the middle numbers.

    If you look at the graph we are 3-coloring, the degrees of the vertices in order are:

    5,6,6,5,6,6,6,6,6,7,7,7,6,6, and symmetrically

    so position 4 is in sort of a trough for degree, while position 5 is connected to the low-degree nodes 1 and 4. It's not surprising that your argument first attacked 10, 11, 12, 17, 18, and 19, the highest-degree nodes.

    ReplyDelete
  15. For 1
    Is it 5^(n-1) * n! ?
    Simple induction logic works
    Say, We can seat the couples with the constraints mentioned in Tn ways.Now put one more couple.

    The new couple can sit across in n+1 positions, they can also sit on 2 different sides of the table.So they can sit across in 2*(n+1)*Tn ways.

    They can sit next to each other on either side and interchange among themselves and in n+1 positions.So they can sit next to each other in
    4*(n+1) ways

    Tn+1 = 5(n+1)Tn

    So Tn = 5^(n-1) * n!

    ReplyDelete
  16. For 1, a lot of people used recursion (Fibonacci) -- but this can also be solved quite simply by writing the expression for a general k (where k is the number of couples who are sitting sideways): (2^n)*(n!)*((n-k)C(k)) and then sum over all even k < (n/2). This also leads to a nice summation formula for a fibonacci number that I didn't know before.

    2 seems trivial, if we consider velocity as a function of distance to be any positive periodic signal of period 1. Since 26.2 is not a multiple of 1, you can adjust the start point of the periodic signal to make the over all average velocity > than the average over a period of 1.

    ReplyDelete