## Thursday, July 03, 2008

### NPR Sunday Puzzle (Jun 29): Anyone have a Pencil?

NPR Sunday Puzzle (Jun 29): Anyone have a Pencil?:
Q: A man buys 20 pencils for 20 cents and gets three kinds of pencils in return. Some of the pencils cost 4 cents each, some are two for a penny and the rest are four for a penny. How many pencils of each type does the man get?
It's a rare NPR *math* puzzle. Using algebra you could write an equation for the number of pencils, and one for the cost of the pencils. But that results in two equations and three unknowns. Fortunately there are some constraints and a little trial and error will get you the answer. Note: You have to have at least one of each type, so just getting 4 of the first type and 16 of the last type wouldn't work.

Edit: I think the thing that confused most people was they assumed they had to buy 4 of the 1/4 cent pencils, or 2 of the 1/2 cent pencils. You can't make 20 cents with those constraints. Here's how I solved it.

Let A be the number of 4 cent pencils.
Let B be the number of 1/2 cent pencils.
Let C be the number of 1/4 cent pencils.

Number of pencils:
A + B + C = 20 pencils

Cost of pencils:
4A + B/2 + C/4 = 20 cents
Multiplying this second equation by 4 to remove the fractions we have:
16A + 2B + C = 80

Now subtract the first equation to eliminate one variable:
15A + B = 60

There are some obvious constraints on A. Because you need at least one of each type of pencil, none of the values can be 0. That eliminates A = 0 or A = 4. Trying the other values you get:
A = 1, B = 45 --> too many pencils
A = 2, B = 30 --> too many pencils
A = 3, B = 15 --> C = 2

A:
3 pencils (at 4 cents) = 12 cents
15 pencils (at 1/2 cent) = 7 1/2 cents
2 pencils (at 1/4 cent) = 1/2 cent

1. Have you solved this already? I've tried several permutations and it seems impossible. You have any hints?

Anna

2. Same here - I went the equation route, and also tried what I thought was literally every permutation. Some came close but none worked.

3. I can't get it either. Let's check formulas. I've got:
4a+1/2b+1/4c= 20 (cents formula) and
a+b+c=20 (the number formula)
Letting, say a=1,2,3, etc. and then solving the other two equations using the substitution method, I can't get it to work out. What am I missing?

4. It's easy to solve using fractions of cents. But that simplicity seems out of character for NPR puzzles. Am I wrong with this assumption?

5. I agree with Les' equations, and similarly, substituting for a doesn't get much traction.

One thing I noticed is that a has to be an even number, because b and c must be even, and the whole thing adds up to 20. So a is either 2 or 4.

Which makes the equations either (1/2b + 1/4c = 12) and (b + c = 18), or (1/2b + 1/4c = 4) and (b + c = 16).

For the second pair of equations, if you multiply everything in the first equation by 4 you get (2b + c = 16), and a comparison with the second equation can only work if b = 0.

That leaves only the first pair. Multiplying by 4 in the first equation gives (2b + c = 36). By the second equation, c = 18 - b. Substituting that into the first gives 2b + (18 - b) = 36, which works out to b = 18, which means c = 0.

So the only derivable answers by algebra seem to indicate that you only get 2 types of pencils. Where's the flaw in this logic?

6. Not all of Nadahlman's assumptions are correct.

As Robert said, the puzzle is easily solved with partial cents, which I assume is the intended answer (note that Mr. Shortz indicated it came from the 19th century, when coin denominations smaller than a penny were in vogue).

Not as satisfying as a solution using integers all the way around, but hey, it's an imperfect world.

7. one thing about the puzzles are they are usually obvious enough for the average person to figure out and if they are this difficult, I say we are looking in the wrong direction.

8. This comment has been removed by a blog administrator.

9. Yep, those were my equations as well. Must be the halfpenny answer. If you use halfpennies,it solves easily.

10. I can make it to 12 for
12 cents but I can't make
it to 20 for 20 cents:

Cents Pencils
1 4
1 2
4 1
4 1
1 2
1 2
=12 =12

11. This comment has been removed by a blog administrator.

12. A penny saved is a penny earned. The early bird catches the worm. Stupid is as stupid does.

13. Is it Late Night host David Letterman that always throws pencils? Or am I thinking of Conan O'Brien?

