From: rknig@NOSPAM.csus.com (Roddy Knight) Newsgroups: sci.math Subject: Re: Help with Logic Problem Date: Sun, 07 Sep 1997 12:43:33 -0800 Organization: CSU Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit I just wanted to let everyone know that I received answer to the problem. It is no longer necessary for anyone to solve it. I have posted the answer I received since I think it is quite thorough. It is from Brian Scott . >"Shortly after opening, a small diner contained only three customers, all >men, and the owner, a women. When the three men simultaneously got up to >pay their checks, the following facts were discovered: > >1) Each of the four had at least one coin, none of which was a penny or a >silver dollar. So the coins available were nickels, dimes, quarters, and half-dollars. >2) None of the four could change any coin. No one had more than 1 nickel (or he could have made change for a dime), no one had more than 1 quarter, and no one had more than 4 dimes. Also, anyone who had a nickel had at most 1 dime. >3) The man named Lou had the largest check to pay, the man named Moe had >the next-to-largest check to pay, and the man named Ned had the smallest >check to pay. >4) None of the three men could give the woman any coins to pay his check >and receive the correct change. This also implies that none of the men could pay the exact amount. >5) If the three men made equal exchanges among themselves, then each man >could pay his check without requiring change. At the very least this means that each check was a multiple of 5 cents; otherwise someone would have needed pennies. But it means more. For instance, no one could have started with just a dime and a nickel. Had anyone done so, (5) implies that his check would have amounted to at most 15 cents, and he could have paid it without making the exchange. (I assume that 'equal exchanges' means that after the exchanges each man ended up with the amount of money that he'd had originally.) >6) When the three men made these equal exchanges they discovered that each >of them thne had only denominations of coins he had not origionally held. This immediately implies that no denomination was originally held by all three men: each was missing at least one denomination. Suppose that some man originally had a nickel. Then he must have had other coins as well, since after the exchange he ended up with no nickels but the same total amount of money. Suppose that he also had a dime. We just saw that he must have had at least one other coin, and it couldn't have been another dime or nickel. Suppose that it was a quarter. He couldn't have had another quarter, so his original holding must have been precisely a nickel, a dime, and a quarter, for a total of 40 cents. But after the exchange he can hold only half-dollars and must hold the same amount, so this is impossible. Therefore if any of the men started with a nickel and a dime, he must also have had a half-dollar, and he must have ended up after the exchange with nothing but quarters. However, no one originally held 2 quarters, so he could have received at most 2 quarters in the exchange. This means that he could have ended up with at most 50 cents, contradicting the assumption that he started with at least 65 cents. It follows that no one originally had both a nickel and a dime. It's also easy to see that no one started with 2 dimes and nothing else. After the exchange he'd have had no dimes, but he'd also have had 20 cents. This means that he'd have had 4 nickels, which could only happen if he got at least 2 nickels from one of the other men. But that's impossible, because no one had more than 1 nickel to start with. (In fact, there are at most 2 among all three men combined.) We now know that no one started with exactly 5, 15, or 20 cents. It's also easy to see that none of the men can have started with dimes, quarters, and half-dollars: he'd have to end up with nothing but nickels, and there aren't enough available. And none of the men started with 4 dimes and nothing else, since the only ways to make 40 cents using only nickels, quarters, and half-dollars all require too many nickels. Essentially the same argument shows that none of the men started with 4 dimes and either a quarter or a half-dollar, or with 2 dimes and a quarter or half-dollar, or with a dime and a quarter. Suppose that one of the men, say X, started with 1 quarter and nothing else. After the exchange he must have 1 nickel and 2 dimes. (He can't have exactly 2 nickels, and since each of the other two men started with at most 1 nickel, he can't have more than 2.) If X got the nickel from Y, Y must end up with no nickels. This means that the third man, Z, cannot have had a nickel originally: he'd have to get rid of it in the exchange, and neither X (who gets his from Y) nor Y (who ends up without one) can receive it. In other words, if X started with just a quarter, there can be only 1 nickel among the three men, the one that Y gave to X. Now what could Y's original holding have been? He can't have had just the nickel, or just the nickel and a dime, or just the nickel, a dime, and a quarter. Could he have had the nickel and 1 quarter? Then he must end up with 3 dimes, and they can only come from Z. The 2 dimes that X ends up with must also come from Z, so Z must have started with at least 5 dimes, which is impossible. This shows that Y cannot have started with 1 nickel and 1 quarter. He also cannot have started with 1 nickel and 1 half-dollar. That's 55 cents, and after the exchange it must be made up with just dimes and quarters. The only possibility is that he ends up with 1 quarter and 3 dimes, and the dimes must come from Z. But as we just saw, Y cannot get 3 dimes from Z. The only remaining possibility is that Y started with 1 nickel, 1 quarter, and 1 half-dollar. That's 80 cents, so after the exchange he'd have to have 8 dimes, and they'd all have had to come from Z, since X didn't have any. But no one held more than 4 dimes originally, so this is impossible. Therefore if X began with just a quarter, there is no possible holding for Y, and it follows that no one began with just 1 quarter and no other coins. Using N, D, Q, and H in the obvious way to represent the coins, we see that we've eliminated all but the following initial holdings: D; H; NQ; NH; DDD; DDDQ; DH; DDDH; QH; NQH. (Note that this means that none of the men started with more than 3 dimes.) If one of the men, say X, started with DH, he must have ended up with NNQQ. This means that each of the other two men must have had a nickel in his original holding. Moreover, one of them must end up with X's H and therefore must not hold an H to begin with. But there is no possible initial holding that contain a nickel, totals at least 50 cents, and doesn't contain a half-dollar. Therefore DH isn't a possible initial holding. We can also eliminate NQH: its original holder would have to end up with 8 dimes from the other two men, but they started with at most 6 dimes between them. A similar argument eliminates QH: to make up 75 cents using only dimes and at most 2 nickels, one must use 7 dimes and 1 nickel, and that's one dime too many. Similarly, note that to eliminate DDDH, note that to make up 80 cents with quarters and at most 2 nickels, one must use 3 quarters. But since no one has more than 1 quarter, there are at most 2 quarters available. At this point only five initial holdings have not been eliminated: D; H; NQ; NH; DDD; and DDDQ. Suppose that one of the men started with D. Obviously after the exchange he must have NN, so the other two men must have started with NQ and NH. (That's the only way to have the necessary 2 nickels.) But the man who started with NQ must end up with DDD, and there aren't three dimes available. Therefore none of the men can have started with 1 dime and nothing else. Suppose that one of the men started with NH. He must get rid of his half-dollar to someone who didn't have one to start with, so one of the men must have started with DDDQ. It's easy to see that in effect these two men simply trade holdings, and the third man therefore must end up with his original holding. Since this is impossible, NH isn't a possible original holding. Essentially the same argument shows that NQ and DDD cannot *both* be original holdings. Since only these, H, and DDDQ haven't been eliminated, this means that the original holdings must have been H, DDDQ, and *one* of NQ and DDD. Say that X started with H. He must get rid of the half-dollar, and only the man, Y, who started with DDDQ can receive it, since the third man, Z, started with only 30 cents. After the exchange Y must have a half-dollar and a nickel; clearly the nickel must have come from Z, who therefore originally held NQ. The original holdings were therefore X:H Y:DDDQ Z:NQ and the holdings after the exchange were X:QQ Y:NH Z:DDD Since X could pay his check after the exchange but not before, his check must have been for 25 cents. Y's must have been for 5 or 50 cents, and Z's must have been for 10 or 20 cents. Now let's consider what the owner originally had. She couldn't have had a quarter, or she'd have been able to make change for X. No matter whether Y's check was for 5 or for 50 cents, if she'd had a nickel, she could have made change for him, so she didn't have a nickel. If she'd had 2 dimes, she could have made change for Z, so she had at most 1 dime. At this point her possible initial holdings in change are D, DH, and H. Suppose that she started with H or DH. Then Y's check must have been for 50 cents. (Otherwise she would have been able to make change for him.) The total bill for the three men would then have been at least 85 cents, and after they had paid, she'd have had over a dollar in change. This contradicts (8) below, so she must have started with D. That implies that Z's check was for 10 cents, and the total bill was either 40 cents or 85 cents. If Y's check was for 5 cents, then after all three men had paid, X held Q, Y held H, Z held DD, and the owner held NDDQ. If Y's check was for 50 cents, the final holdings were Q for X, N for Y, DD for Z, and DDQH for the owner. >7) After the checks were paid and two of the men had gone, the remaining >man bought some candy; this man would have been able to pay for the candy >from the coins he had left, but the woman could not give him the correct >change from the coins she now had. >8) The remaining man was able to pay for the candy with a one-dollar bill, >but had to receive as change all the coins the woman had. If Y's check was for 5 cents, the owner had 50 cents in change and the candy cost 50 cents. But in that case Y was the only one who still had enough change to pay for the candy, and he had the exact amount. This is ruled out by (7). Therefore Y's check was for 50 cents, the owner had 95 cents in change, and the candy cost 5 cents. At that point Y held N and wouldn't have needed change. X held Q, and the owner's 2 dimes would have allowed her to make change for him. The man who bought the candy was therefore Z. >Disregarding the ensuing problems that the woman had in making change that >day, which one of the three men gave the woman the one-dollar bill?" Y's check was for 50 cents, X's for 25 cents, and Z's for 10 cents, so Y is Lou, X is Moe, and Z is Ned. Ned gave her the one-dollar bill. Brian M. Scott -- Remove "NOSPAM" from e-mail address to send e-mail