January 2009 - mathfun@mailman.xmission.com

[math-fun] Isodiametric problem
by victor miller 16 Sep '10

16 Sep '10

A few days ago, at the AMS meeting, I saw a neat talk by Michael Mossinghoff about "isodiametic" problems -- e.g. Fix the diameter of a conv ex n-gon and ask for the ones with maximum perimeter. He reduced the problem to finding univariate polynomials whose non-zero coefficients alternate between +/- 1 and are divisible by a particular cyclotomic polynomial.. He was able to calculate all such up to about 500. Each such polynomial is compactly encoded by th length of the gaps between the non-zero terms. For small n almost all were periodic. He showed how a certain family of periodic constrctions give solutions, but as n got bigger the "sporadic" ones swamped them. He conjectued that these are eventually all of them. He had lots of pictures. The paper is not available yet. Victor

7 9

Re: [math-fun] Fast factoring ?? (really denesting)
by rwg＠sdf.lonestar.org 08 May '09

08 May '09

> On Fri, Dec 19, 2008 at 12:20 PM, <rwg(a)sdf.lonestar.org> wrote: > >> Amen. I've now tried ~ 10^8 cases of (a^(1/5)-b^(1/5))^(1/3) >> without further success, and for sqrt, only >> >> 3/5 4/5 3/5 2/5 2/5 4/5 1/5 1/5 >> 1/5 1/5 - 2 3 + 3 + 2 2 3 - 2 3 + 2 >> sqrt(4 - 3 ) = ---------------------------------------------------. >> 5 >> >> And, of course, these can only give pentanomials. >> --rwg >> ALGORISMIC MICROGLIAS > > I have no technical knowledge on denesting, but here is how I look at > the problem: > > Since sqrt( a^(1/5) + b^(1/5) ) = a^(-2/5) * sqrt( a + (a^4*b)^(1/5) > ), I'll consider only the form: sqrt( a + b^(1/5) ). If sqrt( a + > b^(1/5) ) could be denested, I'd expect it to be denested into the > form: > > x0 + x1*b^(1/5) + x2*b^(2/5) + x3*b^(3/5) + x4*b^(4/5). Notice that in the (comparatively easy) 4th root case, your conjecture catches 1/4 3/4 1/4 sqrt(161 - 12 5 ) = 2 5 - 3 sqrt(5) + 4 5 + 6 but not 1/4 1/4 1/4 3/4 3/4 1/4 sqrt(2) sqrt(31 - 4 3 5 ) = 3 5 - 2 sqrt(5) + 3 5 + 2 sqrt(3). > That's why I don't think you could find anything longer than > pentanomial. OTOH, sqrt( a^(1/7) + b^(1/7) ) is a better bet for > finding hexanomials or longer. Indeed, but the only one I've found so far is perversely pentanomial: 1/7 Sqrt(7 (2 - 2 )) 1/7 3/7 5/7 6/7 ------------------ = -1 + 2 2 + 2 + 2 - 2 . 1/14 2 > Just my 2 cents. > > Warut > You didn't propose 6th roots. Did you have reason to suspect that they are as infertile as they seem to be? --rwg PRECHRISTMAS PETRARCHISMS ALGORISMIC MICROGLIAS

17 71

Re: [math-fun] muffin problem
by Michael Reid 13 Mar '09

13 Mar '09

