tag:blogger.com,1999:blog-3722233.post3357688667258653719..comments2023-10-01T07:37:32.894-05:00Comments on Computational Complexity: Math problems involving FoodLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-81159171187772507772022-03-07T09:28:23.333-06:002022-03-07T09:28:23.333-06:00It just reminded me of the Pancake sorting problem...It just reminded me of the Pancake sorting problem https://en.wikipedia.org/wiki/Pancake_sortingAnonymoushttps://www.blogger.com/profile/17178061957434438831noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87582088478818702212022-01-20T16:39:45.568-06:002022-01-20T16:39:45.568-06:00I once posted 2 items on envy-free cake division o...I once posted 2 items on envy-free cake division on my blog referring to Selfridge & Conway algorithm:<br />algo here: http://borawriteson.blogspot.com/2009/07/cake-division.html<br />my conclusions: http://borawriteson.blogspot.com/2009/07/envy-free-cake-division-2.html Borahttps://www.blogger.com/profile/07302203351181934021noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78987590305763782162022-01-17T08:29:34.784-06:002022-01-17T08:29:34.784-06:00the "No Free Lunch" theorem ?the "No Free Lunch" theorem ?Denis Kuperbergnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58651468891479174352022-01-13T13:17:50.186-06:002022-01-13T13:17:50.186-06:00Also the Baker's Map.
Many plants have been m...Also the Baker's Map.<br /><br />Many plants have been modeled as fractals, and some of these (ginger roots, broccoli) are also edible.<br /><br />Just in the realm of beverages, there's the Drunkard's Walk (in however many dimensions). The Brouwer fixed-point theorem, and Martin Hairer's work on stochastic analysis, are sometimes described as like mixing a cup of coffee or tea.<br />Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69127993492169942722022-01-11T08:53:10.081-06:002022-01-11T08:53:10.081-06:00Not quite, but nice try!
You gotta scale efforts b...Not quite, but nice try!<br />You gotta scale efforts by 100x to claim Yaeg [Yet another EG] status:)<br /><br />My two satoshis:<br />A more insightful and relevant take for a Yaeg would<br />have come, timewise (January 10th), in terms of celebrating Don Knuth's work. Don turned 84!<br /><br />In particular, the use case of food/beverage items<br />in Graham/Knuth/Patashnik [GKP] is intriguing.<br />***<br />Eggs::Setting<br />Combinatorial interpretation for proving identity<br /><br />For proving the addition formula for binomial coefficients<br /><br />\binom{r}{k} = \binom{r-1}{k} + \binom{r-1}{k-1}, <br />where k is an integer and r is r is a positive integer.<br /><br />....<br />If we have a set of r eggs that includes exactly one bad egg, there are \binom{r}{k} ways to select k of the eggs. So, nothing but the good eggs can be selected in exactly \binom{r-1}{k} ways, etc ...<br /><br />****<br /><br />More interesting, the Solera/Wine problem.<br />Setting:: generating functions. <br />Exam problem 45, on page 433 in [GKP].<br />This problem appeared in Don's 1985 final! <br />(I wonder who was part of that class watching this. Most of the new readership wasn't even alive.)<br /><br />***<br /><br />Cheese:: Setting: Recurrences.<br />How many pieces of cheese can you obtain from a single thick piece by making five straight slices? Find a recurrence relation for P_n, the max number of 3-D regions defined by n different planes.<br /><br />***<br /><br />Pizza: Slicing:: Recurrences<br />(obvious)<br />****<br /><br /><br /><br /><br /><br />EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25693371993119431142022-01-10T19:06:16.935-06:002022-01-10T19:06:16.935-06:00Though it is a much easier problem than your examp...Though it is a much easier problem than your examples, the "wheat and chessboard problem" has its own Wikipedia page.<br /><br />The ham sandwich theorem in two dimensions is sometimes called the pancake theorem.<br /><br />Kakutani proved that for any compact convex set S in three dimensions, there exists a circumscribed cube, all of whose faces touch S. The first person I heard this from (can't remember who it was) said that Kakutani's theorem was sometimes informally referred to as the hotdog theorem, because it's maybe not immediately obvious that the theorem is true when S is hotdog-shaped. But I don't know of a published reference to Kakutani's theorem as "the hotdog theorem."Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11029059710003399992022-01-10T15:38:14.125-06:002022-01-10T15:38:14.125-06:00Then of course there is the diet problem in linear...Then of course there is the diet problem in linear programming: https://neos-guide.org/content/diet-problemAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51814491383628508412022-01-10T14:03:49.472-06:002022-01-10T14:03:49.472-06:00Lewis and Rieman wrote of HCI, "It just won&#...Lewis and Rieman wrote of HCI, "It just won't work to build a complete system and then, in the final stages of development, spread the interface over it like peanut butter."Yet another EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92120858466615369502022-01-10T09:54:09.171-06:002022-01-10T09:54:09.171-06:00You raise an excellent point- some theorems are ab...You raise an excellent point- some theorems are about eating or drinking but the food itself is unspecified. Definitely counts!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9095027405287128802022-01-10T04:54:59.990-06:002022-01-10T04:54:59.990-06:00The dining philosophers also involve food (admitte...The dining philosophers also involve food (admittedty no concrete one).Rolandhttp://rolandglueck.de/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53631837217409091612022-01-10T01:06:32.782-06:002022-01-10T01:06:32.782-06:00Spicy Chickens https://arxiv.org/abs/1306.2741Spicy Chickens https://arxiv.org/abs/1306.2741Anonymousnoreply@blogger.com