Jump to content
BrainDen.com - Brain Teasers
  • 0


bonanova
 Share

Question

Recasting an old MG favorite: ;)

In the U.S. if you wanted to produce $.99, you'd need at least 8 coins;

$.49 would require at least 7 coins, and so on. Yesterday our President

declared that the current coin denominations of 50, 25, 10, 5 and 1 do

not constitute Change you can believe in, and ordered a new set of coins

to be minted.

I believe that any citizen of this country should be able to produce any

amount of money less than one dollar using at most two coins, he said.

And he challenged his greatest group of thinkers, the Brain Denizens,

to establish a set of coins that accomplishs this feat.

How many coin denominations will required?

Link to comment
Share on other sites

25 answers to this question

Recommended Posts

  • 0
Recasting an old MG favorite: ;)

In the U.S. if you wanted to produce $.99, you'd need at least 8 coins;

$.49 would require at least 7 coins, and so on. Yesterday our President

declared that the current coin denominations of 50, 25, 10, 5 and 1 do

not constitute Change you can believe in, and ordered a new set of coins

to be minted.

I believe that any citizen of this country should be able to produce any

amount of money less than one dollar using at most two coins, he said.

And he challenged his greatest group of thinkers, the Brain Denizens,

to establish a set of coins that accomplishs this feat.

How many coin denominations will required?

Eighteen

Link to comment
Share on other sites

  • 0

I'm sure it is probably

18

But maybe if you try a different way..

Do it in 10 coins..

coins can represent up to 10 cents.

A coin that is 1-10 cents.

11-20

21-30

31-40

41-50

51-60

61-70

71-80

81-90

91-99 (only one with 9 values)

So if you want something for 45 cents, you give them the 41-50 cent coin, now they owe you up to 5 cents, so they give you a 1-10 cent coin back. Could work if everyone believed in the system. :lol:;)

Link to comment
Share on other sites

  • 0
I'm sure it is probably

But maybe if you try a different way..

Do it in 10 coins..

coins can represent up to 10 cents.

A coin that is 1-10 cents.

11-20

21-30

31-40

41-50

51-60

61-70

71-80

81-90

91-99 (only one with 9 values)

So if you want something for 45 cents, you give them the 41-50 cent coin, now they owe you up to 5 cents, so they give you a 1-10 cent coin back. Could work if everyone believed in the system. :lol:;)

18

Genius!

Link to comment
Share on other sites

  • 0
I'm sure it is probably

But maybe if you try a different way..

Do it in 10 coins..

coins can represent up to 10 cents.

A coin that is 1-10 cents.

11-20

21-30

31-40

41-50

51-60

61-70

71-80

81-90

91-99 (only one with 9 values)

So if you want something for 45 cents, you give them the 41-50 cent coin, now they owe you up to 5 cents, so they give you a 1-10 cent coin back. Could work if everyone believed in the system. :lol:;)

18

if you were to do it like that it could be 2 coins. 1-49 and 50-99 or one coin 1-99

Link to comment
Share on other sites

  • 0
13:

1,2,3,4,5,16,27,38,49,60,71,82,93

1,2,3,4,5,6,19,32,45,58,71,84,97

1,2,3,4,5,6,7,22,37,52,67,82,97

1,2,3,4,5,6,7,8,25,42,59,76,93

1,2,3,4,5,6,7,8,9,28,47,66,85

For your first set you can't make 13-15 in 3 coins...

For your second set you can't make 16-18 in 3 coins...

For your third set you can't make 18-21 in 3 coins...

For your forth set you can't make 22-24 in 3 coins...

and your fifth set you can't make 25-27 in 3 coins...

