# How to make 2 Euros with smaller coins

You are given n > 0 of each of the standard denomination Euro coins: 1 ct, 2 ct, 5 ct, 10 ct, 20 ct, 50 ct, 1 Euro, 2 Euro.

What is the smallest n such that it is impossible to select n coins that make exactly 2 Euros?

201

Proof by induction: Seed at n=1 in the obvious way. Let n be one less than the smallest impossible number. Then n admits a split. If that contains any of the 2p,10p,20p,1Eur,2Eur coins we can replace that with two of half its denomination, a contradiction. If it contains three ore more of either 5p or 50p we can replace them by 1p,2x2p,10p or 10p,2x20p,1Eur, respectively, contradiction. Otherwise we have max 2x5p + 2x50p and the rest must be 1p, at least 90 of them. If they are not all 1p, take a 50p and 2 1p and replace them with 2p + 10p +2x20p or a 5p and a 1p and replace them with 3x2p. $$\square$$

• The proof seems valid, but you don't seem to use the "obvious seed" in any way, and I really can't see any induction happening anywhere. Rather, you seem to be directly (non-inductively) deducing the necessary properties of any doable n where n+1 is impossible. – Bass Aug 20 '20 at 10:47
• @Bass If the seeding is superfluous, then please explain to me why the proof doesn't work unchanged for 1Eur 99p. – Paul Panzer Aug 20 '20 at 11:01
• Certainly the proof still applies, unchanged, to every doable n where n+1 is not doable. – Bass Aug 20 '20 at 11:19
• @Bass Let me rephrase: If the let's call it for no particular reason at all the step if it still works unchanged then why can't we draw the same unchanged conclusion? – Paul Panzer Aug 20 '20 at 11:37
• You know very well why you need to check n=1 in particular, you just don't bother to explain it in your answer, nor in any of your educational and most witty comments. n=1 is one of the boundary values where you might find the smallest impossible n, so you need to check that value in particular. Checking n=1 doesn't affect the neighbouring value of n=2 (or any other n) at all, so calling n=1 a "seed" is misleading at best. Hope this helps. – Bass Aug 20 '20 at 13:23

To demonstrate that Paul Panzer's accepted numeric answer is correct, here is a list of ways to select the coins.

The format is:
Total coins: (quantity x denomination) + (quantity x denomination) + ...

On each line, the math equals 2.00

