Applied Mathematics is a way to use math to solve problems in the real world, like in economics, engineering, and medicine. 

The objective is to determine how many ways there are to make change for a given amount of money using the following 5 coins: pennies, nickels, dimes, quarters, and half-dollars.

How many different ways can you make change for a dollar using five types of coins? The answer is 292. For ten thousand dollars the number explodes to over 666 quadrillion.

You write a computer program that tests every possible combination of pennies, nickels, dimes, quarters, and half-dollars. This brute-force approach works but runs very slowly. So you search for patterns in the results.

You find that the five-coin problem connects to simpler four-coin and three-coin problems. A new program based on these patterns runs over 26,000 times faster. It solves the ten-thousand-dollar problem in less than an hour.

Project Title: Got Change for $10,000? A Mathematical Analysis

Objectives/Goals

The objective is to determine how many ways there are to make change for a given
amount of money
using the following 5 coins: pennies, nickels, dimes, quarters, and
half-dollars.

Methods/Materials

A Fortran program was written to determine the number of ways to make change for
various amounts of
money using the 5 U.S. coins by finding the maximum number of each coin needed,
then testing all
possible combinations and seeing if they matched the desired amount. This
program ran very slowly.
Patterns in the numbers of solutions were searched for and found, and a new
program, based on the
patterns, was written. It was verified that the results of the new (fast)
program agreed with the old (slow)
program. The reason why the algorithm works was found.

Results

The differences between the numbers of solutions in the 5 coin problem for
amounts differing by $0.05
are the same as the number of solutions for the larger amount in the 4 coin
problem. For example: In the
5 coin problems, there are 9 solutions for $0.20 and 13 solutions for $0.25, and
there are
13-9=4 solutions for $0.25 in the 4 coin problem. The differences in the 4 coin
problem are similarly
related to the 3 coin problem solutions. A simple formula was found for
computing the number of
solutions for the 3 coin problem.

Conclusions/Discussion

An efficient algorithm was found that determined the number of solutions for the
original 5 coin problem
by relating it to the simpler 4 coin problem, and then to the even simpler 3
coin problem. For $5.00, the
new program ran over 26,000 times faster than the original program and even
faster for larger amounts.
The number of solutions grows very quickly as the amount of money increases. For
$1.00 there are 292
solutions, for $5.00 there are 59,576 solutions, and for $10,000 there are
666,794,085,020,860,416
solutions. This last number was computed in less than an hour using the new
algorithm.

Summary Statement

The five coin problem (e.g., how many different ways can you make change for
$5.00 using only the five
U.S. coins) was investigated and a highly efficient algorithm was discovered.

Help Received

Father helped with Fortran programming and suggested looking for patterns in the
data. Mother helped with the display board.

Coin Change Combinations and Fast Algorithms

How many ways there are to make change for a given amount of money using pennies, nickels, dimes, quarters, and half-dollars.

<h1><strong>1000 Science Fair Project Ideas by Subject</strong></h1><p>Looking for a science fair project idea? Each of our science fair project idea has complete instructions with video. Get ideas for your science projects, find extra resources for your class' scientific projects, or try a fun experiment at home! It doesn't matter what grade you're in, there's something for everyone!</p><p>You can find your perfect science fair project from the different science subjects below or from our <a href="https://www.all-science-fair-projects.com/category0.html#bottom">science fair project idea lists!</a></p>

