Thread Rating:

Poll

10 votes (45.45%)
9 votes (40.9%)
5 votes (22.72%)
2 votes (9.09%)
7 votes (31.81%)
3 votes (13.63%)
4 votes (18.18%)
3 votes (13.63%)
9 votes (40.9%)
6 votes (27.27%)

22 members have voted

gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 44
  • Posts: 2809
February 26th, 2021 at 7:18:25 PM permalink
Quote: teliot

On the topic of Golfing, let me create a different problem that is based on efficient stamp totals.

Suppose the Post Office issues two values of stamps X cents and Y cents. What are the most efficient values for these two stamps X & Y so that we can make each postage from $1.20 to $2.00, using the least number of stamps overall?

Yeah, "Easy" Math Puzzles. :)





My quick guess is 12 cents and 11 cents.

We need two numbers -one, call it n, that is even and the other that has multiples that are capable of making xmodn, x=1...n-1.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2159
February 26th, 2021 at 9:46:02 PM permalink
Quote: gordonm888



My quick guess is 12 cents and 11 cents.

We need two numbers -one, call it n, that is even and the other that has multiples that are capable of making xmodn, x=1...n-1.

Your answer requires a total of 1118 stamps. My answer requires 1072 stamps.
Personal website: www.ijmp.org
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 33
  • Posts: 2322
February 27th, 2021 at 1:34:02 AM permalink
Quote: teliot

...My answer requires 1072 stamps.

I think you accidentally (or not) gave a hint earlier as 120 = (13-1)*(11-1) and both 13 and 11 are primes; and they seem to work. The early values can be achieved in either 10 or 11 stamps, e.g 120 = 5*each, 121=11*11c, 122 is 4*11c+6*13c, so to get 2 more you replace one 11 with a 13. At the end 199 needs 17 stamps, and 200 (which is 208-8 so 12*13+4*11 requires 16 stamps.) The total is 1072.
teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2159
February 27th, 2021 at 6:04:09 AM permalink
Quote: charliepatrick

I think you accidentally (or not) gave a hint earlier as 120 = (13-1)*(11-1) and both 13 and 11 are primes; and they seem to work. The early values can be achieved in either 10 or 11 stamps, e.g 120 = 5*each, 121=11*11c, 122 is 4*11c+6*13c, so to get 2 more you replace one 11 with a 13. At the end 199 needs 17 stamps, and 200 (which is 208-8 so 12*13+4*11 requires 16 stamps.) The total is 1072.

Yes!

Now, what's the answer if we also need to make a postage of $1.19? This is where it gets slightly evil.


