% Fun, CSCE 235, spring 2007 % 25 April 2007 \pdfpagewidth=8.5truein \pdfpageheight=11truein \hsize=6truein \vsize=9truein \pdfhorigin=1.25truein \pdfvorigin=1truein % MetaPost stuff \input supp-pdf \def\fig#1{\convertMPtoPDF{#1}{1}{1}} \def\midfig#1{{% \setbox0=\hbox{\fig{#1}}% \dimen0=0.5\ht0% \advance\dimen0 by-0.3\ht\strutbox% \lower\dimen0\box0% }} \headline={\hfil} \footline={\hfil} \def\title#1{\goodbreak\bigskip\noindent{\bf{#1}}\par\nobreak\medskip\nobreak} \centerline{CSCE~235: Introduction to Discrete Structures} \centerline{\bf Fun} \centerline{April~25, 2007} \title{The bellhop} \noindent Three men check into a hotel and ask what the nightly rate is. The clerk says a room costs 30~dollars a night, so each of the men gives the clerk ten dollars, and they head up to the room. A while later, the clerk realizes he overcharged the men; the room they are staying in is only 25~dollars a night. So he takes five one-dollar bills from the cash box and hands them to the bellhop with instructions to return the money. On the way up to the room, the bellhop realizes that five dollars cannot be split evenly among three men, so he pockets two dollars and returns three dollars to the men. Now, each of the men initially paid ten dollars for the room, but later received a dollar back, so effectively each man paid nine dollars. In total, then, the room cost the men 27~dollars. With the two dollars the bellhop kept, this comes to 29~dollars. What happened to the missing dollar? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Coconuts\hfill\rm from a short story by Ben Ames Williams} \noindent So at last Wadlin told him. ``Well,'' he explained, ``according to the way the thing was given to me, five men and a monkey were shipwrecked on a desert island, and they spent the first day gathering coconuts for food. Piled them all up together and then went to sleep for the night. ``But when they were all asleep one man woke up, and he thought there might be a row about dividing the coconuts in the morning, so he decided to take his share. So he divided the coconuts into five piles. He had one coconut left over, and he gave that to the monkey, and he hid his pile and put the rest all back together.'' He looked at Marr; the man was listening attentively. ``So by and by the next man woke up and did the same thing,'' Wadlin continued. ``And he had one left over, and he gave it to the monkey. And all five of the men did the same thing, one after the other, each one taking a fifth of the coconuts in the pile when he woke up, and each one having one left over for the monkey. And in the morning they divided what coconuts were left, and they came out in five equal shares.'' He added morosely, ``Of course each one must have known there were coconuts missing; but each one was guilty as the others, so they didn't say anything.'' Marr asked sharply, ``But what's the question?'' ``How many coconuts were there in the beginning?'' Wadlin meekly explained. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Cryptarithmetic} \noindent In the following equation, digits have been replaced by letters. What is the original equation? $${\displaystyle\hfill\hbox{\strut SEND}\atop\displaystyle\hfill{}+\hbox{\strut MORE}}\over\hfill\hbox{\strut MONEY}$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Swap} \noindent Describe a way to swap the values of two integer variables in C or Java without using a temporary variable. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{False proof} \noindent Where is the flaw in this ``proof'' that $+1=-1$? \smallskip \item{} Since $+1/-1=-1/+1$, then $\sqrt{+1/-1}=\sqrt{-1/+1}$, that~is, $\sqrt{+1}/\sqrt{-1}=\sqrt{-1}/\sqrt{+1}$, and so, by cross-multiplying, we find that $(\sqrt{+1})(\sqrt{+1})=(\sqrt{-1})(\sqrt{-1})$, hence $+1=-1$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Eight queens} \noindent Place eight queens on a chessboard so that none of the queens is attacking any other queen. \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Difficult crossings} \noindent Three couples wish to cross a river, using a boat that will hold only two persons. However, each husband is too jealous to leave his wife in the company of either of the other men. How can this be done? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Dissection, part~1} \noindent Convert the Greek cross on the left to the square on the right by cutting the cross into four pieces and rearranging them. $$\midfig{fun.1}\qquad\qquad\midfig{fun.2}$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Interrogation\hfill\rm from {\it 101 Puzzles in Thought and Logic\/} by C.\thinspace R. Wylie, Jr.} \noindent Four men, one of whom was known to have committed a certain crime, made the following statements when questioned by the police: \smallskip \item{}{\it Archie\/}: Dave did it. \item{}{\it Dave\/}: Tony did it. \item{}{\it Gus\/}: I didn't do it. \item{}{\it Tony\/}: Dave lied when he said I did it. \smallskip \noindent If only one of these four statements is true, who was the guilty man? On the other hand, if only one of these four statements is false, who was the guilty man? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Forty pounds} \noindent What is the least number of weights that would make possible the weighing of any number of pounds from one to~40, inclusive, on a balance? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Twenty-four quarts} \noindent Partition 24~quarts of water into three equal parts, using only vessels with capacities of 5,~11, 13, and 24~quarts, respectively. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The jar of bacteria} \noindent A jar contains a single bacterium, which reproduces by simple division to produce two offspring every minute, at which rate it will fill the jar in exactly one hour. How full will the jar be after 59~minutes? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The unexpected hanging} \noindent A prisoner has been sentenced on Saturday. The judge announces that ``the hanging will take place at noon on one of the seven days of next week, but you will not know which day it is until you are told on the morning of the day of the hanging.'' The prisoner, on mulling this over, decides that the judge's sentence could not possibly be carried out. ``For example,'' said he, ``I can't be hanged next Saturday, the last day of the week, because on Friday afternoon I'd still be alive and I'd know for sure that I'd be hanged on Saturday. But I'd know this {\it before\/} I was told about it on Saturday morning, and this would contradict the judge's statement.'' In the same way, he argued, they could not hang him on Friday, or Thursday, or Wednesday, Tuesday, or Monday. ``And they can't hang me tomorrow,'' thought the prisoner, ``because I know it today!" Nevertheless, the decree can be carried out. How is this paradox resolved? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The converging cyclists} \noindent Two cyclists are pedaling toward each other along a straight road at the rate of 12~miles an hour. When they are six miles apart, a dragonfly alights on one bicycle and forthwith flies toward the other, shuttling back and forth at the rate of 20~miles an hour until the two cyclists meet. How far did the dragonfly travel during that time? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The false coin} \noindent You have 12~coins, one of which is counterfeit and therefore weighs either more or less than a true coin. What is the minimum number of weighings on a balance required to identify the false coin, if no weights are available other than the coins themselves? Suppose now that you have 80~coins, one of which is counterfeit, but this time you know that the counterfeit coin weighs less than a true coin. Again you have no weights other than the coins; how many weighings are required to find the false coin? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The three smudged foreheads} \noindent Three travelers were aboard a train that had just emerged from a tunnel, leaving a smudge of soot on the forehead of each. While they were laughing at each other, and before they could look into a mirror, a neighboring passenger suggested that although no one of the three knew whether he himself was smudged, there was a way of finding out without using a mirror. He suggested: ``Each of the three of you look at the other two; if you see at least one whose forehead is smudged, raise your hand.'' Each raised his hand at once. ``Now,'' said the neighbor, ``as soon as one of you knows for sure whether his own forehead is smudged or not, he should drop his hand, but not before.'' After a moment or two, one of the men dropped his hand with a smile of satisfaction, saying: ``I know.'' How did that man know that his forehead was smudged? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Dissection, part~2} \noindent The figure on the left below is an $8\times8$~square which has been divided into four pieces. These four pieces are then rearranged to form the $13\times5$~rectangle on the right. But $8\times8=64$ and $13\times5=65$. Where did the extra square come from? $$\midfig{fun.3}\qquad\qquad\midfig{fun.4}$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The candle woman} \noindent In a small town before the days of electricity, there lived an old woman who would go from door to door collecting candle stumps. She was able to make candles for her own use by melting together five stumps into one candle. On one particularly fruitful day she collected 130~stumps. How many candles did this provide her? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Lockers} \noindent A high school has 500~students and 500~lockers; the lockers are numbered from 1 to~500. At the beginning of a particular day the lockers are all closed. The first of the 500~students walks down the halls and opens every locker in turn. The second student then closes every even-numbered locker. Next, the third student visits every locker whose number is divisible by~3; he opens it if it is closed, and closes it if it is open. The fourth student visits every locker whose number is divisible by~4, closing the open ones and opening the closed ones. And so on. After all 500~students have done this, which lockers are open? Why? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Fermi questions} \noindent Named after the famous physicist Enrico Fermi, these questions require estimation of several quantities to arrive at an approximate answer. The goal is to obtain an estimate that is correct to within an order of magnitude (a factor of ten) by making reasonable assumptions to fill in gaps in the available information, rather than relying upon definite knowledge to get an exact answer. \smallskip \item{1.} How many piano tuners are there in Chicago? \item{2.} How many water balloons would it take to fill this classroom? \item{3.} What is the mass, in kilograms, of the student body at UNL? \item{4.} How many jelly beans fill a one-liter bottle? \item{5.} How many golf balls will fit in a suitcase? \item{6.} If the contents of a DVD were printed in book form as zeroes and ones, how much would the book weigh? \item{7.} Approximately what fraction of the area of the continental United States is covered by automobiles? \item{8.} How fast does the hair on your head grow, in miles per hour? \item{9.} How many revolutions does a wheel on your car make when you drive from Lincoln to Omaha? \item{10.} How many meters long is the film for a feature-length movie? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Poker hands, part~1} \noindent How many different poker hands are a full house? a three-of-a-kind? a pair? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The unfaithful husbands} \noindent The village of Conwegia has 30~couples. All of the women are fine logicians. However, they are also jealous wives and incurable gossips, and so every woman knows about the fidelity (or lack thereof) of every husband in the village, except her own. When a woman discovers that her husband has been unfaithful, she kills him in his sleep that night; news of this murder, of course, spreads quickly through the grapevine, and every woman in the village hears the news early the next morning. One morning a busybody enters the village and provides proof that at least one of the husbands in the village has been unfaithful, without giving any indication of which man is guilty. (As it turns out, every one of the 30~husbands has been unfaithful, but all that the busybody reveals is that there is at least one unfaithful husband.) Of course, every one of the women in the village hear this new gossip within an hour or two. All is quiet for the next 29~nights, but on the thirtieth night there is great bloodshed in Conwegia as every one of the wives murders her husband. Why? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Magic hexagon\hfill\rm from {\it Mathematical Gems\/} by Ross Honsberger} \noindent Place the numbers 1,~2, 3, \dots,~19 into the following hexagonal grid so that every straight line of numbers (in all three of the main directions) adds up to the same sum. $$\midfig{fun.5}$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The Monty Hall problem\hfill\rm this version by Mueser and Granberg, 1999} \noindent A thoroughly honest game-show host has placed a car behind one of three doors. There is a goat behind each of the other doors. You have no prior knowledge that allows you to distinguish among the doors. ``First you point toward a door,'' he says. ``Then I'll open one of the other doors to reveal a goat. After I've shown you the goat, you make your final choice whether to stick with your initial choice of doors, or to switch to the remaining door. You win whatever is behind the door.'' You begin by pointing to door number~1. The host shows you that door number~3 has a goat. Does switching your choice to door number~2 increase your chances of winning? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{One million factorial} \noindent What is the rightmost nonzero digit of $1\,000\,000!$ (one million factorial)? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The tunnel} \noindent A tunnel underneath a large mountain range serves as a conduit for 1001~identical wires; thus, at each end of the conduit, one sees 1001~wire-ends. Your job is to label all the ends with labels (\#1,~\#2, \dots,~\#1001), so that each wire has the same label at its two ends. You may join together arbitrary groups of wires at either end; they will then conduct electricity through the join. Then you cross the mountains by a very expensive and dangerous helicopter ride to the other end, where you can feed electricity through any wire and check which of the other ends are live, attach notes to the wires, and make (or unmake) connections as desired. Then you fly back to the near end, perform the same sort of operations, fly back, and so on as often as required. How can you accomplish your task with the smallest number of helicopter flights? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Poker hands, part~2\hfill\rm from a problem book by Friedland} \noindent Suppose you are playing poker with a small group of companions and a single deck of cards. If Lady Luck guarantees you a full house, and you can choose which full house you will get, which one should you choose? (Hint: The answer is not ``three aces and two kings.'') %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Dropping eggs} \noindent Suppose we wish to know which windows in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions: \smallskip \item{$\bullet$}ÊAn egg that survives a fall can be used again. \item{$\bullet$} A broken egg must be discarded. \item{$\bullet$} The effect of a fall is the same for all eggs. \item{$\bullet$} If an egg breaks when dropped, then it would break if dropped from a higher window. \item{$\bullet$} If an egg survives a fall, then it would survive a shorter fall. \item{$\bullet$} It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor windows do not cause an egg to break. \smallskip \noindent If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second-floor window. Continue upward until it breaks. In the worst case, this method might require 36 droppings. Suppose two eggs are available. What is the least number of egg-droppings that is guaranteed to work in all cases? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The marathon} \noindent Alice and Bob ran a marathon (assumed to be exactly 26.2~miles long) with Alice running at a perfectly uniform eight-minute-per-mile pace, and Bob running in fits and starts, but taking exactly 8~minutes and 1~second to complete each mile interval [this refers to all intervals of the form~$(x,x+1)$, including, for example, the interval from 3.78~miles to 4.78~miles]. Is it possible that Bob finished ahead of Alice? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Land\hfill\rm Lester R. Ford} \noindent Alice and Bob own roughly rectangular pieces of land on the planet Earth, which is assumed to be a perfect sphere of radius 3950~miles. Alice's land is bounded by four fences, two of which run in an exact north-south direction and two of which run in an exact east-west direction. Her north-south fences are exactly 10~miles long; her east-west fences are exactly 20~miles long. Bob's land is similarly bounded by four fences, but his north-south fences are 20~miles long and his east-west fences are 10~miles long. Whose plot of land has the greater area? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Cards} \noindent Consider a deck of cards of three types: one type is blue on both sides, one type is red on both sides, and the last type is blue on one side and red on the other. There are an equal number of cards of each type. You are dealt one card at random from this deck, which is placed flat on a table. The top side of this card is blue. What is the probability that the bottom side is also blue? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Plural} \noindent Find a word that, when spelled backward, becomes its own plural. (This is something of a trick question.) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{The bridge} \noindent Four people come across a bridge on a moonless night, which they need to cross. After examining the rickety structure, they decide that no more than two people should risk crossing at once, for fear of overloading the bridge. However, they have only one flashlight among them, which they need to have to cross the bridge to avoid stepping on rotten planks or falling through gaping holes into the river. Furthermore, the four people require different amounts of time to cross the bridge: the fastest can cross in one minute, the slowest needs ten minutes, and the others need two minutes and five minutes, respectively. When two people cross the bridge together, they must walk at the pace of the slower person. They realize that two people must cross the bridge first, and then one of these people needs to return across the bridge with the flashlight; the flashlight must be shuttled back and forth across the bridge in this fashion until everyone has safely crossed. How can the four people cross the bridge in the minimum amount of time? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Lines of coins} \noindent Place 10~coins in five straight lines so that each line contains exactly four coins. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bigskip\hrule\bigskip \noindent Many of these puzzles were taken from the article ``Number Games and Other Mathematical Recreations'' in the 15th edition of the Encyclop\ae dia Britannica. Others were found online at {\tt http://stanwagon.com\slash wagon\slash Misc\slash bestpuzzles.html}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bye