January 2009 - mathfun@mailman.xmission.com

Re: [math-fun] more muffin problem results
by Michael Reid 20 Jan '09

20 Jan '09

> > > 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 > > > > ouch! i can't manage anything with this one yet ... > > double ouch!! the combinatorics here seem to be a bit involved. > however, i can improve this to T(13, 23) >= 53/2990 with the partition > 2 * [3 * 53/2990 + 71/2990] + 2 * [2 * 53/2990 + 59/2990 + 1/46] + > 2 * [2 * 107/5980 + 27/1495 + 3/130] + [2 * 27/1495 + 2 * 61/2990] + > 4 * [38/1495 + 2 * 77/2990] + 2 * [2 * 153/5980 + 77/2990] > <---> > 10 * [53/2990 + 77/2990] + 4 * [107/5980 + 153/5980] + > 4 * [27/1495 + 38/1495] + 2 * [59/2990 + 71/2990] + > 2 * [61/2990 + 3/130] + [2 * 1/46] . okay, i can now prove that T(13, 23) = 53/2990 . this is the most involved case i've done, but it becomes much easier after finding the right way to organize things. the partition above establishes the lower bound. now suppose we have a partition with all parts >= 53/2990 . if any 1/23 is split into 3 or more parts, then the smallest is <= 1/69 , which is too small. since at least one 1/23 is split, there is no loss in generality in assuming that they are all split (by halving them, if necessary). thus there are 46 parts in total. if some 1/13 is split into 5 or more parts, then the smallest is <= 1/65 , which is too small. if some 1/13 is split into 2 parts, then the larger is >= 1/26 , so its "complement" in a 1/23 is <= 3/598 , which is too small. thus each 1/13 is split into either 3 or 4 parts. we now see that 7 of the 1/13 's are split into 4 parts, and the other 6 are split into 3 parts. we now consider how the parts pair up to form 1/23 's. of the 28 parts in the former 7 1/13 's, at most 18 can pair with a part in the latter 1/13 's, so there must be at least 5 pairs among these 28 parts. suppose that a subset of A of the former 1/13 's contains B pairs. the 4A parts sum to A/13 , and they contain 2B parts that sum to B/23 , so the other 4A - 2B parts sum to A/13 - B/23 = (23A - 13B)/299 . since each part is >= 53/2990 , we have (23A - 13B)/299 >= (53/2990)(4A - 2B) , which is equivalent to the inequality B <= 3A/4 . in particular, for A = 7 , which means all of the former 1/13 's, there are at most 5 pairs, so there must be exactly 5 pairs. now we claim that we can split these 7 1/13 's into two subsets so that none of the 5 pairs are separated. indeed, consider the graph on 7 vertices, corresponding to the 1/13 's, with an edge between two vertices if they contain parts that are paired with each other. since there are (at most) 5 edges, the graph is not connected. this proves the claim. now we see for various values of A , how many pairs a set of A 1/13 's can contain: A max. number of pairs = floor(3A/4) 1 0 2 1 3 2 4 3 5 3 6 4 we see that the only way to have two disjoint subsets that comprise all 7 1/13 's, and contain a total of 5 pairs, is one subset of 3 1/13 's having 2 pairs, and the other subset being the remaining 4 1/13 's , containing 3 pairs. finally, these 4 1/13 's have 16 parts summing to 4/13 , with the 6 parts in the 3 pairs summing to 3/23 . the remaining 10 parts sum to 4/13 - 3/23 = 53/299 , so the smallest of these is <= 53/2990 . this proves that T(13, 23) = 53/2990 . by way of contrast, it is quite easy to show that T(11, 19) = 9/418 . (this is another of scott's cases; i'm not sure if he claimed this was the optimal value, or just a lower bound.) if some 1/19 is split into 3 or more parts, the smallest is <= 1/57 , which is too small. some 1/19 must be split, so we may assume that all split. therefore, each 1/19 splits into exactly 2 parts, so there are 38 parts in total. is some 1/11 splits into 5 or more parts, the smallest is <= 1/55 , which is too small. if some 1/11 splits into 2 parts, the largest is >= 1/22 , so its complement in a 1/19 is <= 3/418 , which is too small. thus each 1/11 splits into either 3 or 4 parts, and there are 5 that split into 4 parts, and 6 that split into 3 parts. of the 20 parts in these former 1/11 's, at least 2 must pair up in the same 1/19 . the larger of these is >= 1/38 , so the other 3 parts in the same 1/11 sum to at most 1/11 - 1/38 = 27/418 . therefore the smallest of these 3 is <= 9/418 . this shows that T(11, 19) <= 9/418 . can we attain this value? well, the argument shows how to start. let me illustrate the parts by this array: * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * where the columns correspond to the parts in the same 1/11 . now label the two parts in the left hand side that are "complements". they must be equal, and for each, the other three parts in the same 1/11 must be equal. thus we have a a * * * * * * * * * b b * * * * * * * * * b b * * * * * * * * * b b * * * and the complements of the b 's must occur on the right hand side. now let's make the remaining 12 parts on the left hand side equal; we get a a c c c * * * * * * b b c c c * * * * * * b b c c c * * * * * * b b c c c which forces the "complements" of the c 's to occur on the right hand side. there is still the task to organize the parts on the right hand side so that the columns each add to 1/11 . however, this is trivial! those parts come in half-dozens, 6 complements of b , call them d , and 12 complements of c , call them e , so put one d and two e 's in each column: a a c c c d d d d d d b b c c c e e e e e e b b c c c e e e e e e b b c c c where a = 1/38 , b = (1/11 - a)/3 = 9/418 , c = (1/11)/4 = 1/44 , d = 1/19 - b = 13/418 and e = 1/19 - c = 25/836 . (this seems to be different from scott's partition.) note also that all the parts are large enough; if not, the upper bound argument wouldn't be strong enough, but this would show exactly where to look for a better bound. mike

2 3

[math-fun] Encoding sorted lists with duplicates
by Steve Witham 20 Jan '09

20 Jan '09

Doh! >I have a sorted list of n integers, that may contain >duplicates, in the range 0..(m-1). >How many possible such lists are there given n and m? Changing to a more standard notation, that's r out of n with repetitions allowed. Following Tom Rokicki's nudge, I did use my brain and got it mostly right before using the web. A page written at my fifth-grade level http://www.mathsisfun.com/combinatorics/combinations-permutations.html uses a mnemonic that I like: walking & picking from a row of bins. Anyway, this is leading up to more of a puzzle: I have a sorted list of r numbers from the integers { 0 .. n-1 }. I can encode the set using differences. For instance 3, 5, 5, 1024, 1025, 6000 --> 3, 2, 0, 1019, 1, 4975 These numbers say how many bins I skip over before taking each thing. The total of the differences will be < n. Invent a binary prefix code (means a distinct string of whole bits for each codeword) to further encode these differences, knowing r (how many there will be) and n (the limit on their total). The goal is to minimize the maximum size of the string of r codewords. Not to try for a smaller total than that, nor to worry about the size of individual codewords per se. Yet, the job is to design, given r and n, a single code to apply to all the differences individually. Then compare to the information-theoretical size: ( r + n - 1 )! log ( -------------- ) 2 r! ( n - 1 )! --Steve

1 0

Re: [math-fun] Estimating Inauguration crowds
by Dan Asimov 19 Jan '09

19 Jan '09

Please just post the links in the future. I hate to waste that many electrons for nothing. --Dan << FYI -- 3 takes on estimating the crowd size at the Inauguration >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Estimating Inauguration crowds
by Henry Baker 19 Jan '09

19 Jan '09

FYI -- 3 takes on estimating the crowd size at the Inauguration http://online.wsj.com/article/SB123145851449666169.html THE NUMBERS GUY JANUARY 9, 2009 The Madness of Estimating Crowds and Commodes Inauguration Turnout of People and Port-a-Potties Could be a Record, But No One Knows; Keep Off My 5 Square Feet By CARL BIALIK See Corrections & Amplifications below How many people will come to the inauguration? And where will they go when they have to, you know, go? President-elect Barack Obama is expected by many to set a record on Jan. 20 for number of people attending a presidential inauguration. But setting a new record requires knowing the old record and producing a new estimate that tops it. And crowd-counting in Washington, D.C., these days is a political hot potato. After high-profile numerical disputes, no government agency is eager to put its name to a specific number -- even though projecting crowd sizes is crucial for planning for an event of such massive proportions. For one thing, just consider their bathroom needs. Two weeks after Mr. Obama's election, Washington Mayor Adrian M. Fenty said up to four million people could attend, citing briefings from federal and local officials. Now a mayor's spokesman says, "we simply do not know." Representatives for the Secret Service, the U.S. Park Police, the National Park Service, the Washington, D.C., police and the Capitol police all declined to predict crowd sizes -- at least publicly. A Secret Service threat assessment obtained by The Wall Street Journal predicted a crowd of between 1.5 million and two million. Several people attribute the numbers reticence in the capital to the controversy about the Louis Farrakhan-organized Million Man March in 1995. The Park Police estimated crowd size at 400,000, and Mr. Farrakhan, who projected a crowd four to five times as large, threatened to sue. "Because people got upset about the Million Man March, Congress directed that we not provide crowd-size estimates," William Line, spokesman for the National Park Service, says. For much of the 20th century, the local police department provided reporters with numbers. They were the source for contemporary reports that Lyndon Johnson attracted a crowd of 1.2 million in 1965, which is now considered the record. The police apparently stopped counting publicly in the 1990s, though the press did report a police estimate of up to 150,000 people lining the parade route for President George W. Bush's second inaugural, in 2005. A police spokeswoman says she doesn't know who made that estimate, nor how earlier counts were arrived at. Betty Sue Flowers, director of the Johnson library in Austin, Texas, doesn't know, either. She notes that Johnson won the 1964 election by 23 percentage points and was riding a wave of popular support for passing the Civil Rights Act that year. Not everyone agrees on the Johnson inaugural number. In 1965, Ebony Magazine reported nearly a million people lined the parade route, attributing some of the excitement to "the first total integration of a Presidential Inauguration." Some recent news articles have figured Johnson's record crowd at 1.5 million. But to inaugural historians, the numbers are little better than guesswork. "I doubt if the numbers are particularly accurate," says Jerry Wallace, who served as a historian and archivist for three inaugural committees. "Any estimate before 1975 is probably a wild guess," according to a 2004 article published in an American Sociological Association magazine by sociologists Clark McPhail and John McCarthy. After that date, crowd counters started employing more scientific means, estimating the area covered and the average area taken up by each attendee. "I have absolutely no idea how they estimate these crowds," adds Jim Bendat, a Los Angeles County public defender and author of a history of inaugurations that states, "More than a million spectators line the streets of Washington." Mr. Bendat explains that "the publisher just threw a number out." Before the 20th century, thousands qualified as large crowds. It was only in the last century that massive crowds became the norm, spurred by advances in transportation and in audio amplification. Warren G. Harding's inaugural address in 1921 was the first to be projected to the crowd by a microphone, says Paul Boller, inaugural historian and professor emeritus at Texas Christian University. It may not have helped much; the New York Times called the crowd "small" and "strangely apathetic," despite "a new voice magnifying device." Adds Mr. Boller, referring to Mr. Harding's address, "Some people said afterwards, it's too bad they invented the microphone." Even without official numbers, it's possible to make a back-of-the-envelope calculation based on the spread of attendees and the area they cover. Five square feet per standing person is a typical reference point, according to Dr. McPhail and Dr. McCarthy. Dr. McPhail estimates that, at that density, the available space for Mr. Obama's inauguration will accommodate under a million people -- with room for a few hundred thousand more at the Lincoln Memorial grounds. The Capitol Police spokeswoman says that a packed west front of the capitol can accommodate 240,000 to 260,000 people. Considering the vagaries of counting crowds once they materialize, it's even tougher to project them in advance. Just one unpredictable factor, weather, can derail the best-laid plans. In 1873, when the inauguration was held in March, 100 canaries meant to inject opulence into Ulysses S. Grant's inaugural ball froze to death, and champagne turned to slush, according to Mr. Bendat. And in 1985, decades after the inauguration had been moved up to January, record-low temperatures forced the cancellation of Reagan's second inaugural parade. Projections matter, even though organizers can't expand the space available along the Pennsylvania Avenue parade route, nor build out capacity on the Mall. For one thing, the more people attending, the more portable toilets needed. The Park Service recommends, but doesn't require, one portable toilet for every 300 people. The portable-toilet industry, perhaps not surprisingly, suggests more are needed. Millicent Carroll, director of industry and regulatory standards for Portable Sanitation Association International, says 7,500 would be needed to accommodate a crowd of one million. Despite the industry's bias, independent, and rough, calculations suggest that number may be low, if anything. A Washington state Department of Transportation study of rest-area restrooms conducted in 1987, in part by then-Cornell undergraduate Anh Tran, found that men spent an average of 47 seconds in stalls, and women 79 seconds, for an average of about a minute. (It's unclear how the presence of a researcher with a stopwatch affected the unwitting study participants. "I was really subtle," Ms. Tran says.) And University of New Mexico urologist Anthony Smith says a typical person urinates up to eight times per day -- more when it's cold outside. So figure on spending a minute once every three hours, or 1/180th of your time, in a portable toilet. Assume an average crowd size of one million people over the duration of the event, and you'd need more than 5,000 portable toilets. And that means they'd be used constantly; uneven demand would produce massive lines. If about twice as much time is needed per person, Old Dominion University's Lawrence Weinstein, a physicist, and John Adam, a mathematician, co-authors of "Guesstimation," guess that 10,000 toilets will be needed. "Since the usage will be randomly distributed (and hence with periods of both under- and over-utilization), it will be much safer to have three times that number," Prof. Weinstein says. One toilet for every 100 people is conservative, compared with other standards. The New York City Marathon last November had one toilet for every 17 runners. The U.S. Army's standard is one commode for every 25 males and one for every 17 females, according to Albin Majewski of the Army's material systems directorate. And the International Code Council requires one toilet for every 40 people at nightclubs, and more than one for every 50 people in an office building. The Presidential Inaugural Committee plans on having 5,000 portable toilets. Its spokeswoman, Linda Douglass, says the committee is working "to ensure that all attendees have adequate facilities and that parks resources are respected." Ms. Carroll, of the portable-toilets trade group, is skeptical, predicting insufficient toilets and incidents of people going where they shouldn't. "It's going to be an ugly scene," she says. "There really aren't enough units out there." Read Carl Bialik's daily commentary about numbers at the free blog, WSJ.com/NumbersGuy. Email him at numbersguy(a)wsj.com. Corrections & Amplifications The estimated size of the crowd at Dwight Eisenhower's inaugural ceremony in 1957 was 750,000 people. A graphic that ran with this column on Jan. 9 labeled the figure as 750 ------------- http://wbir.gns.gannettonline.com/apps/pbcs.dll/article?AID=/20090119/OBAMA… Crowd count could hinge on high-tech balloon It could be up to a high-tech balloon to calculate how many people show up Tuesday on the National Mall to witness President-elect Barack Obama's historic swearing-in ceremony. LARRY WHEELER, Gannett News Service WASHINGTON Â It could be up to a high-tech balloon to calculate how many people show up Tuesday on the National Mall to witness President-elect Barack Obama's historic swearing-in ceremony. A tethered balloon, equipped with high-definition digital cameras and a fiber-optic ground connection, will snap images of the gathering crowd from nearly 800 feet above the Capitol building. "We can see all the way to the steps of the Lincoln Memorial," said President Curt Westergard of Digital Design & Imaging Service, the Falls Church, Va., company that owns and operates the balloon. The aerial images will be transmitted to Steve Doig, chairman of Arizona State University's journalism school. Doig will use computer software to analyze the photographs and estimate crowd size. The real trick will be estimating the density of the crowd in various locations, Doig said. "You can double the crowd-size estimates just by saying, 'I'll divide by 10 instead of five,"' said Doig, who used similar technology to estimate crowd sizes for the Miami Herald during Pope John Paul II's visit there in 1987. For security reasons, Secret Service and Federal Aviation Administration officials have ordered the balloon brought down by 10 a.m., Westergard said. So the best it can offer is a snapshot of the crowd two hours before the inauguration's climax. Still, the aerial camera may be the best hope for anyone interested in a head count for the 56th presidential inauguration. The Park Service, which had produced official crowd counts for National Mall events, was barred by Congress from continuing the practice after a controversy erupted over the agency's estimate of attendance at the Nation of Islam's Million Man March in 1995. When announcing Monday that it would count the crowd at Tuesday's inauguration, official said that there was discussion in the agency whether then ban was forever or just one year. No other law enforcement or government group has stepped forward to fill the void, leaving crowd estimates to the educated guesses of experts and media speculation. According to several crowd-counting experts, the broad, 2.1-mile lawn stretching from the west Capitol steps to the Lincoln Memorial can host as many as 2 million people. While the balloon's camera snaps away, another company will try to photograph the Mall from a much higher vantage point Â outer space. If successful, it will be the first high-resolution commercial color image of an inaugural event taken from space, said Mark Brender, a spokesman for GeoEye, the Dulles, Va., company that owns and operates two commercial imaging satellites. The company's IKONOS and GeoEye-1 satellites will snap images of the Mall at 10:33 a.m. and 11:19 a.m. respectively Tuesday. Both satellites orbit roughly 423 miles above Earth's surface at 17,000 miles per hour. The newer, more capable GeoEye-1 will be closer Â about 199 miles west of Washington. IKONOS will be over the Atlantic Ocean, about 435 miles east of the nation's capital, Brender said. The GeoEye-1 can pick out objects as small as 19 inches across, roughly the size of a baseball field's home plate. IKONOS has slightly less resolution, Brender said. Forecasters are calling for partly cloudy skies Tuesday. "Hopefully there will be a donut hole over the nation's capital so we can see the ground," Brender said. Contact Larry Wheeler at lwheeler(a)gns.gannett.com. Published: January 19. 2009 9:03PM --------- http://www.washingtonpost.com/wp-dyn/content/article/2008/12/21/AR200812210… Inauguration Day Crowd Estimate Reduced by Half By Mary Beth Sheridan Washington Post Staff Writer Monday, December 22, 2008; A01 Officials are casting doubt on an early projection that 4 million to 5 million people could jam downtown Washington on Inauguration Day, saying it is more likely that the crowd will be about half that size. D.C. authorities said the earlier estimates, provided by Mayor Adrian M. Fenty (D), were based on speculation surrounding the historic nature of the swearing-in of Barack Obama as the nation's first African American president. After weeks of checking with charter bus companies, airlines and other sources, they're reassessing. "It's more of an art than a science," City Administrator Dan Tangherlini said. "The fact is, earlier it was speculation. Now we're beginning to flesh it out and what the physical capacities of the system are." The Secret Service has dismissed the high-end estimates of 4 million to 5 million people. But there is universal agreement among security officials and planners that massive numbers of people will flock to the swearing-in of Obama (D), who had drawn huge campaign crowds. Turnout could easily reach 2 million, officials said, far outstripping the 400,000 who attended the 2005 inauguration of President Bush. Although it is possible that 5 million people will descend on the area in the days leading up to the inauguration, it appears unlikely that trains and local roads could get them all to the Mall and parade route Jan. 20, officials said. Jawauna Greene, a spokeswoman for the Maryland Transit Administration, said that inaugural planning committees had initially considered up to 6 million attendees. Lately, she said, D.C. officials had scaled back their estimates to about 2 million. "But there's no telling," she said. Del. Eleanor Holmes Norton (D-D.C.) said the most recent estimates she has gotten from the Presidential Inaugural Committee and federal and local officials project between 1.5 million and 3 million people. In an interview, Tangherlini said the initial estimates were rather crude, but he would not discuss the latest projections. Early on, some officials looked at simply how many people could squeeze onto the Mall. (About 3 million, Tangherlini said.) Officials also reasoned that "this thing could be two, three, four times bigger than what we normally see," Tangherlini said. "And they took 'normally see' to be Lyndon B. Johnson's inauguration," which drew a record 1.2 million people in 1965. With a lack of solid information -- the Secret Service and the Presidential Inaugural Committee declined to make their estimates public -- colossal numbers continue to be bandied about. Maj. Gen. Errol R. Schwartz, head of the D.C. National Guard, said at a news conference Thursday that the crowd estimate was 4 million. His source? "That is the number I have heard on the television," he said. The D.C. government recently conducted a telephone and Internet survey of charter bus companies east of the Mississippi River, which concluded that about half of their 23,000 vehicles are booked for the inauguration, Tangherlini said. Estimated number of passengers: 500,000. In addition, Metro trains are expected to be packed. They can carry about 1.2 million people to the inauguration if all goes well, Tangherlini said. Metro will be running rush-hour train service and expects to offer frequent shuttles on special bus-only lanes for residents and visitors. "I'm at 1.7 million already," Tangherlini said, counting the Metro and charter bus passengers. "And I haven't included walkers, drivers, railroaders, Greyhounders, people who already live here." Not to mention airline passengers. Well more than 400,000 people could fly into the Washington region's three main airports in the days before the inauguration, according to airline figures. Dulles International and Reagan National airports could receive about 300,000 passengers between Jan. 16 and 19, if all scheduled flights are full, said Rob Yingling of the Metropolitan Washington Airports Authority, citing figures from the Official Airline Guide. Officials at Baltimore-Washington International Marshall Airport said they had no estimates on inauguration travelers. But about 30,000 people fly into BWI on an average day, and nearly 40,000 fly in daily during holiday periods, said Jonathan O. Dean, communications manager for the Maryland Aviation Administration. "Flights under existing schedules are near capacity," said David Castelveter of the Air Transport Association. He said airlines are planning to add about 100 incoming and outgoing flights at the three airports from Jan. 15 to 22, which could carry about 5,000 extra people on round trips. And some airlines will use larger-than-usual planes on scheduled runs. However, those numbers can't simply be added to the 1.7 million figure for Metro and charter buses, since many airline passengers might ride Metro to the inauguration. And of course, not every air traveler will attend the festivities. MARC and Virginia Railway Express commuter trains have a firmer number: They plan to carry about 50,000 people to Washington on the morning of Jan. 20 on reservation-only trains. As for Amtrak, reservations for the inaugural period have soared, spokeswoman Karina Romero said. But calculating the total arriving is difficult. Overall, 44,562 tickets have been reserved on lines that serve Washington during inauguration week, she said. But that includes trips to and from Washington, as well as a small number of passengers who will disembark in other cities, including New York. Trains aren't sold out. And Amtrak might expand service. "It's a moving target," Romero said. Tangherlini offered a rough estimate of 75,000 Amtrak passengers. Officials said that, despite their best efforts, many factors are difficult to calculate. One is the number of people driving to the city in the days before the inauguration. John Townsend, public affairs manager for AAA in the D.C. region, said about three-quarters of tourists visiting Washington typically arrive by car. He wouldn't hazard a guess as to how many would get behind the wheel for the Obama inauguration. "We think it's going to be a massive gridlock," he said. Intercity bus companies said most of their ticket sales are last-minute, making it difficult to project how many passengers they will transport to Washington. "We have data for Thanksgiving we collect from year to year, so we can make projections. . . . This, we don't have anything to go on," said Bob Schwarz, executive vice president of Peter Pan Bus Lines. He said that the company's 55 charter buses had been reserved to take groups to the inauguration. "This is a phenomenon we've never seen," he said. City officials are trying to estimate how many churches and schools might use their own buses to carry Obama supporters to Washington. And the temperature could be a critical factor: A mild day could bring out tens of thousands of local residents, and snow, rain or bitter cold would be likely to discourage crowds. "Our biggest collective unknown is the weather," Tangherlini said. Finally, some of those who originally planned to attend the inauguration might be dissuaded by the predictions of traffic chaos. Residents of Baltimore and Philadelphia might decide to catch a glimpse of Obama at recently announced events in those cities in the run-up to the inauguration rather than trek to the nation's capital. Because of the variables, officials said, they have to be ready to handle a far larger crowd than might materialize. Chris Geldart, who heads the D.C. area office for the Department of Homeland Security, said he thought turnout would probably be 1.5 million to 2 million, "because it's winter, and people getting in and out is going to be difficult." "But, hey, we may see up to 4 million," he said. "So we'd better be prepared." In the end, officials might never know how many people turn out. The U.S. Park Police have been barred from providing crowd estimates since they were threatened with a lawsuit for an apparent undercount at the Million Man March in 1995. Sal Lauro, acting assistant chief of the Park Police, declined to give a number of how many people could fit on the Mall, which his agency guards. "I try not to even look at that," he said. Â© 2008 The Washington Post Company

1 0

Re: [math-fun] Sorted lists with duplicates
by Tom Rokicki 19 Jan '09

19 Jan '09

Think about it a bit; you'll see the answer is not substantially different between the problems. On Mon, Jan 19, 2009 at 12:40 PM, Steve Witham <sw(a)tiac.net> wrote: > I have a sorted list of n integers, that may contain > duplicates, in the range 0..(m-1). > How many possible such lists are there given n and m? > The possibility of duplicates makes it different from > "n out of m," right? > > If you add a 0 to the front of the list, then take > differences between successive numbers, the question > becomes, How many lists of n ints between 0 and m-1 > are there that add up to < m? > > --Steve > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > -- Check out Golly at http://golly.sf.net/

1 0

[math-fun] Sorted lists with duplicates
by Steve Witham 19 Jan '09

19 Jan '09

I have a sorted list of n integers, that may contain duplicates, in the range 0..(m-1). How many possible such lists are there given n and m? The possibility of duplicates makes it different from "n out of m," right? If you add a 0 to the front of the list, then take differences between successive numbers, the question becomes, How many lists of n ints between 0 and m-1 are there that add up to < m? --Steve

1 0

Re: [math-fun] more muffin problem results
by Michael Reid 19 Jan '09

19 Jan '09

> > 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 > > ouch! i can't manage anything with this one yet ... double ouch!! the combinatorics here seem to be a bit involved. however, i can improve this to T(13, 23) >= 53/2990 with the partition 2 * [3 * 53/2990 + 71/2990] + 2 * [2 * 53/2990 + 59/2990 + 1/46] + 2 * [2 * 107/5980 + 27/1495 + 3/130] + [2 * 27/1495 + 2 * 61/2990] + 4 * [38/1495 + 2 * 77/2990] + 2 * [2 * 153/5980 + 77/2990] <---> 10 * [53/2990 + 77/2990] + 4 * [107/5980 + 153/5980] + 4 * [27/1495 + 38/1495] + 2 * [59/2990 + 71/2990] + 2 * [61/2990 + 3/130] + [2 * 1/46] . no guarantee that this is best possible. i also briefly looked into the 3-parameter case. recall my notation is T(m, n, p) = maximum c for which there is a partition of 1 with all parts >= c , and which is a refinement of 1/m + 1/m + ... + 1/m = 1 , and of 1/n + 1/n + ... + 1/n = 1 and 1/p + 1/p + ... + 1/p = 1 . i think i checked all the possibilities to show that T(3, 4, 5) = 1/15 . the analysis is similar to the 2-parameter case to find the different types of splitting of individual fractions, but there are many different ways the parts can be redistributed in the other splittings. this was the bulk of the analysis. by way of contrast, it was much easier to prove that T(3, 5, 7) = 1/21 . partitions and proofs left to the interested reader. mike

1 0

Re: [math-fun] more muffin problem results
by Michael Reid 18 Jan '09

18 Jan '09

trying to confirm scott's data ... > 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) confirmed. i can prove that T(5, 7) = 1/21 , and an optimal partition must have a part >= 8/105 . this seems to be the smallest case where one of the smaller fractions must be split into 3 parts. > 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 i can prove that T(7, 10) = 1/30 , which confirms your value of S . however, i can improve the ratio to 23/14 with the partition 3 * [1/30 + 2 * 23/420] + 3 * [2 * 19/420 + 11/210] + [3 * 1/21] <---> [3 * 1/30] + 6 * [19/420 + 23/420] + 3 * [1/21 + 11/210] . this is probably the smallest max/min ratio. > 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 i think i can prove that T(10, 11) = 7/220 , which improves your value of S . in any event, that's a lower bound, obtained by the partition 2 * [2 * 7/220 + 2/55] + 4 * [9/220 + 13/220] + 2 * [1/22 + 3/55] + 2 * [2 * 1/20] <---> 4 * [7/220 + 13/220] + 2 * [2/55 + 3/55] + 4 * [9/220 + 1/20] + [2 * 1/22] . > 12/7: pieces 3..4: 3.4*12; 3.3.3.3*3, 4.4.4*4 S = 3/7, R_U = 4/3 confirmed. i can prove that T(7, 12) = 1/28 , and the optimal partition is unique. this generalizes to T(2n+1, n(n+1)) = 1/((n+1)(2n+1)) , with unique optimal partition n * [(n+1) * 1/((n+1)(2n+1))] + (n+1) * [n * 1/(n(2n+1))] <---> n(n+1) * [1/((n+1)(2n+1)) + 1/(n(2n+1))] . > 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 confirmed. i can prove that T(5, 9) = 2/45 , and an optimal partition must have a part >= 1/15 , which shows that your ratio is best possible. > 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 confirmed. i can prove that T(9, 16) = 11/432 , and an optimal partition must have a part >= 1/27 , which shows that your ratio is best possible. > 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 ouch! i can't manage anything with this one yet ... > 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 confirmed. T(4, 7) = 5/84 , and the optimal partition is unique. > 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 confirmed. i can prove that T(9, 17) = 10/459 , and an optimal partition must have a part >= 1/27 , which shows that your ratio is best possible. mike

2 1

Re: [math-fun] muffin problem
by Dan Asimov 17 Jan '09

17 Jan '09

The muffin problem is fascinatingly both simple to ask and hard to solve. In spirit it reminds me of the Egyptian Fraction Problem, to not only represent the arbitrary p/q > 0 as a sum of distinct integer reciprocals (i.e., an Egyptian fraction), but to do so such that the largest denominator used is minimum. ((( It's well known that the greedy algorithm is not the way to solve this. E.g. -- as found in Wikipedia -- greedily: 5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225, but altruistically: 5/121 = 1/33 + 1/121 + 1/363. ))) QUESTION: Is there an algorithm for solving this minimization problem? As with the muffin problem there is also the question here of which decomposition uses the fewest summands. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

3 2

Re: [math-fun] muffin problem
by Michael Reid 17 Jan '09

17 Jan '09

> > 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) . > > apparently U(3,3n) = 3 and U(3,3n +/- 1) = (3n-1)/2n. > > this translates to T(3,3n) = 1/3n, T(3,3n-1) = 1/6n, and T(3,3n+1) = > (3n-1)/6n(n+1). there's a typo in your formula for T(3, 3n+1) , but other than that, i have the same formula, and now, a proof. it was just a matter of finding the right simplifying device. T(3, 1) = T(1, 3) = 1/3 , which is trivial. T(3, 3n) = 1/(3n) , which is also trivial. T(3, 3n+1) = (3n-1)/(6n(3n+1)) , for n >= 1 , with partition 2 * [n * (3n-1)/(6n(3n+1)) + (n+1) * 1/(6n+2)] + [2n * 1/(6n)] <---> 2n * [(3n-1)/(6n(3n+1)) + 1/(6n)] + (n+1) * [1/(6n+2) + 1/(6n+2)] T(3, 3n+2) = 1/(6n+6) , with partition [(2n+2) * 1/(6n+6)] + 2 * [n * 1/(6n+4) + (n+1) * (3n+4)/(6(n+1)(3n+2))] <---> (2n+2) * [1/(6n+6) + (3n+4)/(6(n+1)(3n+2))] + n * [1/(6n+4) + 1/(6n+4)] T(3, 3n+1): the case when n = 1 is easily to handle separately, so here i'll assume that n > 1 . if some 1/(3n+1) is split into 3 or more parts, then the smallest of these parts is <= 1/(9n+3) , which is too small. here we use that n > 1 . at least one 1/(3n+1) must be split, because 1/3 is not an integer multiple of 1/(3n+1) . therefore we have some part <= 1/(6n+2) . if any 1/(3n+1) is not split, then there is no loss in generality in halving it, because it does not decrease the smallest part size. it might be the case that the two parts go to the same 1/3 , but that's not an issue for us. therefore we may assume that every 1/(3n+1) is split into exactly 2 parts, and thus there are exactly 6n+2 parts in total. therefore, some 1/3 is split into at most 2n parts, so the largest of these is >= 1/(6n) , and its "complement" in a 1/(3n+1) has size <= 1/(3n+1) - 1/(6n) = (3n-1)/(6n(3n+1)) . T(3, 3n+2): the case when n = 0 is easily to handle separately, so here i'll assume that n >= 1 . if some 1/(3n+2) is split into 3 or more parts, then the smallest of these parts is <= 1/(9n+6) , which is too small (for n >= 1 ). at least one 1/(3n+2) must be split, because 1/3 is not an integer multiple of 1/(3n+2) . therefore we have some part <= 1/(6n+4) . as before, if any 1/(3n+2) is not split, then there is no loss in generality in halving it. therefore we may assume that every 1/(3n+2) is split into exactly 2 parts, and thus there are exactly 6n+4 parts in total. now one of the 1/3 's must be split into at least 2n+2 parts, so the smallest of these is <= 1/(6n+6) . mike

1 0