<h2>Science Fair Project Idea Lists</h2><p>Looking for other ways to find good ideas for science fair projects? Check out these lists of science projects!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3>Easy Science Fair Projects</h3><p><img src="/images2/flex/176_popular 2 (2).png" data-size="100" data-float="left" style="width:100px; float:left">Explore the exciting world of science with an easy science fair project that you can do at home using simple materials. Any one of these easy project ideas will teach you important scientific concepts and help you have fun while learning. An easy science fair project is a great way to introduce the wonders of science to kids and adults alike!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><ul><li><p>Changing the Color of Flowers</p></li><li><p>Baking Soda Volcano</p></li><li><p>Swimming Raisins</p></li><li><p>Egg in Vinegar</p></li><li><p>Color of Skittles Experiment</p></li><li><p>Jumping Rice Krispies</p></li><li><p>Mixing Colors of Light</p></li><li><p>Camouflage and Hide</p></li><li><p>Light and Dark on Seed Germination</p></li><li><p>Make a Parachute</p></li></ul><p>More science project details at <a href="https://www.all-science-fair-projects.com/science_fair_project_list/12">Easy Science Fair Projects <strong>→</strong></a></p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3>The Top 10 Best Science Fair Projects</h3><p><img src="/images2/flex/177_popular 2 (3).png" data-size="100" data-float="left" style="width:100px; float:left">To find the best science fair project for you, we've picked the best science projects from 10 different science categories, all with very interesting topics. If you're looking for more science projects at another difficulty level or topic, you can explore science fair project ideas by grade level at the top of this page!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><ul><li><p>Jet Lag in Hamsters (circadian rhythm, Biology science fair project)</p></li><li><p>Egg with Vinegar (acid-base reaction, Chemistry science fair project)</p></li><li><p>Galileo's Inclined Plane Experiment (acceleration, Physics science fair project)</p></li><li><p>Plant's Favorite Color for Photosynthesis (Photosynthesis, Botany science fair project)</p></li><li><p>Color and Taste (color perception, Psychology science fair project)</p></li><li><p>Does Dog Saliva Kill Bacteria? (antibacterial, Microbiology science fair project)</p></li><li><p>Decomposing Plastic Spoons (biodegradable materials, Environmental Science science fair project)</p></li><li><p>Super Hero Egg Shells (structural engineering, Engineering science fair project)</p></li><li><p>Music Math: Playing Notes with Equations (music, Math science fair project)</p></li><li><p>Temperature's Effect on Seawater (climate change, Earth Science science fair project)</p></li></ul><p>More science project details at <a href="https://www.all-science-fair-projects.com/science_fair_project_list/13">Best Science Fair Projects <strong>→</strong></a></p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3>Cool Science Fair Projects</h3><p><img src="/images2/flex/178_popular 2.png" data-size="100" data-float="left" style="width:100px; float:left">Get ready to be amazed by super cool science projects that you can do right at home! With just a few simple things, you can be fascinated by science and have tons of fun with these popular science projects!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><ul><li><p>Explosive Elephant Toothpaste</p></li><li><p>Egg in Vinegar</p></li><li><p>Electrifying Lemon Battery</p></li><li><p>Making Oobleck: Liquid or Solid?</p></li><li><p>Egg Drop Project</p></li><li><p>Colors of Skittles Experiment</p></li><li><p>Cloud in a Bottle</p></li><li><p>Baking Soda Volcano</p></li><li><p>Egg in a Bottle</p></li><li><p>Plastic Milk</p></li></ul><p>Project details and more cool science projects at <a href="https://www.all-science-fair-projects.com/science_fair_project_list/1/Popular_Science_Experiments_At_Home">Popular Science Fair Projects <strong>→</strong></a></p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3>One-Day Science Fair Project Ideas</h3><p><img src="/images2/flex/172_popular 2 (1).png" data-size="100" data-float="left" style="width:100px; float:left">Quick experiments can be a great option for a science fair project. In this list, we've highlighted one-day science fair project ideas for elementary school (easy), middle school (medium), or high school (hard). These experiments are fast and easy to do, but the science topic packs a punch!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h4>Acid-base reactions: Mixing acids with bases quickly makes carbon dioxide gas!</h4><ul><li><p><a href="https://www.all-science-fair-projects.com/project830.html"><strong>Rocket Film Canisters (easy) </strong></a>Make a rocket fly sky high with just baking soda and vinegar!</p></li><li><p><a href="https://www.all-science-fair-projects.com/project829.html"><strong>Make Your Own PH Indicator (medium) </strong></a>Learn how to make your own acid-base indicator using red cabbage and use it to test different fluids!</p></li><li><p><a href="https://www.all-science-fair-projects.com/project1327.html"><strong>Testing Antacids (hard) </strong></a>Find out which antacid can neutralize the most acid and get relief from heartburn and gastritis!</p></li></ul><h4>Chromatography reactions: Separating out colors as liquid moves through the paper!</h4><ul><li><p><a href="https://www.all-science-fair-projects.com/project826.html"><strong>Colors of Skittles Experiment (easy) </strong></a>Did you know that some Skittles have a secret rainbow hiding inside them?</p></li><li><p><a href="https://www.all-science-fair-projects.com/project678.html"><strong>Uncovering Fall Colors (medium) </strong></a>Have you ever wondered why leaves change color in the fall? Let's find out by using chromatography to separate the colors of a green leaf!</p></li></ul><h4>Heat reactions: Heat speeds things up!</h4><ul><li><p><a href="https://www.all-science-fair-projects.com/project274.html"><strong>Which Candle Burns the Fastest? (easy) </strong></a>Do you want to find out which color candle burns the fastest?</p></li><li><p><a href="https://www.all-science-fair-projects.com/project1291.html"><strong>Fire-Resistant Balloons (medium) </strong></a>Ever wondered if a balloon filled with water can withstand fire?</p></li><li><p><a href="https://www.all-science-fair-projects.com/project475.html"><strong>Can Peanuts Heat Water? (hard) </strong></a>Have you ever wondered if peanuts have enough energy to heat up water?</p></li></ul><p>Project details at <a href="https://www.all-science-fair-projects.com/science_fair_project_list/15/Quick_Science_Fair_Projects_You_Can_Do_In_A_Day">Quick Science Fair Projects →</a></p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3 style="text-align: start"><strong>Testable Questions for Science Projects</strong></h3><p><img src="/images2/flex/173_popular 2.png" data-size="100" data-float="left" style="width:100px; float:left">A testable question is a question that we can answer through a science experiment. To do this, we do a control experiment, then we change one thing in the experiment to see how it affects what happens. This is how we can discover the answer to our question!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><ul><li><p>What makes a cloud form?</p></li><li><p>Can drink and food taste different just by changing its color?</p></li><li><p>Does the color of light affect photosynthesis?</p></li><li><p>Does temperature affect seed sprouting?</p></li><li><p>What makes popcorn pop?</p></li></ul><p>More <a href="https://www.all-science-fair-projects.com/science_fair_project_list/14">testable questions with their science projects <strong>→</strong></a></p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h2>Science Fair Project FAQ</h2><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3>What are some hands-on ways to find inspiration for my science fair project?</h3><h4>Science museums</h4><p><img src="/images2/flex/124_7.png" data-size="100" data-float="left" style="width:100px; float:left">Science museums are great places to explore if you're looking for inspiration for your next science fair project or just want to learn more about science. Science museums, natural history museums, space museums, and discovery museums are all great places to do that! You can discover all sorts of interesting things about science and find cool project ideas for science fairs.</p><p>There may be free admission days or free passes to a science museum near you! Check your credit card for offers, your local library for free museum passes, and nearby science museums for free entrance days.</p><p>So what are you waiting for? <a href="https://en.wikipedia.org/wiki/List_of_science_museums">Find a science museum near you</a> and prepare to be awed by all that you can learn there!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h4>Look around and observe</h4><p><img src="/images2/flex/117_5.png" data-size="100" data-float="left" style="width:100px; float:left">Do you know how scientists start their cool projects? They often look around and notice things that are interesting or make them curious. Then they start doing an experiment! You can do the same! Look around your school, home, or community. Is there anything that catches your attention and makes you curious? Maybe you notice something interesting or a problem that people are facing. This could be a great starting point for your science fair project!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h4>Try an Easy Science Project!</h4><p><img src="/images2/flex/144_easy square.png" data-size="100" data-float="left" style="width:100px; float:left">These science projects are easy and fun to do. You may discover a simple experiment that sparks your interest and inspires you to do more experiments, turning it into a science fair project! Check them out at <a href="https://www.all-science-fair-projects.com/science_fair_project_list/12">Easy Science Fair Projects <strong>→</strong></a></p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3 style="text-align: start"><strong>How do I start a science fair project?</strong></h3><p><img src="/images2/flex/199_science coach.png" data-size="100" data-float="left" style="width:100px; float:left">No matter if you're in high school, elementary or middle school, science fair projects are a fun and unique way to discover science by asking a question and doing a science project. We'll help you find a science fair project idea and guide you through the process of doing and presenting your science fair project with <a href="https://www.all-science-fair-projects.com/science_fair_projects_coach/science-project-coach.html">Science Fair Coach's Science Fair Project Guide</a>.</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3>What should I do after I have a science fair project idea?</h3><p><img src="/images2/flex/143_intro science fair.png" data-size="100" data-float="left" style="width:100px; float:left">If you have a science fair project idea, Science Fair Coach can help you turn it into a full science fair project! Starting at the <a href="https://www.all-science-fair-projects.com/pgpage/4">Introduction to Science Fairs</a>, check out the section on <strong>How to do a science fair project</strong> for a step-by-step guide!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><p><img src="/images2/flex/203_compared to scientific method.png" data-size="100" data-float="left" style="width:100px; float:left">We'll guide you through every step of the <a href="https://www.all-science-fair-projects.com/pgpage/5">scientific method</a>, from designing and conducting your experiment to collecting and analyzing your findings.</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><p><img src="/images2/flex/202_engineering design process.png" data-size="100" data-float="left" style="width:100px; float:left">If you're working on an engineering project, you can head over to <a href="https://www.all-science-fair-projects.com/pgpage/9">The Guide to the Engineering Design Process</a>.</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><p> <img src="/images2/flex/150_science fair poster.png" data-size="100" data-float="left" style="width:100px; float:left">Finally, we'll help you showcase your results on a <a href="https://www.all-science-fair-projects.com/pgpage/7">science fair board</a> for others to learn from and enjoy.</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3 style="text-align: start"><strong>How do I make a science fair board?</strong></h3><p style="text-align: start"><img src="/images2/flex/150_science fair poster.png" data-size="100" data-float="left" style="width:100px; float:left">Your science fair board is where you show off your science fair project for everyone to see and learn from. With <a href="https://www.all-science-fair-projects.com/science_fair_projects_coach/science-project-display-board-6a.html">Science Fair Coach's step-by-step guide</a>, you can make sure your science fair board stands out and impresses at the science fair!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><hr style="clear:both; border-style:dotted" data-marker="clearFloat"><h3>Where can I find a science fair competition?</h3><p><img src="/images2/flex/179_Intro Science Fair Projects 32.png" data-size="100" data-float="left" style="width:100px; float:left">Science fair competitions are an excellent opportunity to explore science. One of the of the premier science advocacy organizations, the Society for Science, is associated with more than 400 science fair competitions in almost every US state, as well as over 70 other countries, regions, and territories. You can find out if there's a <a href="https://findafair.societyforscience.org/">Society of Science affiliated science fair</a> near you!</p><p>The <a href="http://physics.usc.edu/~gould/ScienceFairs/">The www Virtual Library: Science Fairs website</a> also has a collection of science fairs from all over the world, as well as national, state, regional, local, and virtual competitions!</p><hr style="clear:both; border-style:dotted" data-marker="clearFloat">

Math is all about numbers, patterns, and solving problems. Computer science is about using math and technology to create computer programs and solve real-world problems. Together, they help us understand how things work, how to solve problems, and how to use technology to make our lives better!

All Science Fair Projects

1000 Science Fair Projects with Complete Instructions

Coin Change Combinations and Fast Algorithms

Hypothesis

Method & Materials

Results

Why do this project?

Also Consider

Full project details

Related Science Fair Project Ideas