Combinatorics Question

[renanmenezes]

Combinatorics Question.

[GMATGuruNY]

Matt is touring a nation in which coins are issued in two amounts, 2¢ and 5¢, which are made of iron and copper, respectively. If Matt has ten iron coins and ten copper coins, how many different sums from 1¢ to 70¢ can he make with a combination of his coins?

A. 66
B. 67
C. 68
D. 69
E. 70

Could anyone please take a look at this and explain what the q means by "how many different sums from 1¢ to 70¢ can he make with a combination of his coins?"..

The prompt is asking how many different SUMS OF MONEY between 1¢ and 70¢, inclusive, can be formed using up to ten 2¢ coins and ten 5¢ coins.
For example, it is possible to form a sum of 16¢ by combining three 2¢ coins and two 5¢ coins:
(3*2) + (2*5) = 16¢.

From 1 to 70, there are 70 possible sums.
The smallest answer choice is 66.
Implication:
At most, 4 of the 70 possible sums cannot be made from the given coins.
Impossible sums are likely to be VERY SMALL or VERY LARGE.

Small sums:
Of the sums between 1 and 10, the following cannot be formed from 2¢ and 5¢ coins:
1 and 3.

Large sums:
If all 20 coins are used, the sum = (10*2) + (10*5) = 70.
The next smallest possible sums are 70-2 = 68 and 70-2-2 = 66.
Thus, 67 and 69 are not achievable.

Since 4 of 70 possible sums -- 1, 3, 67, and 69 -- are not achievable, the total number of sums that can be formed = 70-4 = 66.

The correct answer is A.

[renanmenezes]

----------

[Matt@VeritasPrep]

Hey, that Matt is me, I submitted this question to the VP database!

The question is asking how many sums from 1 to 70 can be made using only 2s and 5s. In other words, if x and y are both nonnegative integers, how many of these equations are possible:

2x + 5y = 1
2x + 5y = 2
2x + 5y = 3
...
2x + 5y = 70

For instance, 2x + 5y = 1 is impossible, but 2x + 5y = 2 works if x = 1 and y = 0.

As Mitch showed above, 1 and 69 are both impossible. 1 and (70 - 1) ... hmm! This suggest some symmetry, so we look for another impossible sum. 3 is an easy one to find, so we can check (70 - 3), which is impossible too. (Matt would use all his coins to make 70¢, but there's no way to subtract 3¢ here, as he can only subtract a 5¢ or two 2¢'s.)

Since we have four impossible solutions, we can make at most (70 - 4), or 66 possible sums. "Coincidentally" (hah!) this is the smallest answer, so it must be right, and we're done!