1, 2, Total = 6560
1, 3, Total = 4415
1, 4, Total = 3362
1, 5, Total = 2747
1, 6, Total = 2349
1, 7, Total = 2075
1, 8, Total = 1886
1, 9, Total = 1743
1, 10, Total = 1640
1, 11, Total = 1559
1, 12, Total = 1496
1, 13, Total = 1451
1, 14, Total = 1431
1, 15, Total = 1389
1, 16, Total = 1394
1, 17, Total = 1367
1, 18, Total = 1400
1, 19, Total = 1379
1, 20, Total = 1394
1, 21, Total = 1399
1, 22, Total = 1445
1, 23, Total = 1419
1, 24, Total = 1395
1, 25, Total = 1511
1, 26, Total = 1504
1, 27, Total = 1509
1, 28, Total = 1550
1, 29, Total = 1571
1, 30, Total = 1508
1, 31, Total = 1559
1, 32, Total = 1640
1, 33, Total = 1751
1, 34, Total = 1793
1, 35, Total = 1757
1, 36, Total = 1739
1, 37, Total = 1739
1, 38, Total = 1757
1, 39, Total = 1793
1, 40, Total = 1886
1, 41, Total = 1919
1, 42, Total = 1927
1, 43, Total = 1949
1, 44, Total = 1985
1, 45, Total = 2035
1, 46, Total = 2099
1, 47, Total = 2177
1, 48, Total = 2269
1, 49, Total = 2375
1, 50, Total = 2495
1, 51, Total = 2479
1, 52, Total = 2420
1, 53, Total = 2367
1, 54, Total = 2320
1, 55, Total = 2279
1, 56, Total = 2244
1, 57, Total = 2215
1, 58, Total = 2192
1, 59, Total = 2175
1, 60, Total = 2223
1, 61, Total = 2339
1, 62, Total = 2465
1, 63, Total = 2601
1, 64, Total = 2747
1, 65, Total = 2903
1, 66, Total = 3069
1, 67, Total = 3245
1, 68, Total = 3230
1, 69, Total = 3219
1, 70, Total = 3212
1, 71, Total = 3209
1, 72, Total = 3210
1, 73, Total = 3215
1, 74, Total = 3224
1, 75, Total = 3237
1, 76, Total = 3254
1, 77, Total = 3275
1, 78, Total = 3300
1, 79, Total = 3329
1, 80, Total = 3362
1, 81, Total = 3399
1, 82, Total = 3440
1, 83, Total = 3485
1, 84, Total = 3534
1, 85, Total = 3587
1, 86, Total = 3644
1, 87, Total = 3705
1, 88, Total = 3770
1, 89, Total = 3839
1, 90, Total = 3912
1, 91, Total = 3989
1, 92, Total = 4070
1, 93, Total = 4155
1, 94, Total = 4244
1, 95, Total = 4337
1, 96, Total = 4434
1, 97, Total = 4535
1, 98, Total = 4640
1, 99, Total = 4749
1, 100, Total = 4862
1, 101, Total = 4879
1, 102, Total = 4797
1, 103, Total = 4715
1, 104, Total = 4633
1, 105, Total = 4551
1, 106, Total = 4469
1, 107, Total = 4387
1, 108, Total = 4305
1, 109, Total = 4223
1, 110, Total = 4141
1, 111, Total = 4059
1, 112, Total = 3977
1, 113, Total = 3895
1, 114, Total = 3813
1, 115, Total = 3731
1, 116, Total = 3649
1, 117, Total = 3567
1, 118, Total = 3485
1, 119, Total = 3403
2, 3, Total = 4387
2, 5, Total = 2713
2, 7, Total = 2042
2, 9, Total = 1706
2, 11, Total = 1522
2, 13, Total = 1419
2, 15, Total = 1359
2, 17, Total = 1342
2, 19, Total = 1346
2, 21, Total = 1362
2, 23, Total = 1384
2, 25, Total = 1445
2, 27, Total = 1477
2, 29, Total = 1531
2, 31, Total = 1537
2, 33, Total = 1657
2, 35, Total = 1705
2, 37, Total = 1727
2, 39, Total = 1785
2, 41, Total = 1879
2, 43, Total = 1927
2, 45, Total = 2003
2, 47, Total = 2107
2, 49, Total = 2239
2, 51, Total = 2350
2, 53, Total = 2332
2, 55, Total = 2326
2, 57, Total = 2332
2, 59, Total = 2350
2, 61, Total = 2439
2, 63, Total = 2605
2, 65, Total = 2791
2, 67, Total = 2997
2, 69, Total = 3022
2, 71, Total = 3055
2, 73, Total = 3096
2, 75, Total = 3145
2, 77, Total = 3202
2, 79, Total = 3267
2, 81, Total = 3340
2, 83, Total = 3421
2, 85, Total = 3510
2, 87, Total = 3607
2, 89, Total = 3712
2, 91, Total = 3825
2, 93, Total = 3946
2, 95, Total = 4075
2, 97, Total = 4212
2, 99, Total = 4357
2, 101, Total = 4510
2, 103, Total = 4469
2, 105, Total = 4428
2, 107, Total = 4387
2, 109, Total = 4346
2, 111, Total = 4305
2, 113, Total = 4264
2, 115, Total = 4223
2, 117, Total = 4182
2, 119, Total = 4141
3, 4, Total = 3300
3, 5, Total = 2681
3, 7, Total = 2009
3, 8, Total = 1813
3, 10, Total = 1562
3, 11, Total = 1485
3, 13, Total = 1383
3, 14, Total = 1353
3, 16, Total = 1322
3, 17, Total = 1303
3, 19, Total = 1309
3, 20, Total = 1311
3, 22, Total = 1345
3, 23, Total = 1353
3, 25, Total = 1397
3, 26, Total = 1408
3, 28, Total = 1468
3, 29, Total = 1491
3, 31, Total = 1513
3, 32, Total = 1566
3, 34, Total = 1642
3, 35, Total = 1661
3, 37, Total = 1685
3, 38, Total = 1723
3, 40, Total = 1782
3, 41, Total = 1839
3, 43, Total = 1893
3, 44, Total = 1927
3, 46, Total = 2009
3, 47, Total = 2057
3, 49, Total = 2167
3, 50, Total = 2229
3, 52, Total = 2269
3, 53, Total = 2293
3, 55, Total = 2297
3, 56, Total = 2328
3, 58, Total = 2343
3, 59, Total = 2381
4, 5, Total = 2648
4, 7, Total = 1973
4, 9, Total = 1636
4, 11, Total = 1448
4, 13, Total = 1346
4, 15, Total = 1287
4, 17, Total = 1271
4, 19, Total = 1271
4, 21, Total = 1285
4, 23, Total = 1308
4, 25, Total = 1343
4, 27, Total = 1401
4, 29, Total = 1451
4, 31, Total = 1481
4, 33, Total = 1566
4, 35, Total = 1619
4, 37, Total = 1661
4, 39, Total = 1721
5, 6, Total = 2214
5, 7, Total = 1939
5, 8, Total = 1741
5, 9, Total = 1599
5, 11, Total = 1411
5, 12, Total = 1353
5, 13, Total = 1307
5, 14, Total = 1282
5, 16, Total = 1243
5, 17, Total = 1231
5, 18, Total = 1230
5, 19, Total = 1227
5, 21, Total = 1243
5, 22, Total = 1266
5, 23, Total = 1273
5, 24, Total = 1282
5, 26, Total = 1339
5, 27, Total = 1353
5, 28, Total = 1383
5, 29, Total = 1411
6, 7, Total = 1904
6, 11, Total = 1374
6, 13, Total = 1271
6, 17, Total = 1188
6, 19, Total = 1194
6, 23, Total = 1242
7, 8, Total = 1670
7, 9, Total = 1527
7, 10, Total = 1418
7, 11, Total = 1337
7, 12, Total = 1277
7, 13, Total = 1235
7, 15, Total = 1177
7, 16, Total = 1160
7, 17, Total = 1157
7, 18, Total = 1155
7, 19, Total = 1157
7, 20, Total = 1159
8, 9, Total = 1490
8, 11, Total = 1300
8, 13, Total = 1198
8, 15, Total = 1137
8, 17, Total = 1123
9, 10, Total = 1344
9, 11, Total = 1263
9, 13, Total = 1159
9, 14, Total = 1121
10, 11, Total = 1226
10, 13, Total = 1121
11, 12, Total = 1128
Last edited by: teliot on Feb 27, 2021
Personal website: www.ijmp.org
ThatDonGuy
ThatDonGuy 
Joined: Jun 22, 2011
  • Threads: 97
  • Posts: 4628
