Mathematics desk
< September 16	<< Aug \| September \| Oct >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 17

Combining two amounts

2-Euro coins weigh 8.5 gram. 1-Euro coins weigh 7.5 gram. How many of each would you need to have exactly 1 kg?

I solved the problem by trial and error, limiting the max nr. of coins to 1000/8.5=117. The results are: 10, 25, 40, 55, 70, 85, 100, 115x 2-Euro coins and the 1-Euro complement.

for i in range(1,117): 
....     if (1000 - 8.5*i) % 7.5 == 0: 
....         print(f'{i}x 2 Euro coins and {int((1000-i*8.5)/7.5)}x 1 Euro coins.')

Is there a more direct way of solving this and similar kinds of problems? --Bumptump (talk) 23:28, 17 September 2021 (UTC)[reply]

@Bumptump: Convert it to a problem with integers: 17x + 15y = 2000. See Diophantine equation#Linear Diophantine equations. PrimeHunter (talk) 23:37, 17 September 2021 (UTC)[reply]

It's not said, but I assume we're not including solutions with negative coins. That makes the question a bit trickier. Variation: What's the largest multiple of .5 grams that can't be weighed out with 1 & 2 Euro coins (also assuming no negative coins)? --RDBury (talk) 06:11, 18 September 2021 (UTC)[reply]

A coin with negative mass will be worth much more than € 2. --Lambiam 10:11, 18 September 2021 (UTC)[reply]

If we are weighing using a traditional scale (with two plates), it makes totally sense to talk about negative coins. No need to get coins with negative mass. 130 * 8.5 = 1000 + 14 * 7.5. --Bumptump (talk) 16:18, 18 September 2021 (UTC)[reply]

With two coin types we can use the explicit formula given by xy - x - y, here yielding 223/2 as the largest that cannot be made using 8.5 and 7.5; a solution exists for all higher amounts and can be computed explicitly and efficiently with the (extended) Euclidean algorithm. The problem with three or more coin types (and no negative coins) is NP-hard; see coin problem.--Jasper Deng (talk) 22:51, 18 September 2021 (UTC)[reply]