Question

How to divide the following set into 2 subsets with equal sum, and 500 numbers in each `1^2,2^2,3^2,4^2,...,1000^2` ?

Answer 1

Here's a solution, but it's not pretty...

Explanation:

Here's an ugly method, but it works.

I used an algorithm as follows:

Start with two empty sets `A` and `B`

For each pair from `(1000, 999)`, `(998, 997)` down to `(2, 1)` add one of the elements of the pair to `A` and the other to `B` as follows:

If `sum_(a in A) a^2 > sum_(b in B) b^2` then add the larger number to `B` and the smaller to `A`. Otherwise add them the other way around.

The resulting sets are:

`A = { 1000, 997, 995, 994, 992, 989, 987, 986, 984, 981, 979, 978, 976, 973, 971, 970, 968, 965, 963, 962, 960, 957, 955, 954, 952, 949, 947, 946, 944, 941, 939, 938, 936, 933, 931, 930, 928, 925, 923, 922, 920, 917, 915, 914, 912, 909, 907, 906, 904, 901, 899, 898, 896, 893, 891, 890, 888, 885, 883, 882, 880, 877, 875, 874, 872, 869, 867, 866, 864, 861, 859, 858, 856, 853, 851, 850, 848, 845, 843, 842, 840, 837, 835, 834, 832, 829, 827, 826, 824, 821, 819, 818, 816, 813, 811, 810, 808, 805, 803, 802, 800, 797, 795, 794, 792, 789, 787, 786, 784, 781, 779, 778, 776, 773, 771, 770, 768, 765, 763, 762, 760, 757, 755, 754, 752, 749, 747, 746, 744, 741, 739, 738, 736, 733, 731, 730, 728, 725, 723, 722, 720, 717, 715, 714, 712, 709, 707, 706, 704, 701, 699, 698, 696, 693, 691, 690, 688, 685, 683, 682, 680, 677, 675, 674, 672, 669, 667, 666, 664, 661, 659, 658, 656, 653, 651, 650, 648, 645, 643, 642, 640, 637, 635, 634, 632, 629, 627, 626, 624, 621, 619, 618, 616, 613, 611, 610, 608, 605, 603, 602, 600, 597, 595, 594, 592, 589, 587, 586, 584, 581, 579, 578, 576, 573, 571, 570, 568, 565, 563, 562, 560, 557, 555, 554, 552, 549, 547, 546, 544, 541, 539, 538, 536, 533, 531, 530, 528, 525, 523, 522, 520, 517, 515, 514, 512, 509, 507, 506, 504, 501, 499, 498, 496, 493, 491, 490, 488, 485, 483, 482, 480, 477, 475, 474, 472, 469, 467, 466, 464, 461, 459, 458, 456, 453, 451, 450, 448, 445, 443, 442, 440, 437, 435, 434, 432, 429, 427, 426, 424, 421, 419, 418, 416, 413, 411, 410, 408, 405, 403, 402, 400, 397, 395, 394, 392, 389, 387, 386, 384, 381, 379, 378, 376, 373, 371, 370, 368, 365, 363, 362, 360, 357, 355, 354, 352, 349, 347, 346, 344, 341, 339, 338, 336, 333, 331, 330, 328, 325, 323, 322, 320, 317, 315, 314, 312, 309, 307, 306, 304, 301, 299, 298, 296, 293, 291, 290, 288, 285, 283, 282, 280, 277, 275, 274, 272, 269, 267, 266, 264, 261, 259, 258, 256, 253, 251, 250, 248, 245, 243, 242, 240, 237, 235, 234, 232, 229, 227, 226, 224, 221, 219, 218, 216, 213, 211, 210, 208, 205, 203, 202, 200, 197, 195, 194, 192, 189, 187, 186, 184, 181, 179, 178, 176, 173, 171, 170, 168, 165, 163, 162, 160, 157, 155, 154, 152, 149, 147, 146, 144, 141, 139, 138, 136, 133, 131, 130, 128, 125, 123, 122, 120, 117, 115, 114, 112, 109, 107, 106, 104, 101, 99, 98, 96, 93, 91, 90, 88, 85, 83, 82, 80, 77, 75, 74, 72, 69, 67, 66, 64, 61, 59, 58, 56, 53, 51, 50, 48, 45, 43, 42, 40, 37, 35, 34, 32, 29, 27, 26, 24, 21, 19, 18, 16, 13, 11, 10, 8, 5, 3, 2}`

