Solution:
r = √12.5 = 5/2 * √2
The first trick to finding this solution is to realize that the circle does not need to be centered on a grid intersection.
To understand how you might solve problems like this, you can start by understanding this circle:
To me, this is the most obvious potential solution. The circle passes through 12 grid intersections, and so is a candidate for the solution to the problem. This circle is based on the well known 3-4-5 triangle. Because 3² + 4² = 5², the distance from the center to any of the 8 points near the corners is 5, the same as the distance to the 4 points near the edges.
The solution is actually just a rotated and shrunken version of this. Observe:
There are other ways you could find the actual solution. One of them is to realize that 7² + 1² = 5² + 5². The points near the corners are 5 half-units from center of the circle horizontally, and 5 half-units vertically as well. The points near the edges are 7 half-units one way and 1 half-unit the other. Therefore, they are all the same distance from the center. This is actually the way I did it when I invented the puzzle.
Additional Information
I used my mad programming skills to generate a list of circles with notable point counts (with radii less than 10000). The data is below. I considered only circles centered on grid intersections, in the middle of grid squares, or in the middle of grid edges (not pictured above). Each entry in the list looks like this:
point count: radius
x1, y1
x2, y2
...
(Mirror-image coordinates are not listed. For instance, the circle with a point count of 4 and radius of 1 actually has these points: (0,1), (0,-1), (1,0) and (-1,0). I only listed one of these since the rest can be easily inferred.)
(for circles centered on squares or edges, the coordinates should be divided by two to get actual non-integer coordinates)
A circle is listed if and only if it has a higher point count than all smaller circles in that category.
A couple interesting things are visible in the data:
- For every circle centered on a grid intersection, there is a corresponding circle centered in the middle of a square. (they are shown side-by-side in the table) This circle has the same point count but the radius is smaller by a factor of the square root of two.
- The points in these circles are related on a sum-and-difference basis. So, for the 3-4-5 circle from above, the points are 4,3 and 5,0. The sum of 4 and 3 is 7, and the difference of 4 and 3 is 1. So, 7,1 is a point in the corresponding circle. Similarly, the sum of 0 and 5 is 5 and the difference of 0 and 5 is 5. So, 5,5 is a point in the corresponding circle.
- For every circle centered on a grid intersection, there is a corresponding circle centered on the middle of an edge. This circle has half the point count and half the radius.
- The point counts do not increase by 4 each time. The pattern of increasing point counts appears to be irregular.
Circles centered on Circles centered on Circles centered on
grid intersections: grid squares: grid edges:
4: 1.00000 4: 0.70711 2: 0.50000
1, 0 1, 1 1, 0
8: 2.23607 8: 1.58114 4: 1.11803
2, 1 3, 1 2, 1
12: 5.00000 12: 3.53553 6: 2.50000
4, 3 5, 5 4, 3
5, 0 7, 1 5, 0
16: 8.06226 16: 5.70088 8: 4.03113
7, 4 9, 7 7, 4
8, 1 11, 3 8, 1
24: 18.02776 24: 12.74755 12: 9.01388
15, 10 19, 17 15, 10
17, 6 23, 11 17, 6
18, 1 25, 5 18, 1
32: 33.24154 32: 23.50532 16: 16.62077
24, 23 37, 29 24, 23
31, 12 41, 23 31, 12
32, 9 43, 19 32, 9
33, 4 47, 1 33, 4
36: 65.00000 36: 45.96194 18: 32.50000
52, 39 65, 65 52, 39
56, 33 79, 47 56, 33
60, 25 85, 35 60, 25
63, 16 89, 23 63, 16
65, 0 91, 13 65, 0
48: 74.33034 48: 52.55949 24: 37.16517
55, 50 81, 67 55, 50
62, 41 87, 59 62, 41
70, 25 93, 49 70, 25
71, 22 95, 45 71, 22
73, 14 103, 21 73, 14
74, 7 105, 5 74, 7
64: 166.20770 64: 117.52659 32: 83.10385
120, 115 185, 145 120, 115
132, 101 191, 137 132, 101
141, 88 205, 115 141, 88
144, 83 215, 95 144, 83
155, 60 227, 61 155, 60
160, 45 229, 53 160, 45
164, 27 233, 31 164, 27
165, 20 235, 5 165, 20
72: 268.00187 72: 189.50594 36: 134.00093
191, 188 269, 267 191, 188
208, 169 305, 225 208, 169
215, 160 325, 195 215, 160
236, 127 333, 181 236, 127
247, 104 351, 143 247, 104
257, 76 363, 109 257, 76
260, 65 375, 55 260, 65
265, 40 377, 39 265, 40
268, 1 379, 3 268, 1
80: 371.65172 80: 262.79745 40: 185.82586
275, 250 393, 349 275, 250
301, 218 405, 335 301, 218
310, 205 435, 295 310, 205
317, 194 465, 245 317, 194
334, 163 475, 225 334, 163
350, 125 497, 171 350, 125
355, 110 511, 123 355, 110
365, 70 515, 105 365, 70
370, 35 519, 83 370, 35
371, 22 525, 25 371, 22
96: 400.28115 96: 283.04152 48: 200.14058
300, 265 415, 385 300, 265
311, 252 431, 367 311, 252
329, 228 469, 317 329, 228
337, 216 473, 311 337, 216
356, 183 497, 271 356, 183
360, 175 515, 235 360, 175
375, 140 535, 185 375, 140
384, 113 539, 173 384, 113
392, 81 553, 121 392, 81
393, 76 557, 101 393, 76
399, 32 563, 59 399, 32
400, 15 565, 35 400, 15
128: 895.05586 128: 632.90007 64: 447.52793
655, 610 905, 885 655, 610
703, 554 985, 795 703, 554
710, 545 1013, 759 710, 545
722, 529 1039, 723 722, 529
766, 463 1067, 681 766, 463
769, 458 1095, 635 769, 458
785, 430 1103, 621 785, 430
815, 370 1165, 495 815, 370
830, 335 1185, 445 830, 335
862, 241 1215, 355 862, 241
865, 230 1227, 311 865, 230
874, 193 1229, 303 874, 193
881, 158 1251, 193 881, 158
886, 127 1255, 165 886, 127
890, 95 1257, 149 890, 95
895, 10 1265, 45 895, 10
144: 1443.23422 144: 1020.52070 72: 721.61711
1027, 1014 1469, 1417 1027, 1014
1107, 926 1571, 1303 1107, 926
1133, 894 1597, 1271 1133, 894
1170, 845 1625, 1235 1170, 845
1230, 755 1735, 1075 1230, 755
1245, 730 1765, 1025 1245, 730
1261, 702 1807, 949 1261, 702
1322, 579 1873, 811 1322, 579
1331, 558 1879, 797 1331, 558
1338, 541 1889, 773 1338, 541
1342, 531 1901, 743 1342, 531
1378, 429 1963, 559 1378, 429
1395, 370 1975, 515 1395, 370
1405, 330 1985, 475 1405, 330
1430, 195 2015, 325 1430, 195
1434, 163 2027, 239 1434, 163
1437, 134 2033, 181 1437, 134
1443, 26 2041, 13 1443, 26
160: 2001.40576 160: 1415.20758 80: 1000.70288
1483, 1344 2075, 1925 1483, 1344
1500, 1325 2143, 1849 1500, 1325
1555, 1260 2155, 1835 1555, 1260
1604, 1197 2309, 1637 1604, 1197
1645, 1140 2345, 1585 1645, 1140
1685, 1080 2365, 1555 1685, 1080
1692, 1069 2429, 1453 1692, 1069
1780, 915 2485, 1355 1780, 915
1800, 875 2531, 1267 1800, 875
1811, 852 2575, 1175 1811, 852
1875, 700 2663, 959 1875, 700
1899, 632 2675, 925 1899, 632
1920, 565 2695, 865 1920, 565
1941, 488 2761, 623 1941, 488
1960, 405 2765, 605 1960, 405
1965, 380 2785, 505 1965, 380
1973, 336 2801, 407 1973, 336
1995, 160 2815, 295 1995, 160
1996, 147 2825, 175 1996, 147
2000, 75 2827, 139 2000, 75
192: 2434.81519 192: 1721.67433 96: 1217.40759
1746, 1697 2497, 2371 1746, 1697
1806, 1633 2527, 2339 1806, 1633
1823, 1614 2633, 2219 1823, 1614
1890, 1535 2711, 2123 1890, 1535
1953, 1454 2725, 2105 1953, 1454
1985, 1410 2855, 1925 1985, 1410
2065, 1290 2875, 1895 2065, 1290
2110, 1215 2953, 1771 2110, 1215
2118, 1201 3025, 1645 2118, 1201
2191, 1062 3061, 1577 2191, 1062
2202, 1039 3131, 1433 2202, 1039
2238, 959 3149, 1393 2238, 959
2271, 878 3197, 1279 2271, 878
2282, 849 3241, 1163 2282, 849
2319, 742 3253, 1129 2319, 742
2335, 690 3319, 917 2335, 690
2362, 591 3325, 895 2362, 591
2385, 490 3355, 775 2385, 490
2390, 465 3395, 575 2390, 465
2415, 310 3407, 499 2415, 310
2417, 294 3425, 355 2417, 294
2426, 207 3437, 209 2426, 207
2433, 94 3439, 173 2433, 94
2434, 63 3443, 49 2434, 63
256: 5444.41227 256: 3849.78084 128: 2722.20614
3896, 3803 5511, 5377 3896, 3803
3980, 3715 5567, 5319 3980, 3715
4027, 3664 5721, 5153 4027, 3664
4133, 3544 5755, 5115 4133, 3544
4156, 3517 5935, 4905 4156, 3517
4280, 3365 5997, 4829 4280, 3365
4315, 3320 6215, 4545 4315, 3320
4520, 3035 6315, 4405 4520, 3035
4540, 3005 6495, 4135 4540, 3005
4645, 2840 6665, 3855 4645, 2840
4772, 2621 6705, 3785 4772, 2621
4805, 2560 6837, 3541 4805, 2560
4861, 2452 6935, 3345 4861, 2452
4931, 2308 6957, 3299 4931, 2308
4960, 2245 7051, 3093 4960, 2245
5051, 2032 7071, 3047 5051, 2032
5059, 2012 7083, 3019 5059, 2012
5072, 1979 7205, 2715 5072, 1979
5128, 1829 7239, 2623 5128, 1829
5140, 1795 7313, 2409 5140, 1795
5189, 1648 7365, 2245 5189, 1648
5245, 1460 7393, 2151 5245, 1460
5260, 1405 7485, 1805 5260, 1405
5315, 1180 7545, 1535 5315, 1180
5360, 955 7555, 1485 5360, 955
5380, 835 7635, 995 5380, 835
5413, 584 7645, 915 5413, 584
5420, 515 7673, 639 5420, 515
5435, 320 7677, 589 5435, 320
5437, 284 7691, 363 5437, 284
5443, 124 7695, 265 5443, 124
5444, 67 7699, 93 5444, 67
288: 8778.85101 288: 6207.58508 144: 4389.42550
6240, 6175 9035, 8515 6240, 6175
6497, 5904 9223, 8311 6497, 5904
6625, 5760 9335, 8185 6625, 5760
6663, 5716 9389, 8123 6663, 5716
6740, 5625 9565, 7915 6740, 5625
6864, 5473 9893, 7501 6864, 5473
7111, 5148 9971, 7397 7111, 5148
7176, 5057 10231, 7033 7176, 5057
7353, 4796 10427, 6739 7353, 4796
7428, 4679 10477, 6661 7428, 4679
7487, 4584 10561, 6527 7487, 4584
7521, 4528 10663, 6359 7521, 4528
7568, 4449 10729, 6247 7568, 4449
7692, 4231 10853, 6029 7692, 4231
7839, 3952 10985, 5785 7839, 3952
7865, 3900 11219, 5317 7865, 3900
8000, 3615 11335, 5065 8000, 3615
8100, 3385 11435, 4835 8100, 3385
8135, 3300 11485, 4715 8135, 3300
8200, 3135 11615, 4385 8200, 3135
8268, 2951 11765, 3965 8268, 2951
8385, 2600 11791, 3887 8385, 2600
8441, 2412 11923, 3461 8441, 2412
8488, 2241 12017, 3119 8488, 2241
8511, 2152 12049, 2993 8511, 2152
8544, 2017 12071, 2903 8544, 2017
8569, 1908 12107, 2749 8569, 1908
8583, 1844 12149, 2557 8583, 1844
8632, 1599 12233, 2119 8632, 1599
8684, 1287 12259, 1963 8684, 1287
8697, 1196 12337, 1391 8697, 1196
8740, 825 12365, 1115 8740, 825
8756, 633 12379, 947 8756, 633
8760, 575 12385, 865 8760, 575
8767, 456 12401, 593 8767, 456
8775, 260 12415, 65 8775, 260
320: 8608.37165 160: 6087.03797
12217, 12131 8730, 8485
12485, 11855 8786, 8427
12635, 11695 9030, 8165
13121, 11147 9083, 8106
13165, 11095 9115, 8070
13237, 11009 9450, 7675
13555, 10615 9547, 7554
13625, 10525 9765, 7270
13919, 10133 9925, 7050
14275, 9625 10014, 6923
14375, 9475 10242, 6581
14707, 8951 10325, 6450
14765, 8855 10550, 6075
15019, 8417 10590, 6005
15125, 8225 10762, 5691
15305, 7885 10821, 5578
15491, 7513 10955, 5310
15655, 7165 11010, 5195
15745, 6965 11158, 4869
15943, 6499 11190, 4795
15985, 6395 11221, 4722
16027, 6289 11355, 4390
16205, 5815 11410, 4245
16265, 5645 11502, 3989
16399, 5243 11595, 3710
16453, 5071 11675, 3450
16595, 4585 11718, 3301
16625, 4475 11810, 2955
16775, 3875 11829, 2878
16823, 3661 11925, 2450
16937, 3091 11950, 2325
16975, 2875 12026, 1893
17035, 2495 12075, 1550
17101, 1993 12085, 1470
17125, 1775 12123, 1114
17185, 1045 12130, 1035
17189, 977 12134, 987
17195, 865 12165, 470
17213, 359 12170, 315
17215, 245 12174, 43
192: 7795.21207
11138, 10909
11210, 10835
11302, 10739
11789, 10202
11885, 10090
11918, 10051
11990, 9965
12403, 9446
12422, 9421
12541, 9262
12790, 8915
12958, 8669
12986, 8627
13261, 8198
13315, 8110
13373, 8014
13474, 7843
13747, 7354
13810, 7235
13885, 7090
14003, 6854
14074, 6707
14174, 6493
14435, 5890
14477, 5786
14515, 5690
14563, 5566
14710, 5165
14806, 4883
14867, 4694
14990, 4285
15026, 4157
15082, 3949
15166, 3613
15203, 3454
15235, 3310
15362, 2659
15389, 2498
15394, 2467
15410, 2365
15469, 1942
15485, 1810
15518, 1501
15562, 941
15565, 890
15571, 778
15581, 542
15590, 115
No comments:
Post a Comment