14. Thank you, my friends. I jumped way beyond the problem by making a sweeping assumption. Sorry to have encouraged spoilers here with my specifics, but at least it's encouraging to see my grasp of algebra is still pretty firm.

15. Letterman, not Conan. Although he pioneered that bit in the NBC timeslot that is now Conan's.

16. There is an answer as both I and a friend both got it and it works. We both did truial and error becasue our math skill are rusty and solving 2 equations with three unknows is a bit rough, to say the least.

Many of you are making the pitfall that you must buy 4 each of the 1/4penny ones and 2 each of the half penny ones becasue partial cents don't exist. But that doesn't matter because you are buying all the pencils and paying 20 cents so any partial penny cancels it self out with others.

17. Oh, and you are buying whole pencils so those are integers and that is the only thoing asked of the puzzle, not how many pennies you spend on each type.

18. A fair (pencil) point.

19. Sharp idea and to the point! I think we should add breaking the pencils in half just to add to the mix!

20. A friend of mine, Miss Beth figured it out. You write two equations, one for pencils, one for the money. Substitute the money equation into the pencil equation for one of the variables. Simplify and iterate until you get a positive answer. It takes about three iterations. Good luck! :)

21. Les, you've got the right idea...

4a + b/2 + c/4 = 20

a + b + c = 20

You know that a has to be 1, 2, 3, or 4

So, solve for b only in terms of a and solve for c only in terms of a and plug away :)

22. I've worked out an answer by letting a = whatever and then substituting the 'money' formula into the 'quantity' formula. But I can't get it to work out when subtituting the other way.
WHY will it not work both ways?

23. seriously? just saying that at least one of the numbers is even or odd is enough to get deleted?

*shrug*

24. I thought it gave too much away but at this point everyone should have enough information to figure this out. If not, feel free to post back after the deadline (Thurs. 3pm ET) with your solution.

25. I got it:

3 @ 0.04 = 0.12
13 @ 0.01 = 0.07
4 @ 0.01 = 0.01

26. I got it:

3 @ 0.04 = 0.12
13 @ 0.01 = 0.07
4 @ 0.01 = 0.01

27. Ignore my 'why will it not work both ways' post. I made a simple math error. It works both ways.

28. Hi Katchena,

Having been rightly upbraided myself for my silliness earlier, I feel it my duty to point out you have some problems with your math. Half a cent is \$.005, and 13 x \$.005 = \$.065. I'm pretty sure you can't round up in this problem.

29. Are (some of) you people out of your minds?

There is no algebraic equation set that will definitively solve this. There are only 4 allowable possibilities for the 4 penny pencil, so start there and use a little guessimation for what the other two numbers could, should (and need to) be. Believe me, after only a little bit of trial and error, you will have it. I just wish I had worked "backwards." Then again, with trial and error, the "last" answer is alwasy the right one.

Anyway, I did it with pen and paper alone in the margins of a small card in only about 10 minutes and my friend polished it off in Excel in about the same amount of time. So stop making it so hard and stop being so afriad to actually do a little addition, multiplication and subtraction. Algebra is a great and very useful skill, but it is not always the be-all and end-all method.

BTW, if anyone knows how to solve this mathematically, with some sort of Taylor Series, derivative, min/max, obscure linear algrebra theorem, eigenvector, eigenvalue or something, I'd love to know. My collegiate math skills have goine a bit rusty.

30. I, too solved it in Excel, so...

And as far as the .005 is concerned, at least I got an answer that seemed as close to what the answer should be!

31. I've been arguing with my friend who did it in Excel.** I say it was a cop out. More fun to use pen (not pencil) and paper. Better for the old noggin' that way. But, then again, his Excel skills are better than mine, so I guess, 6 of one, half a dozen another.

** He also did this week's Car Talk Puzzler (google it) in Excel. I felt that was a bit extreme for such a simple problem that was not only algebraiclly simple, but could even be done in the head logically with minimal math.

32. There's a link to the Car Talk Puzzler to the right of my blog. You don't even need algebra skills for that puzzle, just some subtraction skills.

As Kachena has shown, if you rely on a tool (like Excel) you are liable to get the wrong answer.

33. Now that everyone has sharpened their math skills, isn't anyone up to figuring out the Catch The Bus Puzzle?

