# Making change with prime-valued coins

Am I understanding this question correctly and how do I approach these problems?

In Numberland, the unit of currency is the El (E). The value of each Numberlandian coin is a prime number of Els. So the coin with the smallest value is worth 2E. There are coins of every prime value less than 50. All payments in Numberland an exact number of Els.

(a) What is the smallest payment (without change) which requires at least 3 coins?

My opinion: This seems a bit too obvious which is why I am uncertain. If the smallest is 2E then then the smallest payment that requires 3 coins would be 6E. Is this question actually this easy or am I misunderstanding it?

(b) A bag contains 6 different coins. Alice, Bob and Carol take 2 coins each from the bag and keep them. They find that they have all taken the same amount of money. What is the smallest amount of money that could be in the bag? Explain your reasoning.

My Opinion: I am still unsure of how to approach this question. Help would be appreciated.

(c) Find 5 Numberlandian coins which, when placed in ascending order, form sequence with equal gaps of 6E between their values.

My Opinion: Assuming that I am not misunderstanding the question I got 5, 11, 17, 23, 29 simply by writing down the first few primes and looking for this pattern.

(d) The new leader of Numberland decides to mint coins of prime values greater than 50E. Show that no matter what coins are made, there is only one set of 5 Numberlandian coins which, when placed in ascending order, form a sequence with equal gaps of 6E between their values.

My Opinion: Still Unsure of how to approach it. Help would be appreciated.

Thank you so much :)

• For part B, I think you must show which is the smallest number that can be decomposed as a sum of two different primes in at least three different ways (the answer would be $3$ times this number). – Daniel May 3 '15 at 5:43
• For (a), you can make a payment of 6E with two 3E coins, so a payment of 6E does not require 3 coins. – JimmyK4542 May 3 '15 at 6:01
• @JimmyK4542 But does that still mean that 6E is the smallest payment? – Cool Guy May 3 '15 at 6:15
• Hint for part d. Assume that instead of separation of 6E we were asked about sequences with separation 2E. We see that 3,5,7 is such a sequence, but cannot find longer ones. In fact 3,5,7 is the only sequence of length 3, because if $n>2$, then not all of $n,n+2,n+4$ can be primes because one of them will be divisible by ___ (you fill in the blank and adapt). – Jyrki Lahtonen May 3 '15 at 6:18
• Hint for part b. Have you ever heard of Goldbach's conjecture? Because it has been verified up to gazillions (with the expanded mint selection of part d), it seems clear that the answer won't be a small ____ number. It looks like you need to roll up your sleeves and do some dirty work listing sums that can be paid using at most two coins, and check what's the smallest one missing. Of course, you can try and be clever, but since this is contest math, I won't spoil this any further. – Jyrki Lahtonen May 3 '15 at 6:36

For part (a): It is asking for the smallest payment which requires three coins. For example, in usual American currency, 25 cents can be paid using three coins (dime, dime, nickel), but you would not say it requires three coins, since you can easily pay it with one coin.

In Numberlandia, 2E can be paid with a single 2E coin. 3E can be paid with a 3E coin. 4E can be paid with two 2E coins. 5E can be paid with a 2E coin and a 3E coin. 6E can be paid with two 3E coins... and so on. All of these values can be paid with two coins so far, so you have to keep going until you find that you need three coins.

For part (b): The bag will contain six coins which are six different prime values: $p_1$, $p_2$, $p_3$, $p_4$, $p_5$, $p_6$. Then you need to arrange it so that Alice's coins (say $p_1$ and $p_2$), Bob's coins ($p_3$, $p_4$), and Carol's coins ($p_5, p_6$) all have the same sum. As a starting hint, none of the six primes should be $2$. Then the person who ends up with $2$ will have an odd sum, but the other two would have even sums. So the first set to try would be some arrangement of $3, 5, 7, 11, 13, 17$. Can you get this set to work? Why or why not?

For part (d): There is a good hint already in the comments. A more number-theory-y way to phrase the problem is: Show that if the six integers $x, x + 6, x + 12, x + 18, x + 24$ are all prime, then $x = 5$. Does this help?