EmperorJeramyu wrote:"A government issues only two kinds of coins: one of 7 units, and one 11 units. Thus, certain prices cannot be paid exactly, for example: 15 units. What is the highest price that CANNOT be paid with any combination of the two coins? HINT: You may use as many of the coins as needed."
A friend and I have been laboring at this for a while, but we're stupid, so we need help. Perhaps a resident genious (Read: DSOK), could help us out, and provide some reasoning behind the answer. Thanks.
I'm flattered.
In fact, this is my area of greatest expertise; I have a doctorate in mathematics.
First, let me provide an elementary proof that there is a largest such number. Note that you can obtain both 21 (3 x 7) and 22 (2 x 11). This is the first pair of adjacent integers you get. Adding these two together in all possible ways, you can get 42, 43, and 44. Adding those together gives all numbers from 84 through 88, and adding those pairwise gives every integer from 168 to 176. Since this last list of consecutive integers is more than seven long, every form 7n + k for k =0, 1, 2, 3, 4, 5, and 6 is represented. Every larger number can therefore be represented as one of these numbers, plus a multiple of 7.
Notice that 11 = 7 + 4, so any of the larger numbers 18, 25, 32, etc., with the form 7n + 4 can be written as a multiple of 7 plus 11. Similarly, 22 = 3 x 7 + 1, 33 = 4 x 7 + 5, 44 = 6 x 7 + 2, 55 = 7 x 7 + 6, and 66 = 9 x 7 + 3. At this point, we have all the forms 7n + k, so any larger number than 66 can be written as 7n + 11m. The largest number that can't be written in this form is 66 - 7 = 8 x 7 + 3 = 59. This is because 7n + 3 was the last form to be added to our list, and 59 is the largest number with this form that is less than 66.
Posted: Tue Oct 05, 2004 3:07 pm
I had no idea what the real answer was but that woulda been funny as shit if you had gone in with "none". 
