# 96 combinatorics/coinage/impossible.p

## Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

# 96 combinatorics/coinage/impossible.p

What is the smallest number of coins that you can't make a dollar with?
I.e., for what N does there not exist a set of N coins adding up to a dollar?
It is possible to make a dollar with 1 current U.S. coin (a Susan B. Anthony),
2 coins (2 fifty cent pieces), 3 coins (2 quarters and a fifty cent piece),
etc. It is not possible to make exactly a dollar with 101 coins.

combinatorics/coinage/impossible.s

The answer is 77:

a) 5c = 1 or 5;
b) 10c = 1 or 2 a's (1,2,6,10)
c) 25c = 1 or 2 b's + 1 a
d) 50c = 1 or 2 c's
e) \$1 = 1 or 2 d's

```total	penny	nickel	dime	quarter	half
5		1	2	1	1
6		3	1	1	1
7		5		1	1
8		4	3		1
9		6	2		1
10		8	1		1
11		10			1
12		7	4	1
13		9	3	1
14		11	2	1
15		13	1	1
16		15		1
17		14	3
18		16	2
19		18	1
20		20
21	5	13	3
22	5	15	2
23	5	17	1
24	5	19
25	10	12	3
26	10	14	2
27	10	16	1
28	10	18
29	15	11	3
30	15	13	2
31	15	15	1
32	15	17
33	20	10	3
34	20	12	2
35	20	14	1
36	20	16
37	25	9	3
38	25	11	2
39	25	13	1
40	25	15
41	30	8	3
42	30	10	2
43	30	12	1
44	30	14
45	35	7	3
46	35	9	2
47	35	11	1
48	35	13
49	40	6	3
50	40	8	2
51	40	10	1
52	40	12
53	45	5	3
54	45	7	2
55	45	9	1
56	45	11
57	50	4	3
58	50	6	2
59	50	8	1
60	50	10
61	55	3	3
62	55	5	2
63	55	7	1
64	55	9
65	60	2	3
66	60	4	2
67	60	6	1
68	60	8
69	65	1	3
70	65	3	2
71	65	5	1
72	65	7
73	70		3
74	70	2	2
75	70	4	1
76	70	6
77	can't be done
78	75	1	2
79	75	3	1
80	75	5
81	can't be done
82	80		2
83	80	2	1
84	80	4
85	can't be done
86	can't be done
87	85	1	1
88	85	3
89	can't be done
90	can't be done
91	90		1
92	90	2
93-95	can't be done
96	95	1
97-99	can't be done
100	100
```

Continue to: