Using only 4$ and 7$ bills, you could pay any integer number of dollars, greater than 17.
Prove it.
Given two coprime numbers a and b, what is the minimal number M(a,b) such that any amount greater or equal to M(a,b) can be expressed as p*a+q*b (p & q non-negative integers)?
How much is M(37,38)?
1 = 2*4 - 1*7
For other ways of getting 1, we have to add or subtract as many times 7 4's as we subtract or add 4 7's respectively, since 7*4 = 4*7 and they cancel out if done with opposite sign. But if we add 4 7's, making +3 in all, we have to subtract 7 4's, making -5 in all, and we never get to non-negative for both.
For 17, it's 17 times the above, or 34 4's minus 17 7's. To make the number of 7's non-negative we need 5*4 added to the -17, making 3; but then the 5*7 we need to subtract from the number of 4's makes that count -1.
But from 18 onward there'll be sufficient leeway to get a non-negative answer.
It's best illustrated in the logic of the following program:
CLS
OPEN "generalize.txt" FOR OUTPUT AS #2
DEFDBL A-Z
FOR tot = 5 TO 80
FOR x = 2 TO tot / 2
y = tot - x
a = x: b = y
coa1 = 1: cob1 = 0
coa2 = 0: cob2 = 1
'PRINT a, coa1, cob1
'PRINT b, coa2, cob2
DO
prevr = r
q = a b: r = a MOD b
coa3 = coa1 - q * coa2: cob3 = cob1 - q * cob2
'PRINT r, coa3, cob3
coa1 = coa2: coa2 = coa3
cob1 = cob2: cob2 = cob3
a = b: b = r
LOOP UNTIL r = 0
IF prevr = 1 THEN
PRINT x; y,
PRINT #2, x; y,
FOR try = 1 TO 30 * tot
cx = try * coa1: cy = try * cob1
'PRINT , cx, cy
WHILE cx * cy < 0 AND cx * coa1 >= 0
cx = cx + coa2: cy = cy + cob2
WEND
IF cx < 0 OR cy < 0 THEN highest = try
NEXT
PRINT highest + 1
PRINT #2, highest + 1
END IF
NEXT x
NEXT tot
close 2
where the Euclidean algorithm finds the GCD and the coefficients needed to get there as well as the coefficients needed to balance out to zero. It attempts to form numbers much higher than is possible and keeps track of the highest non-formable number, and adds 1.
The results are shown below, but I can't see a general formula.
Here are specific answers, including M(4,7)=18 and M(37,38)=1332.
x y M(x,y)
2 3 2
2 5 4
3 4 6
3 5 8
2 7 6
4 5 12
3 7 12
2 9 8
3 8 14
4 7 18
5 6 20
5 7 24
2 11 10
3 10 18
4 9 24
5 8 28
6 7 30
3 11 20
5 9 32
2 13 12
4 11 30
7 8 42
3 13 24
5 11 40
7 9 48
2 15 14
3 14 26
4 13 36
5 12 44
6 11 50
7 10 54
8 9 56
5 13 48
7 11 60
2 17 16
3 16 30
4 15 42
5 14 52
6 13 60
7 12 66
8 11 70
9 10 72
3 17 32
7 13 72
9 11 80
2 19 18
4 17 48
5 16 60
8 13 84
10 11 90
3 19 36
5 17 64
7 15 84
9 13 96
2 21 20
3 20 38
4 19 54
5 18 68
6 17 80
7 16 90
8 15 98
9 14 104
10 13 108
11 12 110
5 19 72
7 17 96
11 13 120
2 23 22
3 22 42
4 21 60
6 19 90
7 18 102
8 17 112
9 16 120
11 14 130
12 13 132
3 23 44
5 21 80
7 19 108
9 17 128
11 15 140
2 25 24
4 23 66
5 22 84
7 20 114
8 19 126
10 17 144
11 16 150
13 14 156
3 25 48
5 23 88
9 19 144
11 17 160
13 15 168
2 27 26
3 26 50
4 25 72
5 24 92
6 23 110
7 22 126
8 21 140
9 20 152
10 19 162
11 18 170
12 17 176
13 16 180
14 15 182
7 23 132
11 19 180
13 17 192
2 29 28
3 28 54
4 27 78
5 26 100
6 25 120
7 24 138
8 23 154
9 22 168
10 21 180
11 20 190
12 19 198
13 18 204
14 17 208
15 16 210
3 29 56
5 27 104
7 25 144
9 23 176
11 21 200
13 19 216
15 17 224
2 31 30
4 29 84
5 28 108
7 26 150
8 25 168
10 23 198
13 20 228
14 19 234
16 17 240
3 31 60
5 29 112
7 27 156
9 25 192
11 23 220
13 21 240
15 19 252
2 33 32
3 32 62
4 31 90
6 29 140
8 27 182
9 26 200
11 24 230
12 23 242
13 22 252
16 19 270
17 18 272
5 31 120
7 29 168
11 25 240
13 23 264
17 19 288
2 35 34
3 34 66
4 33 96
5 32 124
6 31 150
7 30 174
8 29 196
9 28 216
10 27 234
11 26 250
12 25 264
13 24 276
14 23 286
15 22 294
16 21 300
17 20 304
18 19 306
3 35 68
5 33 128
7 31 180
9 29 224
11 27 260
13 25 288
15 23 308
17 21 320
2 37 36
4 35 102
5 34 132
7 32 186
8 31 210
10 29 252
11 28 270
14 25 312
16 23 330
17 22 336
19 20 342
3 37 72
7 33 192
9 31 240
11 29 280
13 27 312
17 23 352
19 21 360
2 39 38
3 38 74
4 37 108
5 36 140
6 35 170
7 34 198
8 33 224
9 32 248
10 31 270
11 30 290
12 29 308
13 28 324
14 27 338
15 26 350
16 25 360
17 24 368
18 23 374
19 22 378
20 21 380
5 37 144
11 31 300
13 29 336
17 25 384
19 23 396
2 41 40
3 40 78
4 39 114
5 38 148
6 37 180
7 36 210
8 35 238
9 34 264
10 33 288
11 32 310
12 31 330
13 30 348
14 29 364
15 28 378
16 27 390
17 26 400
18 25 408
19 24 414
20 23 418
21 22 420
3 41 80
5 39 152
7 37 216
9 35 272
13 31 360
15 29 392
17 27 416
19 25 432
21 23 440
2 43 42
4 41 120
7 38 222
8 37 252
11 34 330
13 32 372
14 31 390
16 29 420
17 28 432
19 26 450
22 23 462
3 43 84
5 41 160
7 39 228
9 37 288
11 35 340
13 33 384
15 31 420
17 29 448
19 27 468
21 25 480
2 45 44
3 44 86
4 43 126
5 42 164
6 41 200
7 40 234
8 39 266
9 38 296
10 37 324
11 36 350
12 35 374
13 34 396
14 33 416
15 32 434
16 31 450
17 30 464
18 29 476
19 28 486
20 27 494
21 26 500
22 25 504
23 24 506
5 43 168
7 41 240
11 37 360
13 35 408
17 31 480
19 29 504
23 25 528
2 47 46
3 46 90
4 45 132
5 44 172
6 43 210
8 41 280
9 40 312
10 39 342
11 38 370
12 37 396
13 36 420
15 34 462
16 33 480
17 32 496
18 31 510
19 30 522
20 29 532
22 27 546
23 26 550
24 25 552
3 47 92
7 43 252
9 41 320
11 39 380
13 37 432
17 33 512
19 31 540
21 29 560
23 27 572
2 49 48
4 47 138
5 46 180
7 44 258
8 43 294
10 41 360
11 40 390
13 38 444
14 37 468
16 35 510
19 32 558
20 31 570
22 29 588
23 28 594
25 26 600
3 49 96
5 47 184
7 45 264
9 43 336
11 41 400
15 37 504
17 35 544
19 33 576
21 31 600
23 29 616
25 27 624
2 51 50
3 50 98
4 49 144
5 48 188
6 47 230
7 46 270
8 45 308
9 44 344
10 43 378
11 42 410
12 41 440
13 40 468
14 39 494
15 38 518
16 37 540
17 36 560
18 35 578
19 34 594
20 33 608
21 32 620
22 31 630
23 30 638
24 29 644
25 28 648
26 27 650
5 49 192
7 47 276
11 43 420
13 41 480
17 37 576
19 35 612
23 31 660
25 29 672
2 53 52
3 52 102
4 51 150
6 49 240
7 48 282
8 47 322
9 46 360
12 43 462
13 42 492
14 41 520
16 39 570
17 38 592
18 37 612
19 36 630
21 34 660
23 32 682
24 31 690
26 29 700
27 28 702
3 53 104
5 51 200
9 47 368
11 45 440
13 43 504
15 41 560
17 39 608
19 37 648
23 33 704
25 31 720
27 29 728
2 55 54
4 53 156
5 52 204
7 50 294
8 49 336
10 47 414
11 46 450
13 44 516
14 43 546
16 41 600
17 40 624
20 37 684
22 35 714
23 34 726
25 32 744
26 31 750
28 29 756
3 55 108
5 53 208
7 51 300
9 49 384
11 47 460
13 45 528
15 43 588
17 41 640
19 39 684
21 37 720
23 35 748
25 33 768
27 31 780
2 57 56
3 56 110
4 55 162
5 54 212
6 53 260
7 52 306
8 51 350
9 50 392
10 49 432
11 48 470
12 47 506
13 46 540
14 45 572
15 44 602
16 43 630
17 42 656
18 41 680
19 40 702
20 39 722
21 38 740
22 37 756
23 36 770
24 35 782
25 34 792
26 33 800
27 32 806
28 31 810
29 30 812
7 53 312
11 49 480
13 47 552
17 43 672
19 41 720
23 37 792
29 31 840
2 59 58
3 58 114
4 57 168
5 56 220
6 55 270
7 54 318
8 53 364
9 52 408
10 51 450
11 50 490
12 49 528
13 48 564
14 47 598
15 46 630
16 45 660
17 44 688
18 43 714
19 42 738
20 41 760
21 40 780
22 39 798
23 38 814
24 37 828
25 36 840
26 35 850
27 34 858
28 33 864
29 32 868
30 31 870
3 59 116
5 57 224
7 55 324
9 53 416
11 51 500
13 49 576
15 47 644
17 45 704
19 43 756
21 41 800
23 39 836
25 37 864
27 35 884
29 33 896
2 61 60
4 59 174
5 58 228
8 55 378
10 53 468
11 52 510
13 50 588
16 47 690
17 46 720
19 44 774
20 43 798
22 41 840
23 40 858
25 38 888
26 37 900
29 34 924
31 32 930
3 61 120
5 59 232
7 57 336
9 55 432
11 53 520
13 51 600
15 49 672
17 47 736
19 45 792
21 43 840
23 41 880
25 39 912
27 37 936
29 35 952
31 33 960
2 63 62
3 62 122
4 61 180
6 59 290
7 58 342
8 57 392
9 56 440
11 54 530
12 53 572
14 51 650
16 49 720
17 48 752
18 47 782
19 46 810
21 44 860
22 43 882
23 42 902
24 41 920
27 38 962
28 37 972
29 36 980
31 34 990
32 33 992
5 61 240
7 59 348
13 53 624
17 49 768
19 47 828
23 43 924
25 41 960
29 37 1008
31 35 1020
2 65 64
3 64 126
4 63 186
5 62 244
6 61 300
7 60 354
8 59 406
9 58 456
10 57 504
11 56 550
12 55 594
13 54 636
14 53 676
15 52 714
16 51 750
17 50 784
18 49 816
19 48 846
20 47 874
21 46 900
22 45 924
23 44 946
24 43 966
25 42 984
26 41 1000
27 40 1014
28 39 1026
29 38 1036
30 37 1044
31 36 1050
32 35 1054
33 34 1056
3 65 128
5 63 248
7 61 360
9 59 464
11 57 560
13 55 648
15 53 728
19 49 864
21 47 920
23 45 968
25 43 1008
27 41 1040
29 39 1064
31 37 1080
33 35 1088
2 67 66
4 65 192
5 64 252
7 62 366
8 61 420
10 59 522
11 58 570
13 56 660
14 55 702
16 53 780
17 52 816
19 50 882
20 49 912
22 47 966
25 44 1032
26 43 1050
28 41 1080
29 40 1092
31 38 1110
32 37 1116
34 35 1122
3 67 132
9 61 480
11 59 580
13 57 672
17 53 832
19 51 900
23 47 1012
27 43 1092
29 41 1120
31 39 1140
33 37 1152
2 69 68
3 68 134
4 67 198
5 66 260
6 65 320
7 64 378
8 63 434
9 62 488
10 61 540
11 60 590
12 59 638
13 58 684
14 57 728
15 56 770
16 55 810
17 54 848
18 53 884
19 52 918
20 51 950
21 50 980
22 49 1008
23 48 1034
24 47 1058
25 46 1080
26 45 1100
27 44 1118
28 43 1134
29 42 1148
30 41 1160
31 40 1170
32 39 1178
33 38 1184
34 37 1188
35 36 1190
5 67 264
7 65 384
11 61 600
13 59 696
17 55 864
19 53 936
23 49 1056
25 47 1104
29 43 1176
31 41 1200
35 37 1224
2 71 70
3 70 138
4 69 204
5 68 268
6 67 330
7 66 390
8 65 448
9 64 504
10 63 558
11 62 610
12 61 660
13 60 708
14 59 754
15 58 798
16 57 840
17 56 880
18 55 918
19 54 954
20 53 988
21 52 1020
22 51 1050
23 50 1078
24 49 1104
25 48 1128
26 47 1150
27 46 1170
28 45 1188
29 44 1204
30 43 1218
31 42 1230
32 41 1240
33 40 1248
34 39 1254
35 38 1258
36 37 1260
3 71 140
5 69 272
7 67 396
9 65 512
11 63 620
13 61 720
15 59 812
17 57 896
19 55 972
21 53 1040
23 51 1100
25 49 1152
27 47 1196
29 45 1232
31 43 1260
33 41 1280
35 39 1292
2 73 72
4 71 210
7 68 402
8 67 462
11 64 630
13 62 732
14 61 780
16 59 870
17 58 912
19 56 990
22 53 1092
23 52 1122
26 49 1200
28 47 1242
29 46 1260
31 44 1290
32 43 1302
34 41 1320
37 38 1332
3 73 144
5 71 280
7 69 408
9 67 528
11 65 640
13 63 744
15 61 840
17 59 928
21 55 1080
23 53 1144
25 51 1200
27 49 1248
29 47 1288
31 45 1320
33 43 1344
35 41 1360
37 39 1368
2 75 74
3 74 146
4 73 216
5 72 284
6 71 350
8 69 476
9 68 536
10 67 594
12 65 704
13 64 756
15 62 854
16 61 900
17 60 944
18 59 986
19 58 1026
20 57 1064
23 54 1166
24 53 1196
25 52 1224
26 51 1250
27 50 1274
29 48 1316
30 47 1334
31 46 1350
32 45 1364
34 43 1386
36 41 1400
37 40 1404
38 39 1406
5 73 288
7 71 420
11 67 660
17 61 960
19 59 1044
23 55 1188
25 53 1248
29 49 1344
31 47 1380
35 43 1428
37 41 1440
2 77 76
3 76 150
4 75 222
5 74 292
6 73 360
7 72 426
8 71 490
9 70 552
10 69 612
11 68 670
12 67 726
13 66 780
14 65 832
15 64 882
16 63 930
17 62 976
18 61 1020
19 60 1062
20 59 1102
21 58 1140
22 57 1176
23 56 1210
24 55 1242
25 54 1272
26 53 1300
27 52 1326
28 51 1350
29 50 1372
30 49
|
|
Posted by Charlie
on 2013-05-01 18:00:54 |
part 1 solution, plus examples of M(x,y)
