Associated Topics || Dr. Math Home || Search Dr. Math

### Breaking One Big Problem into Several Smaller Ones

```Date: 09/11/2003 at 16:26:15
From: Raymond
Subject: change for a dollar

How can I change a dollar into exactly 26 coins?
```

```
Date: 09/12/2003 at 10:02:53
From: Doctor Ian
Subject: Re: change for a dollar

Hi Raymond,

How about 25 pennies, and one 75-cent piece?  :^D

Okay, I'm kidding, but only sort of.  The number of pennies is going
to be a multiple of 5.  Do you see why?  So your choices are

Pennies     Other coins
-------     -----------
25               1
20               6
15              11
10              16
5              21
0              25

How does this help?  Well, now we've got a set of smaller problems.
For example, if there are 25 pennies, we have to figure out how to get
75 cents with 1 coin.  That's impossible, so we can forget about it.

If there are 20 pennies, we have to get 80 cents with 6 coins.  If
there are 15 pennies, we need to get 85 cents with 11 coins.  And so on:

Pennies     Other coins   Amount remaining
-------     -----------   ----------------
20               6                 80
15              11                 85
10              16                 90
5              21                 95
0              26                100

This isn't one of those problems where you just do a few operations,
and the answer drops out.  This is a problem where you systematically
explore the space of possible solutions.  It's not so much about
'math' as it is about keeping track of what you've tried, and what you
still need to try.

Anyway, now you have 5 smaller problems:

1. Find  6 coins other than pennies that add up to 80 cents.
2.      11                                         85
3.      16                                         90
4.      21                                         95
5.      26                                        100

If you can solve any one of these, you can just add the pennies in to
get a solution.

So, how do you solve one of these smaller problems?  The same way.
But now, let's concentrate on quarters.  Suppose we want to find 6
coins that add up to 80 cents.  The number of quarters can be 3, 2, 1,
or 0:

Quarters  Other coins  Amount remaining
--------  -----------  ----------------
3            3                 5
2            4                30
1            5                55
0            6                80

Now, it turns out that it _is_ possible to get 30 cents using 4 coins.
If you can figure that out, you can add 2 quarters to get 80 cents
with 6 coins, and add 20 pennies to get a dollar with 26 coins.

Can you take it from here?

Keep in mind that the answer to the problem isn't all that important.

What's important is the idea that you can break a problem into
smaller problems, and investigate those one at a time - perhaps by
breaking them into smaller problems as well.  The main difficulty is
keeping track of your work, so you don't miss possibilities, or waste
time trying the same dead ends more than once.  That's where tools
like tables and diagrams come in handy.

Note also that there may be more than one solution to the problem!  If
you set up a system that examines all the possibilities, you can be
sure of finding all the possible solutions.

or anything else.

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
Elementary Puzzles
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search