Can you solve Martin Gardner's "coin of the realm" puzzle?


#1

[Read the post]


#2

Probably wrong, but 1, 2, 4, 8, 16, 32, 64 seems the most obvious.

[ETA: Reading comprehension is hard. Every bad exam I ever took was because I didn’t read the damned question properly]


#3

I thought that, too, but then I tried to make 50 with 2 coins.


#4

7 would require 3 coins (1, 2, 4) with this system.


#5

Doesn’t work for 7, 11, or 13 either.


#6

As a kid, I liked puzzles because I could prove how smart I was. Now I hate puzzles because they prove how stupid I am.


#7

Does this puzzle require the coins to be frictionless point-masses?


#8

Series of primes doesn’t work, either.


#9

Fibonnaci numbers fail at 12.


#10

I’m not sure, but now I’m wondering how you would flip a perfectly spherical, frictionless coin.


#11

Do the denominations of the coins have to be in whole-cent amounts?


#12

Okay, I think I’ve figured it out, and the answer is, “No, there’s no better answer than the one given.”

It has to do with geometry.

In order for this to work, you need to have one set of coins be the number of blocks that you’re dividing 100 into, and then another set of coins be the number of blocks that you’re dividing the larger blocks into.

So if you broke the number up into blocks of, say, 20, then you’d have 4 coins making up the intervals (20,40,60,80) and 19 coins making up the rest of the numbers.

You’re effectively trying to minimize x+y where (x+1) (y+1) = 100.

This is exactly the same as trying to minimize the perimeter of a rectangle for a given surface area, and the rectangular shape that always accomplishes this is a square (x=y).

Since the given solution already has x=y (the same number of blocks and sub-blocks), there is no better solution than the one given.


#13

Hmm…A base 10 system (1-9, 10,20-90) seems to be local minimum at 18 coins.
a base 9 system (1-8, 9,18,27…99) requires 19 coins as does a base 11 system (1-10,11,22,33…99) Which makes sense, since 100 is an even number in a base10 system.


#14

A quick google would suggest there are at least two 16 coin solutions possible. Not sure if it can go any lower than that though, and I’m not sure how they arrived at those solutions.

Like the first comment here, I immediately went to binary, before realizing that quickly fails.


#15

Dammit. I really wanted some 13-cent and 57-cent pieces.

Edit: I suck at math.


#16

Yeah, my brain keeps saying that, for the reasons I described, the given solution is the most efficient if duplicates are not allowed. It tells me that it’s possible that a more streamlined solution can be arrived that takes advantage of being able to use the same coin twice, but damned if I can figure out how.

Since when is 57 prime?


#17

Well, 13 is prime, so you need those 57-cent pieces, see? To get to 70?

</me pretending to be competent at math>


#18

Here’s a cute trick for multiples of 3 or 9…
If you add all of the digits of a number together and get a multiple of 3, the number is a multiple of 3.
Ditto for 9.

That’s how I knew right away that 57 wasn’t prime - the digits add to 12.


#19

Seems like something @nemomen should write a search algorithm for.


#20

If each side is worth a different amount?

I say this jokingly, but it makes me wonder if it is possible to devise coinage that changes value depending on what coin it is paired with. Financially stupid, but an interesting puzzle.