tag:blogger.com,1999:blog-3722233.post6385731915939062477..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Math Problems on vacationLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-6780845380007524052008-09-12T05:49:00.000-05:002008-09-12T05:49:00.000-05:00For 1, a lot of people used recursion (Fibonacci) ...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.<BR/><BR/>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.Steppenwolfhttps://www.blogger.com/profile/02429889115227193580noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77876005719514038032008-08-27T03:00:00.000-05:002008-08-27T03:00:00.000-05:00For 1Is it 5^(n-1) * n! ?Simple induction logic wo...For 1<BR/>Is it 5^(n-1) * n! ?<BR/>Simple induction logic works<BR/>Say, We can seat the couples with the constraints mentioned in Tn ways.Now put one more couple.<BR/><BR/>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. <BR/><BR/>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 <BR/>4*(n+1) ways<BR/><BR/>Tn+1 = 5(n+1)Tn<BR/><BR/>So Tn = 5^(n-1) * n!Vivekhttps://www.blogger.com/profile/12216771733577241232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48491278441848024322008-08-13T15:20:00.000-05:002008-08-13T15:20:00.000-05:00I see, I made a mistake in filling in consequences...I see, I made a mistake in filling in consequences of the middle numbers.<BR/><BR/>If you look at the graph we are 3-coloring, the degrees of the vertices in order are:<BR/><BR/>5,6,6,5,6,6,6,6,6,7,7,7,6,6, and symmetrically<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48087290655773102322008-08-13T14:50:00.000-05:002008-08-13T14:50:00.000-05:00It's not quite unique up to recolorings. Without ...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.<BR/><BR/>Unfortunately, it's not really clear how to generalize this approach to more colors, let alone other polynomials.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3678491999288676712008-08-13T14:21:00.000-05:002008-08-13T14:21:00.000-05:00Former VDW undergrad, that's a very nice argument ...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.<BR/><BR/>The exhaustive search makes a potentially useful programming exercise, though -- I may use it sometime.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87041632399473071742008-08-13T13:37:00.000-05:002008-08-13T13:37:00.000-05:00The construction that shows 29 is impossible goes ...The construction that shows 29 is impossible goes as follows:<BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37539560099677117372008-08-13T11:41:00.000-05:002008-08-13T11:41:00.000-05:00My first solution to the VDW problem worked for {1...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83295555236992079862008-08-13T07:21:00.000-05:002008-08-13T07:21:00.000-05:00The exact answer is 29.That is(1) For any 3-colori...The exact answer is 29.<BR/>That is<BR/>(1) For any 3-coloring of<BR/>{1,...,29} there is an <BR/>x < y <BR/>with y-x a square and <BR/> COL(x)=COL(y), and<BR/>(2) there exists a 3-coloring<BR/>of {1,...,28} so that there<BR/>is no x < y with y-x a square<BR/>and COL(x)=COL(y).<BR/>This is part of a paper<BR/>I am writing (with C. Kruskal and J. Kruskal)<BR/>with tentative title<BR/>SANE BOUNDS ON SOME POLYVDW NUMBERS.<BR/><BR/>bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45162568548986915452008-08-13T01:06:00.000-05:002008-08-13T01:06:00.000-05:00Q3: If (a,b,c) is a Pythagorean triple, then it is...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.<BR/><BR/>This shows that the length of a 3-colorable interval must be less than 43. What is the sharpest value?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43001994571258247792008-08-12T15:29:00.000-05:002008-08-12T15:29:00.000-05:00I prefer to see Q4 like this:Say that instead of b...I prefer to see Q4 like this:<BR/><BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36534178866052314622008-08-12T14:53:00.000-05:002008-08-12T14:53:00.000-05:00A slightly nicer way to see 4:Look at the first pe...A slightly nicer way to see 4:<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90240988744394140332008-08-12T14:25:00.000-05:002008-08-12T14:25:00.000-05:00For 4:If n>1, then answer is 1/2. Prove this by...For 4:<BR/><BR/>If n>1, then answer is 1/2. Prove this by induction: the first person sits in:<BR/><BR/>(1)his own seat<BR/>(2)the last person's seat<BR/>(3)any other seat<BR/><BR/>(1) and (2) even each other out, and (3) gives 1/2 by induction.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11904653626333417012008-08-12T14:21:00.000-05:002008-08-12T14:21:00.000-05:00For 2:Run the first 0.2 of each mile very fast and...For 2:<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15477135870768462482008-08-12T14:17:00.001-05:002008-08-12T14:17:00.001-05:00Regarding the two-pile game: This is the game of E...Regarding the two-pile game: This is the game of Euclid! I once wrote a little paper on this game!<BR/><BR/>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).)<BR/><BR/>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.<BR/><BR/>http://www.cs.tau.ac.il/research/gabriel.nivasch/publications/index.html#euclidAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26072450899908259282008-08-12T14:17:00.000-05:002008-08-12T14:17:00.000-05:00Trying an answer for first question : Fib(n+1)2^n(...Trying an answer for first question : Fib(n+1)2^n(n!) where fib(n) is n'th number in Fibonacci sequence.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42324017021064057752008-08-12T13:37:00.000-05:002008-08-12T13:37:00.000-05:00I'm going to do this with {0, ..., 2005} instead o...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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>1 can't have the same color as 0 or 50, so it's green.<BR/><BR/>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!Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.com