[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
What is the smallest number that can be divided by 6, leaving a remainder of 5; by 5 leaving 4; and by 4 leaving 3?
Source: The Mensa (c) Puzzle Calendar for Oct 18. 2001;
Background & Techniques
Here's an introduction to Chinese Remainder problems. They're called "Chinese Remainder" because the problem and the theorem which defines when they can be solved were both known to the early Chinese scholars. The earliest known example of this type of problem was published in the 3rd, 4th or 5th century AD by Chinese scholar, Sun Zi, in a book titled "Master Sun's Mathematical Manual".
Here's Sun Zi's original problem:
His solution is the following poem:
I'm glad we have computers!
The Chinese Remainder Theorem is not particularly easy to understand - it just says that under certain conditions (i.e. the divisors have no common factors), there is a solution:
If m1, ..., mk are pair-wise relatively prime moduli and a1, ..., ak are natural numbers, then there exists a natural number x that simultaneously satisfies x = ai mod(mi), i=1, ..., k.
Here mod is the modulus (or remainder) operation, a mod (b) is the remainder when a is divided by b.
In terms of the original problem: "Find N such that N mod(6)=5, N mod(5)=4, and N mod(4)=3". Notice that two of our factors (6 and 4) are not relatively prime so the Chinese Remainder Theorem doesn't say whether it can be solved or not. Not very helpful. (In fact, it is solvable, but it's easy to change the required remainder values to find cases that are not solvable.)
Analytical solutions for this type of problem are hard, at least for me. But a computer and Delphi make solving a pretty easy. We'll just take in the three divisors and the three remainders and try numbers from 1 to 1,000 looking for one that meets the requirements.
Two versions of the program are included.
Addendum August 6, 2003: Today's Mensa Puzzle Calendar posed another Chinese Remainder problem involving stamp in a stamp album. I added it to the sample problems in Chinese Remainder 2, and also fixed the program so that extra blank lines in the input grid are ignored rather than reporting an error. If you check the source code, the Tmemos that contain the problem descriptions are all defined in the same location which can make it a little difficult to change, or even find them when workin in Delphi's editor. A tip is to right click on the top memo and then click "Send to back" to view the next one in line (called Z-order by Windows programmer types).
November 4, 2010: A new C.R. problem from our Mensa Puzzle-A-Day calendar today has been added to the set of sample programs.
This is an easier version of a problem dating from the 7th century: An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?
Running/Exploring the Program
Suggestions for Further Explorations
Is there a test to determine that a particular problem has no solution?
Copyright © 2000-2018, Gary Darby All rights reserved.