`B = { 999, 998, 996, 993, 991, 990, 988, 985, 983, 982, 980, 977, 975, 974, 972, 969, 967, 966, 964, 961, 959, 958, 956, 953, 951, 950, 948, 945, 943, 942, 940, 937, 935, 934, 932, 929, 927, 926, 924, 921, 919, 918, 916, 913, 911, 910, 908, 905, 903, 902, 900, 897, 895, 894, 892, 889, 887, 886, 884, 881, 879, 878, 876, 873, 871, 870, 868, 865, 863, 862, 860, 857, 855, 854, 852, 849, 847, 846, 844, 841, 839, 838, 836, 833, 831, 830, 828, 825, 823, 822, 820, 817, 815, 814, 812, 809, 807, 806, 804, 801, 799, 798, 796, 793, 791, 790, 788, 785, 783, 782, 780, 777, 775, 774, 772, 769, 767, 766, 764, 761, 759, 758, 756, 753, 751, 750, 748, 745, 743, 742, 740, 737, 735, 734, 732, 729, 727, 726, 724, 721, 719, 718, 716, 713, 711, 710, 708, 705, 703, 702, 700, 697, 695, 694, 692, 689, 687, 686, 684, 681, 679, 678, 676, 673, 671, 670, 668, 665, 663, 662, 660, 657, 655, 654, 652, 649, 647, 646, 644, 641, 639, 638, 636, 633, 631, 630, 628, 625, 623, 622, 620, 617, 615, 614, 612, 609, 607, 606, 604, 601, 599, 598, 596, 593, 591, 590, 588, 585, 583, 582, 580, 577, 575, 574, 572, 569, 567, 566, 564, 561, 559, 558, 556, 553, 551, 550, 548, 545, 543, 542, 540, 537, 535, 534, 532, 529, 527, 526, 524, 521, 519, 518, 516, 513, 511, 510, 508, 505, 503, 502, 500, 497, 495, 494, 492, 489, 487, 486, 484, 481, 479, 478, 476, 473, 471, 470, 468, 465, 463, 462, 460, 457, 455, 454, 452, 449, 447, 446, 444, 441, 439, 438, 436, 433, 431, 430, 428, 425, 423, 422, 420, 417, 415, 414, 412, 409, 407, 406, 404, 401, 399, 398, 396, 393, 391, 390, 388, 385, 383, 382, 380, 377, 375, 374, 372, 369, 367, 366, 364, 361, 359, 358, 356, 353, 351, 350, 348, 345, 343, 342, 340, 337, 335, 334, 332, 329, 327, 326, 324, 321, 319, 318, 316, 313, 311, 310, 308, 305, 303, 302, 300, 297, 295, 294, 292, 289, 287, 286, 284, 281, 279, 278, 276, 273, 271, 270, 268, 265, 263, 262, 260, 257, 255, 254, 252, 249, 247, 246, 244, 241, 239, 238, 236, 233, 231, 230, 228, 225, 223, 222, 220, 217, 215, 214, 212, 209, 207, 206, 204, 201, 199, 198, 196, 193, 191, 190, 188, 185, 183, 182, 180, 177, 175, 174, 172, 169, 167, 166, 164, 161, 159, 158, 156, 153, 151, 150, 148, 145, 143, 142, 140, 137, 135, 134, 132, 129, 127, 126, 124, 121, 119, 118, 116, 113, 111, 110, 108, 105, 103, 102, 100, 97, 95, 94, 92, 89, 87, 86, 84, 81, 79, 78, 76, 73, 71, 70, 68, 65, 63, 62, 60, 57, 55, 54, 52, 49, 47, 46, 44, 41, 39, 38, 36, 33, 31, 30, 28, 25, 23, 22, 20, 17, 15, 14, 12, 9, 7, 6, 4, 1 }`

and the sum of the squares in each set is the same: `166916750`