[math-fun] more muffin problem results
I found some interesting muffin results and insights by considering a subset of optimal muffin partitions which are "uniform". To simplify terminology and analysis I restrict consideration to muffin instances (m,p) with m muffins >= p people. Solutions for the case m<p then follow by duality, as previously noted. For piece size S(m,p) I normalize muffin size to 1. Conjecture 1: S(m,p) >= 1/3 for all muffin instances with m >= p. I don't have a proof yet, but many cases and the problem structure support this conjecture. Combined with Veit Elser's bound this gives a tight bound S(m,p) = 1/3 for 1 < m/p < 3/2. The basic muffin problem optimizes the maximum size of the minimum muffin piece. Some secondary optimizations: say an optimal partition is "ratio optimal" if it minimizes the ratio of the largest piece to the smallest piece, and "piece optimal" if it minimizes the total number of pieces. Michael Reid's examples have been piece optimal, but ratio optimal partitions provide a nice dimensionless measure of piece sizes. Define R_X(m,p) for a given muffin partition X to be the ratio of the largest piece size to the smallest piece size. Let R_XX(m,p) for a set of partitions XX of (m,p) be the minimum of R_X(m,p) for X in XX. Proposition 2: R_A(m,p) < 2 for every instance (m,p) and A the set of all optimal muffin partitions. Proof: starting from any optimal partition, halve the largest pieces until the proposition holds. Say a muffin partition is "uniform" if |j-k| <= 1 whenever two muffins are split into j and k pieces, respectively, and |a-b| <= 1 whenever two people receive a and b pieces, respectively. Conjecture 3: Every muffin instance has a ratio optimal partition which is uniform; R_U(m,p) = R_A(m,p), where U is the set of uniform optimal partitions. Consideration of uniform partitions gives a handle on bounding piece sizes. Conjecture 4: The number of pieces per muffin in a uniform ratio optimal muffin partition is: a). 1 if m is kp for some k >= 1; b). 3 if m/p = 4/3; b). 2 or 3 if 1 < m/p < 3/2; c). 2 otherwise. For 3/2 < m/p < 2, each muffin is split into 2 pieces and each person receives either 3 or 4 pieces. Persons receiving 3 pieces must have some piece of size at least m/3p, and its complement piece in a muffin has size at most 1-m/3p. The ratio of the pieces is (m/3p)/(1-(m/3p)) = m/(3p-m). This bound appears to be tight over a range of values. Conjecture 5: For 9/5 < m/p < 2, R_U(m,p) = m/(3p-m) and S(m,p) = 1-m/3p. Here are some example partitions m/p. These are given with integral pieces, which one may normalize if desired. I believe these are all optimal. 7/5: pieces 5,7,8: 5.5.5, 7.8*6; 7.7.7*2, 8.8.5*3 S = 1/3, R_U = 8/5 (note: 7.8*6 = 6 muffins split 7.8, 8.8.5*3 = 3 people with pieces 8.8.5) 10/7: pieces 7..13: 7.7.7, 13.8*3, 12.9*3, 11.10*3; 7.11.12*3, 3.9.13*3, 10.10.10 S = 1/3, R_U = 13/7 11/10: pieces 10..19: 10.10.10*2, 11.19*2, 12.18*2, 13.17*2, 14.16*2, 15.15; 10.10.13*2, 10.11.12*2, 14.19*2, 15.18*2, 16.17*2 S = 1/3, R_U = 19/10 12/7: pieces 3..4: 3.4*12; 3.3.3.3*3, 4.4.4*4 S = 3/7, R_U = 4/3 9/5: pieces 4..6: 5.5*3, 4.6*6; 6.6.6*2, 4.4.5.5*3 S = 2/5, R_U = 3/2 16/9: pieces 11.16: 11.16*12, 12.15*2, 13.14*2; 16.16.16*4, 11.11.11.15*2, 11.11.12.14*2, 11.11.13.13 S = 11/27, R_U = 16/11 23/13: pieces 21..31: 21.31*12, 22.30*6, 23.29*4, 26.26; 31.31.30*6, 21.21.21.29*4, 22.22.22.26*2, 23.23.23.23 S = 21/52, R_U = 31/21 7/4: pieces 5..7: 5.7*6, 6.6; 7.7.7*2, 5.5.5.6*2 S = 5/12, R_U = 7/5 17/9: pieces 10..17: 10.17*6, 11.16, 12.15, 13.14*9; 17.17.17*2, 10.12.13.16, 10.13.13.15, 11.13.13.14, 10.13.14.14*4 S = 10/27, R_U = 17/10 Conjecture 6: S(km,kp) = S(m,p) and R_U(km,kp) = R_U(m,p) for k > 1. This could have a simple proof, or very interesting counterexamples.
participants (1)
-
Scott Huddleston