34. Yes, that CarTalk omelet puzzler (if even a puzzler at all) was too easy, even for them. I'm ashamed that when I did it, I was so used to there being a hitch, that I didn't just do it in my head. Too habitually, I wrote out the three equations then solved them through sustitution, when all I really had to do was two quick subtractions (which by the time I wrote the three equations down, should have been quite patently obvious).

I agree that using tools Like Excel can spit out the wrong answer, but only in the realm of garbage in = garbage out. I'm assuming that round-off problem was Excel's fault, but I'm not sure why she didn't pick up on that when she posted her answer.

However, if you set things up right in Excel, then it should work. If she had only used dollars instead of cents (or pure numbers instead of money or changed the significant digits of the money), then that roundoff would not have automatically happened.

It's good to know that thoughts of partial pennies even messes up Excel, even though we deal with them each and every single day (when calculating sales tax for instance). I can only assume that people will be really confused if we ever do drop the penny. I mean, how do you round partial nickles? Always up, even if less than a penny (I'm sure business would love that) or up at 2.5 cents and down at less? But if there is no such thing as a penny or cent, what is the meaning of 2.5 cents anyway? And how do you set up a relaible number system that has no unity digits other than zero and 5? That just seems like cruelty, especially for the vast majority of humans that are already struggling with numbers as they are.

35. This comment has been removed by a blog administrator.

36. Hard to argue with that.

37. Seems legit enough...

38. Spoilers and outright answers aren't allowed until after the NPR deadline has passed.

GregDavid used the same method I did and showed that the answer is straightforward. I'll repeat the details tomorrow after the 3pm ET deadline.

39. Sorry about posting the spoiler. I was feeling a bit proud of my latest uber-streamlined method** (I solved this long before I even found your blog, the hard way.)

** (My friend and I have been bantering back and forth about the best way to solve this (without Excel). He sent me something that seemed novel but quite convoluted. That sparked something in me to work out a better solution, somewhat based on his, that was very staightforward and quick easy to work out. Instead of my original brute force trial and error method that required many cases to be calculated. Worked? yes! Quick and painless, no!)

I'm still wondering if anyone knows a way (or the way) to solve this without having to do any trial and error or iterations, you know, purely with equations and no test substitutions? Or is it that problems like this really do exist beyond the realm of "pure math?" Just wondering.

40. My first post here. It's interesting reading all the clues and thoughts. For some reason, my head found it much easier to think of these as three distinct items (like apples, bananas and peaches) and not all pencils.
And, yes it is easy if you allow that you can buy the pencils in "odd lots" -- after all, we can buy a gallon of gas for \$4.0397.
Late night TV is a distant memory for me, but I would have sworn it was Johnny Carson who tossed the pencil over his shoulder every night.

41. Carson famously had pencils with erasers at both ends, which he would idly drum with or toss and catch. But I think Letterman more than Carson was known as a thrower. For one thing Letterman has the fake windows and they play the crashing glass sound when he throws... wait a minute... maybe I was thinking of Letterman throwing his blue index cards through the window.

42. I like the elegance of one of the middle moves Greg David made in his math approach, i.e. substituting in that expression from one equation into the other one. It led more directly to the answer.

Failing to see that, I still had viable equations but it took more trial and error work to reach the answer.

43. It's funny how our brains work. We see 4 for a dollar and we isntanly assume we have to buy them 4 at a time.

Marketers know this all too well and use it to their advantage to sell more product. That is why they so often have two-for deals. They know that most think they have to buy two when they really don't.

I, of course, nearly always just buy one which will then ring up at half the 2-for price. Great way to try and get the store's computer system to mess up and then get the item for free as a courtesy for scanner errors. Plus, before there were automatic UPC scanners, the checkout person would have to do division and you know how few of them can actually do any math anymore.

44. Sorry, I guess my comments about Conan O'Brien and the cheese omelette w/ bacon (ala Car Talk Puzzler) were a little off-topic. I'll try to stick to comments relevant to the pencil puzzle.

45. Sorry, I'm the one that brought up the Omelet Puzzler. It seemed fittig to mention it because not only did Will give us a rare math puzzler, but so did CarTalk, and Will's was a real puzzler (challenging) and Click and Clack's was hardly a puzzler at all (which they admitted at the outset).

46. Here is the matrix formula:

http://ccrma.stanford.edu/~jos/mdft/Solving_Linear_Equations_Using.html

By subbing for c, you get 2 linear equations, and you can solve from there.