February 27th, 2021 at 7:12:35 AM permalink
Quote: teliot

On the topic of Golfing, let me create a different problem that is based on efficient stamp totals.

Suppose the Post Office issues two values of stamps X cents and Y cents. What are the most efficient values for these two stamps X & Y so that we can make each postage from $1.20 to $2.00, using the least number of stamps overall?

Yeah, "Easy" Math Puzzles. :)


Because I have nothing better to do at 7 AM on a Saturday morning...


(13, 11) uses 1072 stamps:
Total1311Total1311Total1311Total1311
1205514048160311180131
1210111411011619418187
1226414257162410182140
12311014311016310318396
124731446616459184412
12529145112165112185105
126821467516668186511
12738147211167121187114
128911488416877188610
12947149310169130189123
130100150931708619079
1315615149171312191132
1320121521021729519288
1336515358173411193141
13411115411117410419497
1357415567175510195150
136210156120176113196106
137831577617769197512
13839158212178122198115
139921598517978199611
200124


teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2159
February 27th, 2021 at 7:30:55 AM permalink
Quote: ThatDonGuy

Because I have nothing better to do at 7 AM on a Saturday morning...


(13, 11) uses 1072 stamps:
Total1311Total1311Total1311Total1311
1205514048160311180131
1210111411011619418187
1226414257162410182140
12311014311016310318396
124731446616459184412
12529145112165112185105
126821467516668186511
12738147211167121187114
128911488416877188610
12947149310169130189123
130100150931708619079
1315615149171312191132
1320121521021729519288
1336515358173411193141
13411115411117410419497
1357415567175510195150
136210156120176113196106
137831577617769197512
13839158212178122198115
139921598517978199611
200124


Ha! I was writing c code at 5:30 this morning.

Correct, of course.
Personal website: www.ijmp.org
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1367
  • Posts: 22723
February 27th, 2021 at 7:45:24 AM permalink
I'm sure we're all wondering if there is at least a short cut to the right answer to such problems or is brute force the only way? I suspect in general the coinages will be semi-prime to each other, but I can't put into words why.
It's not whether you win or lose; it's whether or not you had a good bet.
teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2159
February 27th, 2021 at 8:05:12 AM permalink
Quote: Wizard

I'm sure we're all wondering if there is at least a short cut to the right answer to such problems or is brute force the only way? I suspect in general the coinages will be semi-prime to each other, but I can't put into words why.

Yes, the coinages must be relatively prime. If d is a divisor of a & b, then d is also a divisor of ax + by for all x, y. Ergo, you can only make coinages that are divisible by gcd(a,b).

As for your interesting question of getting a short cut, that's why I gave the example of $1.19. The answer doesn't fit the most obvious short cut, namely to minimize the difference |a-b| while maximizing the product (a-1)*(b-1) <= N (where N is the smallest coinage that needs to be made).
Last edited by: teliot on Feb 27, 2021
Personal website: www.ijmp.org
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 33
  • Posts: 2322
February 27th, 2021 at 8:52:25 AM permalink
This is only an observation but when the difference between two values was 2, one had to devise two sets of numbers.

For instance if you were using 5 and 7, 25 would be 5*5 and 0*7. Reducing the number of 5's by 1 and adding a 7 instead, would add 2 (27=4*5+1*7 etc.). So this creates 25 27 29 31 33 35. 28 is 4*7 so 26 is 3*7+1*5. 30 is 6*5 which starts the next series up to 42; 7*5 starts 35....

Presumably this process continues all the way up. So you might be able to determine how this goes based on the pattern and end conditions.
Gialmere
Gialmere
Joined: Nov 26, 2018
  • Threads: 39
  • Posts: 1821
March 1st, 2021 at 8:22:24 AM permalink
Here's an easy Monday puzzle...

Have you tried 22 tonight? I said 22.

  • Jump to: