8
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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$

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ – Bass Aug 20 '20 at 10:47
  • $\begingroup$ @Bass If the seeding is superfluous, then please explain to me why the proof doesn't work unchanged for 1Eur 99p. $\endgroup$ – Paul Panzer Aug 20 '20 at 11:01
  • $\begingroup$ Certainly the proof still applies, unchanged, to every doable n where n+1 is not doable. $\endgroup$ – Bass Aug 20 '20 at 11:19
  • $\begingroup$ @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? $\endgroup$ – Paul Panzer Aug 20 '20 at 11:37
  • $\begingroup$ 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. $\endgroup$ – Bass Aug 20 '20 at 13:23
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.