47. This problem, with two equations and three unknowns (where the unknowns are integers) fails into a category called Linear Diophantine Equations. In our case, the easiest solution is reduce the problem to one equation with two unknowns and then try all the possibilities of one variable (eg. A, the number of 4 cent pencils).

48. Yet another comment . . . ;-)
This being a puzzle from a 19th century trade card, I wondered what coins were available. The half cent coin was produced in the United States from 1793-1857.
http://en.wikipedia.org/wiki/United_States_half_cent_coin

49. It is a little sad to be up in the middle of the night working on a puzzler, but I think I got it. I set up a grid of 5x4 squares, each square representing a pencil. I used trial and error to assign each square a price until they added up to 20 cents. Using a visual made it easier for me.

50. Thanks for the excellent math link Blaine. That is highly educational. Sorry for being too lazy to look it up myself.**

** Then again, I never would have pulled DIOPHANTINE out of my proverbial rear so not sure what I would have searched on. But clearly the key is simultaneous equations with integral solutions. I kind of intuited that the whole pencil condition was key and is surely what made a singular solution even possible but I still seemed to believe that condition could be used to eliminate trial and error rather than just minimize it. Otherwise why would I have multiplied through by 4 to get rid of the halves and quarters(a stroke of real genius that I didn't even realize at the time).

Still struggling with the Bus Problem. I think I have the answer, through logic, intuition and some graphical aids, but I have yet to try to prove it mathematically (a bit out of laziness but also from a lack of a definitive method and the requsite genius to come up with one).

51. Three things:

1. Blaine's math link is good. I'm only on page 2 and I can already see I will enjoy reading it. Isn't it funny how as adults we sometimes wish we could go back to school and just enjoy learning where it was so often a chore at the time?

2. I post the NPR puzzle on my blog every week and offer hints to whoever wants to email me for one. Sometimes (Shalit, Ebert) the emails are not particularly interesting, but with certain puzzles such as 8735 and this week's, it can lead to some unexpected and surprising revelations.

For example, one correspondent came up with a solution in which the man bought fractional pencils:

"hey, i think i got it....

He bought 3.5 of A
7.5 of B
and 9 of C

A + B + C = 20
3.5 + 7.5 + 9 = 20
4A + 1/2B + 1/4C = 20
14 + 3.75 + 2.25 = 20

its right =D but i dont get how you can buy 3.5 of a pencil =\ is there a different way?"

I told him I believed the intended answer involved round numbers of pencils, if not costs, but who knows, maybe they'd accept his answer too.

3. I have not tried to solve the bus puzzle yet. At first glance it looked to me like a pretty straightforward exercise in determining at what physical point the express bus' faster rate compensated for its later start. But Greg David's comment just above this one makes me wonder whether it is tougher than I first thought?

52. occasionally i search on Google for forums or bulletin boards where people are discussing the Sunday Puzzle, and i'm so glad to find one such as this!

two coworkers and i hammered away at the pencils puzzle, and ultimately we agree with GregDavid, that the focus should be limited to the pencils as integers, the ability to buy any number of pencils, despite how they're priced.

i just wish the quantity of cents were all whole numbers :(
it would have made it more satisfying to solve the riddle, especially after making an Excel spreadsheet with formulas in each cell, etc. oh well.

53. "i just wish the quantity of cents were all whole numbers :("

It can be (sort of). Just multiply your total cost equation by 4 (on both sides). All the nasty fractions (or .25 and .5) go away and, luckily with this puzzle at least, no ugly fractions return. If you do it right, then you will find doing a spreadsheet cost your far more time than it saved.

BTW, I really wish Will Shortz had mentioned the whole pencil requirement but it really isn't much of a stretch as far as assumptions go. It's the belief that you don't have to buy and 2's and 4's of the cheap ones that most have problem coming to terms with (which is surely an interesting phenomenon to study in the realm of Psychology, Reason and Marketing).

54. Sometimes it's easy to overthink. I got it in about 5 mins with excel trial and error. Call it cheating if you must, but I always mess up systems of equations....

55. Everyone ready for 4th of July? I'm trying to figure out if I should barbecue chicken or burgers. Corn on the cob is a given, though.

56. Anyone notice my clues to the answer?

Conan O'Brien (COB)
Cheese Omelette + Bacon (COB)
Chicken Or Burgers (COB)
Corn on the COB

Taking the position of each letter in the alphabet:
C = 3
O = 15
B = 2

57. You should have made that your own puzzler. Something like: What does the Pencil Puzzler and one or more of those word sets have in common? That would have been a real good one. I doubt I would have make the leap to alphabetic positions.

It would be neat to formulate a similar puzzle that has items that start with those letters (instead of pencils) and see if anyone catches it. Like a mystery novel, all the clues are there in plain view, you just have to know where to look (viz., shift your focus).

Enjoy the BBQ. Probably Marinated Pork Steaks, COB and marinated and grilled veggies and gourmet potatos here, plus some sort of spirits (maybe). No clues there, just love to grill in the Spring, Summer and Fall and just anything can be done on one, and it keeps the house cooler to boot.

58. This comment has been removed by the author.

59. What a dumb puzzle. Show
me a 1/4-cent piece,1/2-cemt piece?

60. U.S. Half Cent from the 19th century... remember the puzzle mentioned the 19th century.

61. I was a bit disheartened that Will simply gave the answer to this puzzler and did not mention one iota about the solution, the pitflls and/or that such problems exist in a special realm of mathematics that have puzzled and challenged even the greatest of mathematicians for centuries, even to this very day.

From Wiki:

"The questions asked in Diophantine analysis include:

Are there any solutions?
Are there any solutions beyond some that are easily found by inspection?
Are there finitely or infinitely many solutions?
Can all solutions be found, in theory?
Can one in practice compute a full list of solutions?
These traditional problems often lay unsolved for centuries, and mathematicians gradually came to understand their depth (in some cases), rather than treat them as puzzles."

Clearly Will is a true puzzle guy first and foremost, and not a mthematician, and thus, has failed to understand the greater depth of what he does. Nobody's perfect.

62. Pencils or pets, it's all about the same (almost). I just found this in the CarTalk Puzzler Archive:

New Puzzler: Cats, Dogs and Mice - Oh My!

RAY: I happened to find this puzzler the other day in my puzzler folder. It's from Barry Lawber. And it's from July '96.

TOM: I hope he's still alive.

RAY: I hope so too.

Here's his puzzler:

You're given a hundred dollars and told to spend it all purchasing exactly a hundred animals at the pet store. Dogs cost \$15. Cats cost a buck, and mice are 25 cents each.

TOM: Let me get this straight. You have to spend exactly a hundred bucks and you end up with exactly a hundred animals?

RAY: Right. The other only other criterion is that you have to purchase at least one of each animal.

The question is, how many of each animal do you have to purchase to equal a hundred animals purchased at exactly a hundred dollars?

63. You can solve it the exact same way as the pencils...

Let D, C and M be the number of dogs, cats and mice, respectively.

Number:
D + C + M = 100

Cost:
15D + C + M/4 = 100

Multiply the second equation by 4 to get rid of fractions:
60D + 4C + M = 400

Subtract the first equation to eliminate M:
59D + 3C = 300

Valid values of D are 1 to 5. But only one of these gives a value of C which is a whole number. The rest is left as an exercise for the reader.

64. Unlike our puzzle, no fractional purchases required.

65. My only point in posting the pets puzzle wasn't to see if anyone could solve it. Obviously it was nearly identical - nearly so - so if you could do pencils, then pets was a walk in the park - which is what I meant in my quip, "Pencils or pets, it's all about the same (almost)." (Almost) referring to slightly different coefficients.

However, when I saw it in Click and Clack's archives (as I tried to cheat on 335 443 554), I realized that I may have just encountered it before. (Sometimes I never miss CarTalk and doing their puzzler, other times I forget they and them even exist). But I never would have forgotten Linear Diophatine Equations (which, to the best of my aging memory, never even came up in HS or 4 years excelling at RPI).

So, I just wanted to highlight the fact that these sorts of puzzlers come in many flavors and come up every so many years, here and there, in one form or another, as I had learned from reading about this very interesting class of problems (Thanks to Blaine's Link and then Wiki - knowing what they are called made all the difference).

Of course, t'were I more passionate about doing puzzlers and solving everything, everywhere, all the time (like my physicist friends are and do), than simply talking about puzzlers, I would have solved the Pets one too.

But, to me, the real fun is the self discovering how, not the simply doing, when you already know how. At that point, it's just work, and work I like to be paid for (even if it is fun too). }:-)