Chapter 16 Counting 16.1 Why Count? Are there two different subsets of the ninety 25-digit numbers shown below that have the same sum —for example, maybe the sum of the numbers in the first col-umn is equal to the sum of the numbers in the second column? 0020480135385502964448038 5763257331083479647409398 0489445991866915676240992 5800949123548989122628663 1082662032430379651370981 6042900801199280218026001 1178480894769706178994993 6116171789137737896701405 1253127351683239693851327 6144868973001582369723512 1301505129234077811069011 6247314593851169234746152 1311567111143866433882194 6814428944266874963488274 1470029452721203587686214 6870852945543886849147881 1578271047286257499433886 6914955508120950093732397 1638243921852176243192354 6949632451365987152423541 1763580219131985963102365 7128211143613619828415650 1826227795601842231029694 7173920083651862307925394 1843971862675102037201420 7215654874211755676220587 2396951193722134526177237 7256932847164391040233050 2781394568268599801096354 7332822657075235431620317 2796605196713610405408019 7426441829541573444964139 2931016394761975263190347 7632198126531809327186321 2933458058294405155197296 7712154432211912882310511 3075514410490975920315348 3171004832173501394113017 8247331000042995311646021 3208234421597368647019265 8496243997123475922766310 3437254656355157864869113 8518399140676002660747477 3574883393058653923711365 8543691283470191452333763 3644909946040480189969149 8675309258374137092461352 3790044132737084094417246 8694321112363996867296665 3870332127437971355322815 8772321203608477245851154 4080505804577801451363100 8791422161722582546341091 4167283461025702348124920 9062628024592126283973285 4235996831123777788211249 9137845566925526349897794 4670939445749439042111220 9153762966803189291934419 4815379351865384279613427 9270880194077636406984249 4837052948212922604442190 9324301480722103490379204 5106389423855018550671530 9436090832146695147140581 5142368192004769218069910 9475308159734538249013238 5181234096130144084041856 9492376623917486974923202 5198267398125617994391348 9511972558779880288252979 5317592940316231219758372 9602413424619187112552264 5384358126771794128356947 331332 CHAPTER 16. COUNTING 7858918664240262356610010 9631217114906129219461111 8149436716871371161932035 3157693105325111284321993 3111474985252793452860017 5439211712248901995423441 7898156786763212963178679 9908189853102753335981319 3145621587936120118438701 5610379826092838192760458 8147591017037573337848616 9913237476341764299813987 3148901255628881103198549 5632317555465228677676044 5692168374637019617423712 8176063831682536571306791 Finding two subsets with the same sum may seem like an silly puzzle, but solving problems like this turns out to be useful, for example in finding good ways to fit packages into shipping containers and in decoding secret messages. The answer to the question turns out to be “yes.” Of course this would be easy to confirm just by showing two subsets with the same sum, but that turns out to be kind of hard to do. So before we put a lot of effort into finding such a pair, it would be nice to be sure there were some. Fortunately, it is very easy to see why there is such a pair —or at least it will be easy once we have developed a few simple rules for counting things. The Contest to Find Two Sets with the Same Sum One term, Eric Lehman, a 6.042 instructor who contributed to many parts of this book, offered a $100 prize for being the first 6.042 student to actually find two different subsets of the above ninety 25-digit numbers that have the same sum. Eric didn’t expect to have to pay off this bet, but he underestimated the ingenuity and initiative of 6.042 students. One computer science major wrote a program that cleverly searched only among a reasonably small set of “plausible” sets, sorted them by their sums, and actually found a couple with the same sum. He won the prize. A few days later, a math major figured out how to reformulate the sum problem as a “lattice basis reduc-tion” problem; then he found a software package implementing an efficient basis reduction procedure, and using it, he very quickly found lots of pairs of subsets with the same sum. He didn’t win the prize, but he got a standing ovation from the class —staff included. Counting seems easy enough: 1, 2, 3, 4, etc. This direct approach works well for counting simple things —like your toes —and may be the only approach for ex-tremely complicated things with no identifiable structure. However, subtler meth-ods can help you count many things in the vast middle ground, such as: • The number of different ways to select a dozen doughnuts when there are five varieties available. • The number of 16-bit numbers with exactly 4 ones.333 16.2. COUNTING ONE THING BY COUNTING ANOTHER Counting is useful in computer science for several reasons: • Determining the time and storage required to solve a computational problem —a central objective in computer science —often comes down to solving a counting problem. • Counting is the basis of probability theory, which plays a central role in all sciences, including computer science. • Two remarkable proof techniques, the “pigeonhole principle” and “combi-natorial proof,” rely on counting. These lead to a variety of interesting and useful insights. We’re going to present a lot of rules for counting. These rules are actually the-orems, but most of them are pretty obvious anyway, so we’re not going to focus on proving them. Our objective is to teach you simple counting as a practical skill, like integration. 16.2 Counting One Thing by Counting Another How do you count the number of people in a crowded room? You could count heads, since for each person there is exactly one head. Alternatively, you could count ears and divide by two. Of course, you might have to adjust the calculation if someone lost an ear in a pirate raid or someone was born with three ears. The point here is that you can often count one thing by counting another, though some fudge factors may be required. In more formal terms, every counting problem comes down to determining the size of some set. The size or cardinality of a finite set, S, is the number of elements in it and is denoted |S|. In these terms, we’re claiming that we can often find the size of one set by finding the size of a related set. We’ve already seen a
View Full Document
Unlocking...