> I've calcuated U(4,13) = 11/6 (using Veit's notation) using CPLEX > (industrial strength MIP) with the MIP that Veit suggested. i can now determine T(4, n) in general. recall that my normalization is that T(m, n) equals the maximum c such that there is a partition of 1 with all parts >= c , which is simultaneously a refinement of 1/m + 1/m + ... + 1/m = 1 and also of 1/n + 1/n + ... + 1/n = 1 . T(4, 4n) = 1/4n , with unique partition 4n * 1/(4n) . this is obvious. T(4, 4n+2) = 1/(8n+4) . 4 * [(2n+1) * 1/(8n+4)] <---> (4n+2) * [1/(8n+4) + 1/(8n+4)] achieves this bound. moreover, at least one 1/(4n+2) must be split, so it has a part at most 1/(8n+4) . the partition is not unique; at least two 1/(4n+2) 's must split into 1/(8n+4) + 1/(8n+4) . the others either split in the same way, or do not split. T(4, 2n+1) = (2n-1)/(4n(2n+1)) if n >= 1 . the case n = 1 is T(4, 3) = T(3, 4) = 1/12 , which is easy to handle separately. if n > 1 , there is a unique optimal partition, which is 2 * [n * (2n-1)/(4n(2n+1)) + 1/(4n+2)] + 2 * [n * 1/(4n)] <---> 2n * [(2n-1)/(4n(2n+1)) + 1/(4n)] + [1/(4n+2) + 1/(4n+2)] suppose that 1/4 splits as 1/(2n+1) + 1/(2n+1) + ... + 1/(2n+1) + ( p smaller parts ) , where there are k > 0 parts of size 1/(2n+1) . if p >= n - 2k + 1 , then the smallest of the parts is at most (1/4 - k/(2n+1))/p <= ((2n-4k+1)/(4(2n+1)))/(n - 2k + 1) = (2 - 1/(n - 2k + 1))/(4(2n+1)) < (2 - 1/n)/(4(2n+1)) = (2n-1)/(4n(2n+1)) , so this part is too small. on the other hand, if p <= n - 2k , then the largest of the parts not equal to 1/(2n+1) is at least (1/4 - k/(2n+1))/p . since this occurs as a part of 1/(2n+1) , it has another part at most 1/(2n+1) - (1/4 - k/(2n+1))/p <= 1/(2n+1) - (1/4 - k/(2n+1))/(n - 2k) = (2 - 1/(n - 2k))/(4n(2n+1)) < (2 - 1/n)/(4(2n+1)) = (2n-1)/(4n(2n+1)) , so again there is a part which is too small. this shows that no 1/4 can contain any parts of size 1/(2n+1) , and therefore every 1/(2n+1) must split. now suppose that 1/4 splits into p parts, which we know must all be less than 1/(2n+1) . if p >= n+2 , then the smallest of these parts is <= 1/(4(n+2)) < (2n-1)/(4n(2n+1)) , so too small. (here we need n > 1 .) if p <= n-1 , then the largest of these parts is at least 1/(4(n-1)) , and since it occurs as part of 1/(2n+1) , there must be another part of size <= 1/(2n+1) - 1/(4(n-1)) < (2n-1)/(4n(2n+1)) , which is again too small. therefore, each 1/4 splits into either n or n+1 parts. if 1/(2n+1) splits into 3 or more parts, then some part has size <= 1/(3(2n+1)) , which is less than (2n-1)/(4n(2n+1)) if n > 1 . thus each 1/(2n+1) splits into exactly 2 parts, so there are 4n+2 parts in total. now two of the 1/4 's must split into n parts, and the other two must split into n+1 parts. moreover, the largest part in either of the 1/4 's that split into n parts has size >= 1/(4n) . since it occurs as part of 1/(2n+1) , the other part has size <= 1/(2n+1) - 1/(4n) = (2n-1)/(4n(2n+1)) . thus, to have optimality, both of the 1/4 's that split into 1/(4n) + 1/(4n) + ... + 1/(4n) , and now n of the 1/(2n+1) 's must split as (2n-1)/(4n(2n+1)) + 1/(4n) . finally, there are 2n parts of the minimal size (2n-1)/(4n(2n+1)) , and neither of the remaining 1/4 's can contain n+1 of them , so both contain n of them, and thus split as n * (2n-1)/(4n(2n+1)) + 1/(4n+2) , which determines the partition. T(1, n) and T(2, n) are very easy to determine in general. it looks like there is probably also pattern in T(3, n) . T(6, n) might also be possible to determine in general. mike

5 11

[math-fun] New add-mult squares
by Christian Boyer 06 Feb '09

06 Feb '09