I'm goin' w/ 14 coins for sets of 3...(the 1-5, and then by 10's as stated above)

Link to comment
Share on other sites

  • 0
13:

1,2,3,4,5,16,27,38,49,60,71,82,93

1,2,3,4,5,6,19,32,45,58,71,84,97

1,2,3,4,5,6,7,22,37,52,67,82,97

1,2,3,4,5,6,7,8,25,42,59,76,93

1,2,3,4,5,6,7,8,9,28,47,66,85

yup 13. thanks man

Link to comment
Share on other sites

  • 0
yup 13. thanks man

If you only allow 2 coins, then the set {1 2 3 4 8 13 16} can get up to 21.

{1,2,3,4,4+1,4+2,4+3,8,8+1,8+2,8+3,8+4,13,13+1,13+2,16,16+1,16+2,16+3,16+4,13+8}

Using this same set but allowing 3 coins allows up to 37.

{...,13+8+1,13+8+2,13+8+3,13+8+4,16+8+2,16+8+3,16+8+4,13+16,13+16+1,13+16+2,13+1

6+3,13+16+4,16+16+2,16+16+3,16+16+4,16+13+8}

So now we can add 38, 60, and 82. Since these are each separated by 22 we can use the 2 coin combinations above to reach between them.

So my final set is {1,2,3,4,8,13,16,38,60,82}, which only has 10 elements.

Link to comment
Share on other sites

  • 0
For your first set you can't make 13-15 in 3 coins...

For your second set you can't make 16-18 in 3 coins...

For your third set you can't make 18-21 in 3 coins...

For your forth set you can't make 22-24 in 3 coins...

and your fifth set you can't make 25-27 in 3 coins...

I'm goin' w/ 14 coins for sets of 3...(the 1-5, and then by 10's as stated above)

Look closer all my combo's work. However look below you can do it in less:

If you only allow 2 coins, then the set {1 2 3 4 8 13 16} can get up to 21.

{1,2,3,4,4+1,4+2,4+3,8,8+1,8+2,8+3,8+4,13,13+1,13+2,16,16+1,16+2,16+3,16+4,13+8}

Using this same set but allowing 3 coins allows up to 37.

{...,13+8+1,13+8+2,13+8+3,13+8+4,16+8+2,16+8+3,16+8+4,13+16,13+16+1,13+16+2,13+1

6+3,13+16+4,16+16+2,16+16+3,16+16+4,16+13+8}

So now we can add 38, 60, and 82. Since these are each separated by 22 we can use the 2 coin combinations above to reach between them.

So my final set is {1,2,3,4,8,13,16,38,60,82}, which only has 10 elements.

Awesome! You're right as far as I can tell! Makes me wonder if it can be less though.

Link to comment
Share on other sites

  • 0

As the President looked over the evening mail he was heard to exclaim:

Eighteen? Are you kidding me? Dick Cheney gave me 18!

The best he got was 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90.

No one can do better?

The two coins don't have to have different values.

Link to comment
Share on other sites

  • 0
As the President looked over the evening mail he was heard to exclaim:

Eighteen? Are you kidding me? Dick Cheney gave me 18!

The best he got was 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90.

No one can do better?

The two coins don't have to have different values.

If by 2 coins he means 2 different coins, but however many of each, I'll say a penny and a dime. You can make any change with a penny and a dime. Or a penny and nickel too I suppose. Or just mint pennies only.

:P

A simpler version of my earlier post...

Use 9 coins:

On the heads side call each one 1cent,2cents...9cents.

On the tails side call it 10cents,20cents...,90cents.

So you could make any change using 2 coins depending on which side is showing.(I think George Bush just might fall for this. (No offense George Bush) :lol: )

:P:P I don't know...18? :lol:
Link to comment
Share on other sites

  • 0
As the President looked over the evening mail he was heard to exclaim:

Eighteen? Are you kidding me? Dick Cheney gave me 18!

The best he got was 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90.

No one can do better?

The two coins don't have to have different values.

I can make many other combinations that work for 18 coins but have yet to find one smaller. I don't doubt it exists but it's escaping me.

Link to comment
Share on other sites

  • 0
I see it but how on earth did you come up with it?

Sloane's told me the minimum number of denominations was 16. With 16 demoninations you can obtain a value of $1.04. Starting with their solution for 20 denominations as a base, another set would be

Spoiler for this:

1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52
which gives their max of $1.04. I like the first one I posted better since it stops right at 1 dollar.
Link to comment
Share on other sites

  • 0

I wrote some code (included below), and used it to verify that there is no 15 coin solution. I then made it work for more than 2 coins, and here are the results (including the "best" solution... the one that allows combining to reach all numbers up to a highest maximum):

2: 16 denominations. Still running, and I don't expect it to finish this week.

3: 9 denominations == 1 3 8 9 14 32 36 51 53 (up to 121) Computed in 4787 seconds.

4: 6 denominations == 1 4 9 16 38 49 (up to 108). Computed in 20 seconds.

5: 5 denominations == 1 4 9 31 51 (up to 126). Computed in 3 seconds.

6: 4 denominations == 1 4 19 33 (up to 114). Computed in under a second.

7: 4 denominations == 1 5 24 37 (up to 165). Computed in 4 seconds.

8: 4 denominations == 1 6 25 65 (up to 234). Computed in 30 seconds.

9: 3 denominations == 1 9 20 (up to 112). Computed in under a second.

10: 3 denominations == 1 10 26 (up to 146). Computed in under a second.


#include <iostream>
#include <windows.h>
#include <winbase.h>
#include <time.h>

using namespace std;

//////////////////////these are the variables to play with
//max number of coins to add together
int maxnum = 2;
//max target value
int maxt = 99;
//////////////////////

//amount to sleep each second (in milliseconds) -- to control cpu% used
#define sleepamount 400
//max number of denominations to test
#define maxcoins 50

int coins[maxcoins];//denomiation values
int numcoins=0; // one less than the first number of denominations you want to check
int stack[50];//used to check all combinations of denominations
int totals[50];
int best[maxcoins];//store the best set found
int bestscore = 0;

int main(int argc, char* argv[])
{
if (argc>1) maxt = atoi(argv[1]);
if (argc>2) maxnum = atoi(argv[2]);
if (argc>3) numcoins = atoi(argv[3])-1;

memset(best,0,sizeof(int)*maxcoins);
int done = 0;
int starttime = (int)time(0);
int lasttime = starttime;

while(!done)
{
numcoins++;
if (numcoins > maxcoins) break;
cout << "Testing " << numcoins << " coins." << endl;
for(int i = 0; i < numcoins; i++) coins[i] = i+1;
int next = maxt;
for(int i = numcoins-1; i >= 0; i--)//make sure large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}
if (coins[0] != 1) cout << "Target max definitely not reachable." << endl;

while(coins[0] == 1)//smallest denomination must be 1
{
if ((int)time(0)!=lasttime){Sleep(sleepamount);lasttime = (int)time(0);}

///check each target value up to maxt
int target=0;
while(1)
{
target++;
//try all combinations of coins to reach the target
int last = numcoins-1;
while(coins[last]>target)last--;
if (coins[last]==target)continue;
int foundtarget = 0;
int depth = 0;
stack[0] = -1;
while(depth >= 0)
{
stack[depth]++;
if (stack[depth]>last) {depth--; continue;}
int total = 0;
if (depth) total = totals[depth-1];
totals[depth] = total+coins[stack[depth]];
if (totals[depth]==target) {foundtarget = 1; break;}
if (totals[depth] > target) {depth--; continue;}
if (depth < maxnum-1) {depth++; stack[depth]=-1;}
}
if (!foundtarget) break;
}

if (target-1 > bestscore)
{
memcpy(best,coins,sizeof(int)*numcoins);
bestscore = target-1;
}

if (target >= maxt+1)
{
cout << endl;
for(int i = 0; i < numcoins; i++) cout << coins[i] << " ";
cout << " (up to " << target-1 << ") ";
done = 1;
//break; //add in this break to stop when first answer is found
}

///increment denominations
int index = numcoins-1;
while(coins[index] >= target) index--;
while(index && (coins[index]>=coins[index-1]*maxnum+1)) index--;
while(index && (coins[index]>=maxt-((numcoins-1)-index))) index--;
coins[index]++;
for(int i = index+1; i < numcoins; i++) coins[i] = coins[i-1]+1;
next = maxt;

for(int i = numcoins-1; i >= 0; i--)//make sure the large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}

//stuff to let me know it's still working
if ((index < numcoins-6)&&(!done)) cout << index << ",";
if ((index < numcoins-8)&&(!done)) cout << endl << "Time elapsed = " << ((int)time(0))-starttime << endl;
}
if (bestscore)
{
cout << endl << "Best for " << numcoins << " was " << bestscore << " = ";
for(int i = 0; i < numcoins; i++) cout << best[i] << " ";
cout << endl << endl;
}
//break;//remove this break to keep adding to the number of denominations until an answer is found
}
int endtime = (int)time(0);
cout << endl << "Finished in " << endtime-starttime << " seconds" << endl;
system("pause");
return 0;
}
#include <stdio.h>

Link to comment
Share on other sites

  • 0
I wrote some code (included below), and used it to verify that there is no 15 coin solution. I then made it work for more than 2 coins, and here are the results (including the "best" solution... the one that allows combining to reach all numbers up to a highest maximum):

2: 16 denominations. Still running, and I don't expect it to finish this week.

3: 9 denominations == 1 3 8 9 14 32 36 51 53 (up to 121) Computed in 4787 seconds.

4: 6 denominations == 1 4 9 16 38 49 (up to 108). Computed in 20 seconds.

5: 5 denominations == 1 4 9 31 51 (up to 126). Computed in 3 seconds.

6: 4 denominations == 1 4 19 33 (up to 114). Computed in under a second.

7: 4 denominations == 1 5 24 37 (up to 165). Computed in 4 seconds.

8: 4 denominations == 1 6 25 65 (up to 234). Computed in 30 seconds.

9: 3 denominations == 1 9 20 (up to 112). Computed in under a second.

10: 3 denominations == 1 10 26 (up to 146). Computed in under a second.


#include <iostream>
#include <windows.h>
#include <winbase.h>
#include <time.h>

using namespace std;

//////////////////////these are the variables to play with
//max number of coins to add together
int maxnum = 2;
//max target value
int maxt = 99;
//////////////////////

//amount to sleep each second (in milliseconds) -- to control cpu% used
#define sleepamount 400
//max number of denominations to test
#define maxcoins 50

int coins[maxcoins];//denomiation values
int numcoins=0; // one less than the first number of denominations you want to check
int stack[50];//used to check all combinations of denominations
int totals[50];
int best[maxcoins];//store the best set found
int bestscore = 0;

int main(int argc, char* argv[])
{
if (argc>1) maxt = atoi(argv[1]);
if (argc>2) maxnum = atoi(argv[2]);
if (argc>3) numcoins = atoi(argv[3])-1;

memset(best,0,sizeof(int)*maxcoins);
int done = 0;
int starttime = (int)time(0);
int lasttime = starttime;

while(!done)
{
numcoins++;
if (numcoins > maxcoins) break;
cout << "Testing " << numcoins << " coins." << endl;
for(int i = 0; i < numcoins; i++) coins[i] = i+1;
int next = maxt;
for(int i = numcoins-1; i >= 0; i--)//make sure large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}
if (coins[0] != 1) cout << "Target max definitely not reachable." << endl;

while(coins[0] == 1)//smallest denomination must be 1
{
if ((int)time(0)!=lasttime){Sleep(sleepamount);lasttime = (int)time(0);}

///check each target value up to maxt
int target=0;
while(1)
{
target++;
//try all combinations of coins to reach the target
int last = numcoins-1;
while(coins[last]>target)last--;
if (coins[last]==target)continue;
int foundtarget = 0;
int depth = 0;
stack[0] = -1;
while(depth >= 0)
{
stack[depth]++;
if (stack[depth]>last) {depth--; continue;}
int total = 0;
if (depth) total = totals[depth-1];
totals[depth] = total+coins[stack[depth]];
if (totals[depth]==target) {foundtarget = 1; break;}
if (totals[depth] > target) {depth--; continue;}
if (depth < maxnum-1) {depth++; stack[depth]=-1;}
}
if (!foundtarget) break;
}

if (target-1 > bestscore)
{
memcpy(best,coins,sizeof(int)*numcoins);
bestscore = target-1;
}

if (target >= maxt+1)
{
cout << endl;
for(int i = 0; i < numcoins; i++) cout << coins[i] << " ";
cout << " (up to " << target-1 << ") ";
done = 1;
//break; //add in this break to stop when first answer is found
}

///increment denominations
int index = numcoins-1;
while(coins[index] >= target) index--;
while(index && (coins[index]>=coins[index-1]*maxnum+1)) index--;
while(index && (coins[index]>=maxt-((numcoins-1)-index))) index--;
coins[index]++;
for(int i = index+1; i < numcoins; i++) coins[i] = coins[i-1]+1;
next = maxt;

for(int i = numcoins-1; i >= 0; i--)//make sure the large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}

//stuff to let me know it's still working
if ((index < numcoins-6)&&(!done)) cout << index << ",";
if ((index < numcoins-8)&&(!done)) cout << endl << "Time elapsed = " << ((int)time(0))-starttime << endl;
}
if (bestscore)
{
cout << endl << "Best for " << numcoins << " was " << bestscore << " = ";
for(int i = 0; i < numcoins; i++) cout << best[i] << " ";
cout << endl << endl;
}
//break;//remove this break to keep adding to the number of denominations until an answer is found
}
int endtime = (int)time(0);
cout << endl << "Finished in " << endtime-starttime << " seconds" << endl;
system("pause");
return 0;
}
#include <stdio.h>

All possible solutions to the original problem are the following:

1 2 3 7 11 15 19 23 27 28 29 30 60 63 66 69 (up to 99)

1 2 3 7 11 15 19 23 27 28 29 30 61 64 67 70 (up to 100)

1 3 4 5 8 14 20 26 32 35 41 45 46 48 49 53 (up to 99)

1 3 4 5 8 14 20 26 32 38 41 43 46 47 48 51 (up to 99)

1 3 4 5 8 14 20 26 32 38 41 45 46 48 49 85 (up to 99)

1 3 4 5 8 14 20 26 32 38 43 44 46 47 48 51 (up to 99)

1 3 4 5 8 14 20 26 32 38 44 45 47 48 49 52 (up to 101)

1 3 4 5 8 14 20 26 32 38 44 46 47 48 49 51 (up to 100)

1 3 4 5 8 14 20 26 32 38 44 46 48 49 51 53 (up to 102)

1 3 4 5 8 14 20 26 32 38 44 47 48 49 51 52 (up to 104) **best one

1 3 4 6 10 14 18 22 26 28 29 31 61 62 67 68 (up to 99)

1 3 4 7 8 9 16 17 21 24 35 46 57 68 79 90 (up to 100)

1 3 4 9 11 16 20 25 30 34 39 41 46 47 49 50 (up to 100)

1 3 5 6 10 14 18 22 26 28 29 31 61 62 67 68 (up to 99)

It took 1106776 seconds (12.8 days) to finish.

Link to comment
Share on other sites

  • 0

Not sure anyone is interested... but here it is anyway.

what took my old version 4787 seconds (solving the 3 coin problem), now takes 891 seconds. So perhaps solving the 2 coin problem will only take 3 days instead of 2 weeks.


#include <iostream>
#include <windows.h>
#include <winbase.h>
#include <time.h>

using namespace std;

//////////////////////these are the variables to play with
//max number of coins to add together
int maxnum = 2;
//max target value
int maxt = 99;
//////////////////////

//amount to sleep each second (in milliseconds) -- to control cpu% used
#define sleepamount 400
//max number of denominations to test
#define maxcoins 50

int coins[maxcoins];//denomiation values
int numcoins=0; // one less than the first number of denominations you want to check
int stack[50];//used to check all combinations of denominations
int totals[50];
int best[maxcoins];//store the best set found
int bestscore = 0;
int lastindex = 1;
int startt[maxcoins];

int main(int argc, char* argv[])
{
if (argc>1) maxt = atoi(argv[1]);
if (argc>2) maxnum = atoi(argv[2]);
if (argc>3) numcoins = atoi(argv[3])-1;

memset(best,0,sizeof(int)*maxcoins);
int done = 0;
int starttime = (int)time(0);
int lasttime = starttime;

startt[0] = maxnum;
lastindex = 1;
while(!done)
{
numcoins++;
if (numcoins > maxcoins) break;
cout << "Testing " << numcoins << " coins." << endl;
for(int i = 0; i < numcoins; i++) coins[i] = i+1;
int next = maxt;
for(int i = numcoins-1; i >= 0; i--)//make sure large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}
if (coins[0] != 1) cout << "Target max definitely not reachable." << endl;

int target;
while(coins[0] == 1)//smallest denomination must be 1
{
if ((int)time(0)!=lasttime){Sleep(sleepamount);lasttime = (int)time(0);}

///check each target value up to maxt

target=startt[lastindex-1];
int tochange = lastindex;
while(1)
{
target++;
//try all combinations of coins to reach the target
int last = numcoins-1;
while(coins[last]>target)last--;
//if (coins[last]==target)continue;
int foundtarget = 0;
int depth = 0;
stack[0] = -1;
while(depth >= 0)
{
stack[depth]++;
int total = 0;
if (depth)
{
if (stack[depth]>stack[depth-1]) {depth--; continue;}
total = totals[depth-1];
}
else
{
if (stack[depth]>last) {depth--; continue;}
}
totals[depth] = total+coins[stack[depth]];
if (totals[depth]==target) {foundtarget = 1; break;}
if (totals[depth] > target) {depth--; continue;}
if (depth < maxnum-1) {depth++; stack[depth]=-1;}
}

if (!foundtarget)
{
while (tochange < numcoins)
{
startt[tochange++] = target-1;
}
break;
}
else
{
while (stack[0] > tochange)
{
startt[tochange++] = target-1;
}
}
}

if (target-1 > bestscore)
{
memcpy(best,coins,sizeof(int)*numcoins);
bestscore = target-1;
}

if (target >= maxt+1)
{
cout << endl;
for(int i = 0; i < numcoins; i++) cout << coins[i] << " ";
cout << " (up to " << target-1 << ") ";
done = 1;
//break; //add in this break to stop when first answer is found
}

///increment denominations
int index = numcoins-1;
while(coins[index] >= target) index--;
while(index && (coins[index]>=coins[index-1]*maxnum+1)) index--;
while(index && (coins[index]>=maxt-((numcoins-1)-index))) index--;
lastindex = index;
coins[index]++;
for(int i = index+1; i < numcoins; i++) coins[i] = coins[i-1]+1;
next = maxt;

for(int i = numcoins-1; i >= 0; i--)//make sure the large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}

//stuff to let me know it's still working
if ((index < numcoins-6)&&(!done)) cout << index << ",";
if ((index < numcoins-8)&&(!done)) cout << endl << "Time elapsed = " << ((int)time(0))-starttime << endl;
}
if (bestscore)
{
cout << endl << "Best for " << numcoins << " was " << bestscore << " = ";
for(int i = 0; i < numcoins; i++) cout << best[i] << " ";
cout << endl << endl;
}
//break;//remove this break to keep adding to the number of denominations until an answer is found
}
int endtime = (int)time(0);
cout << endl << "Finished in " << endtime-starttime << " seconds" << endl;
system("pause");
return 0;
}
#include <stdio.h>

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...