1: (1 * 2.00)
2: (2 * 1.00)
3: (1 * 1.00) + (2 * 0.50)
4: (4 * 0.50)
5: (1 * 1.00) + (1 * 0.50) + (2 * 0.20) + (1 * 0.10)
6: (1 * 1.00) + (5 * 0.20)
7: (2 * 0.50) + (5 * 0.20)
8: (2 * 0.50) + (4 * 0.20) + (2 * 0.10)
9: (1 * 0.50) + (7 * 0.20) + (1 * 0.10)
10: (10 * 0.20)
11: (9 * 0.20) + (2 * 0.10)
12: (8 * 0.20) + (4 * 0.10)
13: (7 * 0.20) + (6 * 0.10)
14: (6 * 0.20) + (8 * 0.10)
15: (5 * 0.20) + (10 * 0.10)
16: (4 * 0.20) + (12 * 0.10)
17: (3 * 0.20) + (14 * 0.10)
18: (2 * 0.20) + (16 * 0.10)
19: (1 * 0.20) + (18 * 0.10)
20: (20 * 0.10)
21: (19 * 0.10) + (2 * 0.05)
22: (18 * 0.10) + (4 * 0.05)
23: (17 * 0.10) + (6 * 0.05)
24: (16 * 0.10) + (8 * 0.05)
25: (15 * 0.10) + (10 * 0.05)
26: (14 * 0.10) + (12 * 0.05)
27: (13 * 0.10) + (14 * 0.05)
28: (12 * 0.10) + (16 * 0.05)
29: (11 * 0.10) + (18 * 0.05)
30: (10 * 0.10) + (20 * 0.05)
31: (9 * 0.10) + (22 * 0.05)
32: (8 * 0.10) + (24 * 0.05)
33: (7 * 0.10) + (26 * 0.05)
34: (6 * 0.10) + (28 * 0.05)
35: (5 * 0.10) + (30 * 0.05)
36: (4 * 0.10) + (32 * 0.05)
37: (3 * 0.10) + (34 * 0.05)
38: (2 * 0.10) + (36 * 0.05)
39: (1 * 0.10) + (38 * 0.05)
40: (40 * 0.05)
41: (2 * 0.10) + (34 * 0.05) + (5 * 0.02)
42: (1 * 0.10) + (36 * 0.05) + (5 * 0.02)
43: (38 * 0.05) + (5 * 0.02)
44: (2 * 0.10) + (32 * 0.05) + (10 * 0.02)
45: (1 * 0.10) + (34 * 0.05) + (10 * 0.02)
46: (36 * 0.05) + (10 * 0.02)
47: (2 * 0.10) + (30 * 0.05) + (15 * 0.02)
48: (1 * 0.10) + (32 * 0.05) + (15 * 0.02)
49: (34 * 0.05) + (15 * 0.02)
50: (2 * 0.10) + (28 * 0.05) + (20 * 0.02)
51: (1 * 0.10) + (30 * 0.05) + (20 * 0.02)
52: (32 * 0.05) + (20 * 0.02)
53: (2 * 0.10) + (26 * 0.05) + (25 * 0.02)
54: (1 * 0.10) + (28 * 0.05) + (25 * 0.02)
55: (30 * 0.05) + (25 * 0.02)
56: (2 * 0.10) + (24 * 0.05) + (30 * 0.02)
57: (1 * 0.10) + (26 * 0.05) + (30 * 0.02)
58: (28 * 0.05) + (30 * 0.02)
59: (2 * 0.10) + (22 * 0.05) + (35 * 0.02)
60: (1 * 0.10) + (24 * 0.05) + (35 * 0.02)
61: (26 * 0.05) + (35 * 0.02)
62: (2 * 0.10) + (20 * 0.05) + (40 * 0.02)
63: (1 * 0.10) + (22 * 0.05) + (40 * 0.02)
64: (24 * 0.05) + (40 * 0.02)
65: (2 * 0.10) + (18 * 0.05) + (45 * 0.02)
66: (1 * 0.10) + (20 * 0.05) + (45 * 0.02)
67: (22 * 0.05) + (45 * 0.02)
68: (2 * 0.10) + (16 * 0.05) + (50 * 0.02)
69: (1 * 0.10) + (18 * 0.05) + (50 * 0.02)
70: (20 * 0.05) + (50 * 0.02)
71: (2 * 0.10) + (14 * 0.05) + (55 * 0.02)
72: (1 * 0.10) + (16 * 0.05) + (55 * 0.02)
73: (18 * 0.05) + (55 * 0.02)
74: (2 * 0.10) + (12 * 0.05) + (60 * 0.02)
75: (1 * 0.10) + (14 * 0.05) + (60 * 0.02)
76: (16 * 0.05) + (60 * 0.02)
77: (2 * 0.10) + (10 * 0.05) + (65 * 0.02)
78: (1 * 0.10) + (12 * 0.05) + (65 * 0.02)
79: (14 * 0.05) + (65 * 0.02)
80: (2 * 0.10) + (8 * 0.05) + (70 * 0.02)
81: (1 * 0.10) + (10 * 0.05) + (70 * 0.02)
82: (12 * 0.05) + (70 * 0.02)
83: (2 * 0.10) + (6 * 0.05) + (75 * 0.02)
84: (1 * 0.10) + (8 * 0.05) + (75 * 0.02)
85: (10 * 0.05) + (75 * 0.02)
86: (2 * 0.10) + (4 * 0.05) + (80 * 0.02)
87: (1 * 0.10) + (6 * 0.05) + (80 * 0.02)
88: (8 * 0.05) + (80 * 0.02)
89: (2 * 0.10) + (2 * 0.05) + (85 * 0.02)
90: (1 * 0.10) + (4 * 0.05) + (85 * 0.02)
91: (6 * 0.05) + (85 * 0.02)
92: (2 * 0.10) + (90 * 0.02)
93: (1 * 0.10) + (2 * 0.05) + (90 * 0.02)
94: (4 * 0.05) + (90 * 0.02)
95: (1 * 0.10) + (1 * 0.05) + (92 * 0.02) + (1 * 0.01)
96: (1 * 0.10) + (95 * 0.02)
97: (2 * 0.05) + (95 * 0.02)
98: (2 * 0.05) + (94 * 0.02) + (2 * 0.01)
99: (1 * 0.05) + (97 * 0.02) + (1 * 0.01)
100: (100 * 0.02)
101: (99 * 0.02) + (2 * 0.01)
102: (98 * 0.02) + (4 * 0.01)
103: (97 * 0.02) + (6 * 0.01)
104: (96 * 0.02) + (8 * 0.01)
105: (95 * 0.02) + (10 * 0.01)
106: (94 * 0.02) + (12 * 0.01)
107: (93 * 0.02) + (14 * 0.01)
108: (92 * 0.02) + (16 * 0.01)
109: (91 * 0.02) + (18 * 0.01)
110: (90 * 0.02) + (20 * 0.01)
111: (89 * 0.02) + (22 * 0.01)
112: (88 * 0.02) + (24 * 0.01)
113: (87 * 0.02) + (26 * 0.01)
114: (86 * 0.02) + (28 * 0.01)
115: (85 * 0.02) + (30 * 0.01)
116: (84 * 0.02) + (32 * 0.01)
117: (83 * 0.02) + (34 * 0.01)
118: (82 * 0.02) + (36 * 0.01)
119: (81 * 0.02) + (38 * 0.01)
120: (80 * 0.02) + (40 * 0.01)
121: (79 * 0.02) + (42 * 0.01)
122: (78 * 0.02) + (44 * 0.01)
123: (77 * 0.02) + (46 * 0.01)
124: (76 * 0.02) + (48 * 0.01)
125: (75 * 0.02) + (50 * 0.01)
126: (74 * 0.02) + (52 * 0.01)
127: (73 * 0.02) + (54 * 0.01)
128: (72 * 0.02) + (56 * 0.01)
129: (71 * 0.02) + (58 * 0.01)
130: (70 * 0.02) + (60 * 0.01)
131: (69 * 0.02) + (62 * 0.01)
132: (68 * 0.02) + (64 * 0.01)
133: (67 * 0.02) + (66 * 0.01)
134: (66 * 0.02) + (68 * 0.01)
135: (65 * 0.02) + (70 * 0.01)
136: (64 * 0.02) + (72 * 0.01)
137: (63 * 0.02) + (74 * 0.01)
138: (62 * 0.02) + (76 * 0.01)
139: (61 * 0.02) + (78 * 0.01)
140: (60 * 0.02) + (80 * 0.01)
141: (59 * 0.02) + (82 * 0.01)
142: (58 * 0.02) + (84 * 0.01)
143: (57 * 0.02) + (86 * 0.01)
144: (56 * 0.02) + (88 * 0.01)
145: (55 * 0.02) + (90 * 0.01)
146: (54 * 0.02) + (92 * 0.01)
147: (53 * 0.02) + (94 * 0.01)
148: (52 * 0.02) + (96 * 0.01)
149: (51 * 0.02) + (98 * 0.01)
150: (50 * 0.02) + (100 * 0.01)
151: (49 * 0.02) + (102 * 0.01)
152: (48 * 0.02) + (104 * 0.01)
153: (47 * 0.02) + (106 * 0.01)
154: (46 * 0.02) + (108 * 0.01)
155: (45 * 0.02) + (110 * 0.01)
156: (44 * 0.02) + (112 * 0.01)
157: (43 * 0.02) + (114 * 0.01)
158: (42 * 0.02) + (116 * 0.01)
159: (41 * 0.02) + (118 * 0.01)
160: (40 * 0.02) + (120 * 0.01)
161: (39 * 0.02) + (122 * 0.01)
162: (38 * 0.02) + (124 * 0.01)
163: (37 * 0.02) + (126 * 0.01)
164: (36 * 0.02) + (128 * 0.01)
165: (35 * 0.02) + (130 * 0.01)
166: (34 * 0.02) + (132 * 0.01)
167: (33 * 0.02) + (134 * 0.01)
168: (32 * 0.02) + (136 * 0.01)
169: (31 * 0.02) + (138 * 0.01)
170: (30 * 0.02) + (140 * 0.01)
171: (29 * 0.02) + (142 * 0.01)
172: (28 * 0.02) + (144 * 0.01)
173: (27 * 0.02) + (146 * 0.01)
174: (26 * 0.02) + (148 * 0.01)
175: (25 * 0.02) + (150 * 0.01)
176: (24 * 0.02) + (152 * 0.01)
177: (23 * 0.02) + (154 * 0.01)
178: (22 * 0.02) + (156 * 0.01)
179: (21 * 0.02) + (158 * 0.01)
180: (20 * 0.02) + (160 * 0.01)
181: (19 * 0.02) + (162 * 0.01)
182: (18 * 0.02) + (164 * 0.01)
183: (17 * 0.02) + (166 * 0.01)
184: (16 * 0.02) + (168 * 0.01)
185: (15 * 0.02) + (170 * 0.01)
186: (14 * 0.02) + (172 * 0.01)
187: (13 * 0.02) + (174 * 0.01)
188: (12 * 0.02) + (176 * 0.01)
189: (11 * 0.02) + (178 * 0.01)
190: (10 * 0.02) + (180 * 0.01)
191: (9 * 0.02) + (182 * 0.01)
192: (8 * 0.02) + (184 * 0.01)
193: (7 * 0.02) + (186 * 0.01)
194: (6 * 0.02) + (188 * 0.01)
195: (5 * 0.02) + (190 * 0.01)
196: (4 * 0.02) + (192 * 0.01)
197: (3 * 0.02) + (194 * 0.01)
198: (2 * 0.02) + (196 * 0.01)
199: (1 * 0.02) + (198 * 0.01)
200: (200 * 0.01)