Help needed! Look at this matrix: 75 38 207 102 11 20 91 56 5 44 49 104 57 50 153 138 133 200 17 92 45 66 21 26 99 30 39 14 175 152 23 68 78 63 22 15 184 119 100 19 136 161 76 25 42 117 10 33 28 13 40 77 34 69 114 225 46 51 150 171 52 7 88 35 If you ADD the numbers of each row or column or diagonal, always the same sum S = 600. If you MULTIPLY the numbers of each row or column or diagonal, always the same product P = 67463283888000. This kind of object is called an additive-multiplicative (or addition-multiplication, or add-mult) magic square. Some few 8x8 and 9x9 squares are known: http://mathworld.wolfram.com/Addition-MultiplicationMagicSquare.html But larger squares (10x10 and above) are extremely rare, most of them being unknown. I have some new squares, from 10x10 to 25x25. But before their publication, I would like to be sure that they are fully correct. If you can help me, checking these squares (and that the n^2 used integers in each nxn square are distinct, very important...), send me a private message. Thanks in advance! Integer values < 15,000 Products P < 10^80 (multiprecision needed) Christian. www.multimagie.com/indexengl.htm

1 2

[math-fun] tennis probabilities
by Erich Friedman 29 Jan '09

29 Jan '09

i've been watching the australian open tennis tournament with interest, and have these probability questions. assume here that two players are equally matched. also assume that the usual tennis scoring is used: a game is won by the first player to win 4 points, but you must win by 2. a set is won by the first player to win 6 games, but you must win by 2. if the game score is 6-6, a tiebreaker occurs and the first one to 7 points wins, again you have to win by 2. a match (on the men's side) is won by the first player to win 3 sets. but if the set score is 2-2, no tiebreaker is played in the last set. the first player to win 2 more games than his opponent wins the match. EASY: what is the probability that the winner of a game faced game point against him? (that is, what is the probability that the eventual winner was one point away from defeat?) HARD: what is the probability that the winner of a set faced set point against him? REALLY HARD: what is the probability that the winner of a match faced match point against him? BONUS QUESTION: how do these probabilities change if one player is favored over the other? erich

1 0

Re: [math-fun] simultaneous refinements of 3 partitions (was: muffins)
by Michael Reid 28 Jan '09

28 Jan '09

> > Could muffin(4k,5k,6k,7k) = 1/21 for some k? > > surely you mean 1/(21k) above. and yes, n = 2 works: [ ... ] k = 3 also works: [2 * 1/63 + 1/45 + 37/1260] + [2 * 1/63 + 8/315 + 11/420] + [1/63 + 2 * 17/840 + 17/630] + [1/63 + 23/1260 + 13/630 + 1/35] + 2 * [2 * 1/63 + 61/2520 + 23/840] + [41/2520 + 11/630 + 59/2520 + 11/420] + [2/105 + 7/360 + 3/140 + 59/2520] + [3/140 + 19/630 + 2/63] + 2 * [1/42 + 71/2520 + 79/2520] + [41/2520 + 23/1260 + 7/360 + 37/1260] <---> [1/63 + 2/105 + 2/63] + [1/63 + 13/630 + 19/630] + [1/63 + 1/45 + 1/35] + [1/63 + 1/42 + 17/630] + [11/630 + 1/42 + 8/315] + 2 * [1/63 + 7/360 + 79/2520] + 2 * [1/63 + 3/140 + 37/1260] + 2 * [1/63 + 59/2520 + 23/840] + 2 * [41/2520 + 61/2520 + 11/420] + 2 * [23/1260 + 17/840 + 71/2520] <---> [2 * 1/63 + 1/42] + [1/63 + 11/630 + 1/45] + [1/63 + 2/105 + 13/630] + [1/42 + 2/63] + [8/315 + 19/630] + [17/630 + 1/35] + 2 * [1/63 + 41/2520 + 59/2520] + 2 * [1/63 + 23/1260 + 3/140] + 2 * [1/63 + 7/360 + 17/840] + 2 * [61/2520 + 79/2520] + 2 * [11/420 + 37/1260] + 2 * [23/840 + 71/2520] <---> 3 * [3 * 1/63] + [1/63 + 2/63] + [11/630 + 19/630] + [2/105 + 1/35] + [13/630 + 17/630] + [1/45 + 8/315] + [2 * 1/42] + 2 * [41/2520 + 79/2520] + 2 * [23/1260 + 37/1260] + 2 * [7/360 + 71/2520] + 2 * [17/840 + 23/840] + 2 * [3/140 + 11/420] + 2 * [59/2520 + 61/2520] i got this in much the same way: combining 3 optimal partitions for the (5, 6, 7) case and rescaling. then it was a simple matter to arrange the parts to get a refinement of 12 * 1/12 . moreover, by combining the k = 2 and k = 3 cases, we get partitions that prove T(4k, 5k, 6k, 7k) = 1/(21k) for all k > 1 . my earlier search for optimal partitions for the (5, 6, 7) case shows, modulo possibly missing some sub-sub-subcases, that T(4, 5, 6, 7) < 1/21 , as scott surmised. i suppose now i should scrutinize the details of this search to make sure i didn't miss anything. mike

1 0

Re: [math-fun] muffin problem
by James Propp 28 Jan '09

28 Jan '09

Veit Elser writes: >It's easy to show > >S(k m, k p) >= S(m, p). > >Proof: >I prefer the symmetrical quantity U(m, p) = p S(m, p). >[etc.] It's actually easier to see this fact if one uses S instead of U and thinks in terms of actual muffins: If you've got km muffins and kp people, divide the first m muffins among the first p people, the next m muffins among the next p people, etc. If in each batch of p people nobody gets a piece of size smaller than S(m,p), then none of the mp people gets a piece of size smaller than S(m,p), so we've found a way to divide km mufins among kp people so that nobody gets a piece of size smaller than S(m,p). That is, S(km,kp) is at least as large as S(m,p). I suspect that S(km,kp) sometimes is strictly larger than S(m,p); what do the rest of you think? Jim Propp

1 0

Re: [math-fun] muffin problem
by James Propp 28 Jan '09

28 Jan '09

Scott wrote: >Conjecture 6: S(km,kp) = S(m,p) Has anyone settled this? I don't even see how to prove that S(km,kp) stabilizes as k goes to infinity with m,n fixed. Jim Propp

2 1

Re: [math-fun] simultaneous refinements of 3 partitions (was: muffins)
by Michael Reid 28 Jan '09

28 Jan '09

> Could muffin(4k,5k,6k,7k) = 1/21 for some k? surely you mean 1/(21k) above. and yes, n = 2 works: [2 * 1/42 + 1/30 + 37/840] + [2 * 1/42 + 4/105 + 11/280] + [1/42 + 41/1680 + 61/1680 + 17/420] + [1/42 + 23/840 + 13/420 + 3/70] + [1/42 + 17/560 + 59/1680 + 1/28] + [11/420 + 1/35 + 7/240 + 23/560] + [9/280 + 19/420 + 1/21] + [1/28 + 71/1680 + 79/1680] <---> [1/42 + 1/35 + 1/21] + [1/42 + 13/420 + 19/420] + [1/42 + 1/30 + 3/70] + [1/42 + 1/28 + 17/420] + [11/420 + 1/28 + 4/105] + [1/42 + 7/240 + 79/1680] + [1/42 + 9/280 + 37/840] + [1/42 + 59/1680 + 23/560] + [41/1680 + 61/1680 + 11/280] + [23/840 + 17/560 + 71/1680] <---> [2 * 1/42 + 1/28] + [1/42 + 11/420 + 1/30] + [1/42 + 1/35 + 13/420] + [1/28 + 1/21] + [4/105 + 19/420] + [17/420 + 3/70] + [1/42 + 41/1680 + 59/1680] + [1/42 + 23/840 + 9/280] + [1/42 + 7/240 + 17/560] + [61/1680 + 79/1680] + [11/280 + 37/840] + [23/560 + 71/1680] <---> 2 * [3 * 1/42] + [1/42 + 1/21] + [11/420 + 19/420] + [1/35 + 3/70] + [13/420 + 17/420] + [1/30 + 4/105] + [2 * 1/28] + [41/1680 + 79/1680] + [23/840 + 37/840] + [7/240 + 71/1680] + [17/560 + 23/560] + [9/280 + 11/280] + [59/1680 + 61/1680] i got this by joining two of the partitions i found for (5, 6, 7) and dividing by 2 so that all parts add to 1 . it is guaranteed to be a refinement of 10 * 1/10 , 12 * 1/12 and of 14 * 1/14 . then i rearranged the parts to show that it's also a refinement of 8 * 1/8 . note that the largest part is 1/21 , which is twice the smallest part. thus we get another partition by splitting the largest part in half. there are also other ways to rearrange the same set of parts within the 8 * 1/8 . also, it is easy to show that T(5k, 7k) = 1/(21k) , so that 1/42 is not only a lower bound for T(8, 10, 12, 14) ; it's the exact value. mike

1 0

[math-fun] simultaneous refinements of 3 partitions (was: muffins)
by Michael Reid 28 Jan '09

28 Jan '09

some more (minor) results for the 3-parameter case. recall that my notation is: T(n_1, n_2, ... , n_k) is the largest c such that there is a partition of 1 with all parts >= c which is a simultaneous refinement of 1/n_i + 1/n_i + ... + 1/n_i = 1 for each i . i noticed that there are examples of optimal partitions for T(m, n) which have some 1/n 's unsplit, and others split. unless the minimal part is 1/(2n) (or 1/n in the case that m divides n ), we have some freedom in choosing how to split the previously unsplit 1/n 's, and sometimes we can get optimal partitions for the 3-parameter case. for example: T(5, 8) = 1/20 , from [4 * 1/20] + 4 * [3/40 + 1/8] <---> 4 * [1/20 + 3/40] + 4 * [1/8] . by splitting two of the 1/8 's into 7/120 + 1/15 , we also get a refinement of 1/3 + 1/3 + 1/3 : [3 * 1/20 + 7/120 + 1/8] + [1/20 + 7/120 + 3 * 3/40] + [2 * 1/15 + 3/40 + 1/8] , which shows that T(3, 5, 8) = 1/20 . T(6, 8) = 1/24 , from 6 * [1/24 + 1/8] <---> 2 * [3 * 1/24] + 6 * [1/8] . by splitting the 1/8 's as 7/120 + 1/15 , we also get a refinement of 1/5 + 1/5 + 1/5 + 1/5 + 1/5 : 3 * [2 * 1/24 + 2 * 7/120] + 2 * [3 * 1/15] , which shows that T(5, 6, 8) = 1/24 . instead, we might split 3 of the 1/8 's as 1/21 + 13/168 , and the other 3 as 5/84 + 11/168 , to get a refinement of 7 * 1/7 : 3 * [1/24 + 1/21 + 13/168] + 3 * [1/24 + 5/84 + 11/168] + [3 * 1/21] , which shows that T(6, 7, 8) = 1/24 . alternatively, if we split each 1/8 as 1/18 + 5/72 , we get a refinement of 9 * 1/9 : 6 * [1/24 + 5/72] + 3 * [2 * 1/18] , which shows that T(6, 8, 9) = 1/24 . > Muffin (5,6,7) = muffin (2,3,5,6,7) = 1/21: > 210/7 = [10.10.10], 2[11.19], [12.18], [13.17], 2[14.16] > 210/6 = [10.12.13], 2[10.11.14], [17.18], 2[16.19] > 210/5 = [16.16.10], [17.11.14], [18.10.14], [19.10.13], [19.11.12] very nice! i noticed that there was a continuum of optimal partitions for T(5, 7) when i briefly tried to determine if some of the optimal partitions were unique, but did not make the connection to using this to try for optimal partitions for the 3-parameter case. this is better than what i did above, because the above is a special case of having continua of optimal partitions. > I believe this partition is unique up to piece size and multiplicity, > and that muffin(4,5,6,7) < 1/21. the latter statement would follow from the former, so i tried to prove the former. but it is not true, as i found several more optimal partitions for T(5, 6, 7): (1) [1/21 + 2/35 + 2/21] + [1/21 + 13/210 + 19/210] + [1/21 + 1/15 + 3/35] + [1/21 + 1/14 + 17/210] + [11/210 + 1/14 + 8/105] <---> [2 * 1/21 + 1/14] + [1/21 + 11/210 + 1/15] + [1/21 + 2/35 + 13/210] + [1/14 + 2/21] + [8/105 + 19/210] + [17/210 + 3/35] <---> [3 * 1/21] + [1/21 + 2/21] + [11/210 + 19/210] + [2/35 + 3/35] + [13/210 + 17/210] + [1/15 + 8/105] + [2 * 1/14] (2) [1/21 + 37/630 + 59/630] + [1/21 + 22/315 + 26/315] + [1/21 + 23/315 + 5/63] + [31/630 + 4/63 + 11/126] + [1/18 + 19/315 + 53/630] <---> [1/21 + 31/630 + 22/315] + [1/21 + 1/18 + 4/63] + [1/21 + 37/630 + 19/315] + [23/315 + 59/630] + [5/63 + 11/126] + [26/315 + 53/630] <---> [3 * 1/21] + [31/630 + 59/630] + [1/18 + 11/126] + [37/630 + 53/630] + [19/315 + 26/315] + [4/63 + 5/63] + [22/315 + 23/315] (3) [1/21 + 7/120 + 79/840] + [1/21 + 9/140 + 37/420] + [1/21 + 59/840 + 23/280] + [41/840 + 61/840 + 11/140] + [23/420 + 17/280 + 71/840] <---> [1/21 + 41/840 + 59/840] + [1/21 + 23/420 + 9/140] + [1/21 + 7/120 + 17/280] + [61/840 + 79/840] + [11/140 + 37/420] + [23/280 + 71/840] <---> [3 * 1/21] + [41/840 + 79/840] + [23/420 + 37/420] + [7/120 + 71/840] + [17/280 + 23/280] + [9/140 + 11/140] + [59/840 + 61/840] (4) [3 * 1/21 + 2/35] + [1/21 + 13/210 + 19/210] + [1/21 + 1/15 + 3/35] + [1/21 + 1/14 + 17/210] + [11/210 + 1/14 + 8/105] <---> 2 * [2 * 1/21 + 1/14] + [1/21 + 11/210 + 1/15] + [1/21 + 2/35 + 13/210] + [8/105 + 19/210] + [17/210 + 3/35] <---> 2 * [3 * 1/21] + [11/210 + 19/210] + [2/35 + 3/35] + [13/210 + 17/210] + [1/15 + 8/105] + [2 * 1/14] partition (4) is derived from (1) by splitting the 2/21 into 2 * 1/21 . i got these by classifying all optimal partitions for the (5, 7) case, and then examining those for special cases that are also refinements of 6 * 1/6 . for the (5, 7) case, i found 9 2-dimensional families, ( 6 parallelogram regions and 3 hexagonal regions), 9 1-dimensional families, and 3 isolated cases. that gives some idea of the complexity of the problem. i think that i found all solutions to the (5, 7) case and also to the (5, 6, 7) case, which would imply that indeed T(4, 5, 6, 7) < 1/21 . however, i am not overly confident that i didn't miss a sub-sub-sub-subcase somewhere! it is easy to specialize the aforementioned families to find a partition that establishes T(4, 5, 7) = 1/21 , for instance, [1/21 + 1/20 + 1/15 + 3/35] + [1/21 + 2 * 5/84 + 1/12] + [1/21 + 2/35 + 29/420 + 8/105] + [31/420 + 1/12 + 13/140] <---> [1/21 + 5/84 + 13/140] + [1/21 + 1/15 + 3/35] + [1/21 + 29/420 + 1/12] + [1/20 + 31/420 + 8/105] + [2/35 + 5/84 + 1/12] <---> [3 * 1/21] + [1/20 + 13/140] + [2/35 + 3/35] + 2 * [5/84 + 1/12] + [1/15 + 8/105] + [29/420 + 31/420] also, a partition that demonstrates T(4, 6, 7) = 1/21 is easy to find: [2 * 1/21 + 5/84 + 2/21] + [3 * 5/84 + 1/14] + [1/14 + 1/12 + 2/21] + [3 * 1/12] <---> 2 * [1/21 + 2 * 5/84] + 2 * [1/14 + 2/21] + 2 * [2 * 1/12] <---> 2 * [1/21 + 2/21] + 4 * [5/84 + 1/12] + [2 * 1/14] . mike

1 0