Ponder This Challenge - May 2022 - Splitting a set in two for sum 0

Let $A$ be a set of integers of size $2n$. It is a known theorem that every such set contains a subset $B\subseteq A$ of size $n$ such that the sum $\sum_{b\in B}b$ is divisible by $n$.

For example, for $n=7$, given the set $A=[70, 18, 15, 74, 71, 40, 92, 54, 23, 82, 24, 6, 73, 62]$ we can find a subset $B=[71, 82, 24, 62, 54, 23, 6]$ whose elements sum to $322=7\times 46$.

We add an additional constraint on $B$. If $A=[a_1, a_2,\ldots, a_{2n}]$ then $B$ must contain *exactly* one element from each pair of elements $(a_{2i-1},a_{2i})$ for $1\le i\le n$.

In the above example, $B$ does not satisfy this constraint; both 23 and 82 (elements 9,10, i.e. $i=5$) are in $B$. But we can find another solution satisfying the additional constaint: $B = [70, 74, 71, 92, 23, 24, 73]$

Your goal: Given the set A [194, 236, 291, 430, 1, 721, 486, 819, 2, 44, 196, 238, 293, 529, 584, 45, 197, 433, 101, 46, 586, 337, 5, 725, 102, 822, 781, 144, 6, 920, 394, 242, 976, 533, 492, 244, 493, 632, 784, 729, 106, 536, 591, 149, 10, 537, 204, 634, 689, 150, 399, 538, 690, 926, 884, 54, 206, 539, 400, 831, 207, 735, 401, 832, 498, 929, 789, 251, 111, 542, 208, 639, 305, 736, 112, 930, 500, 349, 791, 931, 888, 156, 113, 253, 501, 933, 695, 62, 503, 159, 891, 838, 116, 935, 989, 742, 505, 937, 699, 841, 893, 551, 894, 842, 22, 67, 119, 358, 313, 843, 604, 359, 895, 553, 217, 747, 702, 941, 993, 457, 121, 70, 218, 555, 800, 168, 25, 362, 26, 653, 414, 363, 125, 753, 29, 949, 514, 950, 805, 78, 999, 757, 418, 467, 31, 80, 128, 468, 613, 857, 807, 276, 323, 761, 227, 858, 712, 277, 325, 374, 616, 665, 810, 763, 132, 86, 36, 474, 424, 862, 522, 961, 135, 89, 426, 186, 39, 672, 233, 866, 330, 770, 815, 287, 912, 384, 137, 191, 525, 676, 41, 192, 623, 581]

Provide a subset of the correct size and sum satisfying the additional constraint. Give your solution in the same list format as the set A.

A bonus "*" for finding a solution for the set A

[900, 523, 1, 823, 151, 74, 301, 75, 152, 76, 752, 826, 902, 677, 4, 827, 304, 978, 604, 229, 455, 379, 755, 831, 905, 82, 6, 532, 456, 383, 606, 833, 906, 983, 7, 84, 308, 534, 758, 834, 908, 984, 9, 235, 609, 985, 909, 86, 610, 236, 760, 386, 311, 836, 461, 687, 611, 538, 761, 239, 612, 989, 762, 90, 313, 540, 463, 690, 613, 840, 164, 91, 464, 241, 764, 391, 914, 991, 465, 392, 615, 842, 915, 94, 166, 694, 466, 994, 916, 695, 317, 96, 618, 996, 768, 97, 169, 397, 320, 697, 620, 98, 770, 700, 921, 101, 323, 851, 623, 702, 923, 852, 174, 253, 625, 554, 26, 854, 926, 105, 177, 255, 478, 405, 778, 705, 179, 556, 779, 706, 180, 707, 630, 108, 930, 558, 31, 708, 631, 858, 781, 559, 482, 411, 932, 561, 483, 711, 933, 262, 34, 862, 184, 113, 784, 413, 934, 713, 186, 414, 337, 265, 637, 565, 787, 266, 339, 117, 190, 267, 490, 567, 790, 717, 940, 869, 491, 120, 641, 270, 642, 720, 792, 121, 193, 271, 643, 872, 344, 123, 944, 124, 195, 274, 495, 424, 795, 724, 945, 275, 196, 575, 796, 725, 47, 875, 947, 426, 798, 277, 948, 877, 49, 428, 199, 129, 799, 879, 200, 130, 350, 580, 501, 880, 801, 131, 951, 281, 53, 731, 203, 432, 54, 133, 205, 134, 805, 284, 806, 734, 507, 884, 359, 435, 60, 885, 960, 436, 61, 137, 361, 287, 511, 587, 811, 288, 212, 588, 662, 888, 363, 290, 963, 590, 364, 740, 964, 141, 365, 291, 815, 592, 816, 892, 817, 143, 68, 593, 518, 744, 69, 595, 519, 895, 669, 146, 819, 897, 71, 148, 72, 298, 372, 598, 672, 149, 73, 299, 373, 599]

Solution

• Click here to view the solution

  May 2022 Solution:

  A solution to the base riddle is

  [236, 430, 1, 819, 44, 238, 529, 45, 433, 46, 337, 5, 102, 144, 6, 242, 533, 244, 632, 729, 106, 149, 10, 204, 150, 399, 690, [884, 206, 400, 207, 832, 929, 789, 111, 208, 736, 112, 500, 791, 156, 113, 933, 62, 503, 891, 116, 989, 505, 699, 893, 894, 22, 119, 313, 359, 895, 217, 702, 993, 121, 218, 800, 25, 26, 414, 125, 29, 514, 78, 757, 467, 80, 468, 857, 276, 761, 858, 277, 325, 665, 763, 86, 474, 862, 961, 89, 186, 672, 866, 770, 287, 384, 137, 525, 41, 623]

  And for the bonus:

  [523, 823, 74, 75, 76, 826, 677, 827, 978, 604, 379, 755, 905, 6, 456, 606, 906, 7, 308, 758, 908, 9, 609, 909, 610, 760, 836, 461, 611, 761, 612, 762, 313, 463, 613, 164, 464, 764, 914, 465, 842, 915, 166, 466, 695, 96, 996, 768, 169, 320, 620, 770, 921, 851, 623, 923, 174, 625, 26, 926, 177, 478, 778, 179, 779, 180, 630, 930, 31, 631, 781, 482, 932, 483, 933, 34, 184, 784, 934, 186, 337, 637, 787, 339, 190, 490, 790, 940, 491, 641, 642, 792, 193, 643, 344, 944, 195, 495, 795, 945, 196, 796, 47, 947, 798, 948, 49, 129, 879, 200, 350, 501, 131, 281, 53, 203, 54, 205, 805, 734, 884, 435, 60, 960, 61, 361, 511, 811, 212, 662, 363, 963, 364, 964, 365, 815, 816, 817, 68, 518, 69, 519, 669, 819, 71, 72, 372, 672, 73, 373]

Solvers

• Daniel Chong Jyh Tar (2/5/2022 10:41 AM IDT)
• *John Goh (2/5/2022 11:27 AM IDT)
• *Alex Fleischer (2/5/2022 11:49 AM IDT)
• *Alper Halbutogullari (2/5/2022 11:59 AM IDT)
• *PaulRevenant (2/5/2022 12:08 PM IDT)
• *Bertram Felgenhauer (2/5/2022 12:13 PM IDT)
• *Walter Sebastian Gisler (2/5/2022 12:33 PM IDT)
• *Latchezar Christov (2/5/2022 12:43 PM IDT)
• *Niels Wouda (2/5/2022 1:15 PM IDT)
• *Jeremias Herrmann (2/5/2022 2:23 PM IDT)
• *Gaétan (2/5/2022 2:39 PM IDT)
• *Savitha Viswanadh Kandala (2/5/2022 3:00 PM IDT)
• *Boaz Menuhin (2/5/2022 3:10 PM IDT)
• Graham Hemsley (2/5/2022 3:51 PM IDT)
• Lorenz Reichel (2/5/2022 4:07 PM IDT)
• *Vamsi Krishna Talupula (2/5/2022 4:19 PM IDT)
• *Clive Tong (2/5/2022 4:44 PM IDT)
• *Lorenzo Gianferrari Pini (2/5/2022 5:18 PM IDT)
• *Gary M. Gerken (2/5/2022 5:19 PM IDT)
• *Victor Chang (2/5/2022 5:31 PM IDT)
• *Lazar Ilic (2/5/2022 5:35 PM IDT)
• *Daniel Bitin (2/5/2022 6:03 PM IDT)
• *Phil Proudman (2/5/2022 6:15 PM IDT)
• *Ruben Brokkelkamp (2/5/2022 6:16 PM IDT)
• *Maksym Voznyy (2/5/2022 6:30 PM IDT)
• *Benson Tran (2/5/2022 7:08 PM IDT)
• *Amos Guler (2/5/2022 7:15 PM IDT)
• *Carlos Alcoba (2/5/2022 7:36 PM IDT)
• *Bert Dobbelaere (2/5/2022 7:40 PM IDT)
• *Thomas Egense (2/5/2022 7:56 PM IDT)
• *Ryan Propper (2/5/2022 8:00 PM IDT)
• *Srinivas Kandala (2/5/2022 8:46 PM IDT)
• *Anders Kaseorg (2/5/2022 9:26 PM IDT)
• *Otto Ng (2/5/2022 9:27 PM IDT)
• *Dieter Beckerle (2/5/2022 11:30 PM IDT)
• *Sanandan Swaminathan (2/5/2022 11:33 PM IDT)
• *Vladimir Volevich (3/5/2022 12:12 AM IDT)
• Stefan Wirth (3/5/2022 2:08 AM IDT)
• *Reiner Martin (3/5/2022 2:15 AMIDT)
• *Laurent Lessard (3/5/2022 2:20 AM IDT)
• *Hong-Ta Chen (3/5/2022 4:50 AM IDT)
• *Quentin Higueret (3/5/2022 6:07 AM IDT)
• *Sri Mallikarjun J (3/5/2022 8:51 AM IDT)
• *Andrei Arhire (3/5/2022 2:08 PM IDT)
• Handre Williams (3/5/2022 2:38 PM IDT)
• *Nir Lavee (3/5/2022 3:08 PM IDT)
• *Paul Shaw (3/5/2022 4:18 PM IDT)
• *Rob Pratt (3/5/2022 5:17 PM IDT)
• *Dominik Reichl (3/5/2022 5:19 PM IDT)
• *Li Li (3/5/2022 5:52 PM IDT)
• *Samantha Casanova (3/5/2022 6:52 PM IDT)
• *Jacek Markiewicz (4/5/2022 12:48 AM IDT)
• *Asaf Zimmerman (4/5/2022 2:08 AM IDT)
• *Faiyaz Saraf (4/5/2022 3:57 AM IDT)
• *Tim Walters (4/5/2022 4:20 AM IDT)
• *Soonho You (4/5/2022 5:26 AM IDT)
• *Stefano Soccio (4/5/2022 11:49 AM IDT)
• *Tamir Ganor & Shouky Dan (4/5/2022 1:55 PM IDT)
• Fabio Michele Negroni (4/5/2022 3:28 PM IDT)
• *Benjamin Lui (4/5/2022 5:26 PM IDT)
• *Tymoteusz Gedliczka (4/5/2022 6:29 PM IDT)
• *Wolfgang Kais (4/5/2022 9:03 PM IDT)
• *Alexander Gramolin (4/5/2022 9:06 PM IDT)
• *Frank Schoeps (4/5/2022 10:58 PM IDT)
• *Michael Liepelt (4/5/2022 11:43 PM IDT)
• *Liubing Yu (5/5/2022 5:20 AM IDT)
• *Brian Bitto (5/5/2022 6:05 AM IDT)
• *Chris Shannon (5/5/2022 9:40 AM IDT)
• Fabio Filatrella (5/5/2022 11:24 AM IDT)
• *David Greer (5/5/2022 12:56 PM IDT)
• *Muralidhar Seshadri (5/5/2022 1:30 PM IDT)
• *Harald Bögeholz (5/5/2022 1:43 PM IDT)
• Ananda Raidu (5/5/2022 3:39 PM IDT)
• *AndreasStiller (5/5/2022 5:53 PM IDT)
• *Erik Wünstel (5/5/2022 9:56 PM IDT)
• *Franciraldo Cavalcante (5/5/2022 10:40 PM IDT)
• *Daniel Johnson-Chyzhykov (5/5/2022 10:48 PM IDT)
• *Dan Dima (5/5/2022 11:58 PM IDT)
• *Giorgos Kalogeropoulos (6/5/2022 1:50 AM IDT)
• *Collin Pearce (6/5/2022 4:12 AM IDT)
• *Nyles Heise (6/5/2022 8:09 AM IDT)
• *Serge Thill (6/5/2022 5:54 PM IDT)
• *Serino Dario (6/5/2022 6:23 PM IDT)
• *Sam Griff (6/5/2022 6:38 PM IDT)
• *Prashant Wankhede (6/5/2022 7:59 PM IDT)
• *Evert van Dijken (6/5/2022 10:29 PM IDT)
• *Catherine Li (7/5/2022 1:05 AM IDT)
• Suman Bhaumik (7/5/2022 2:18 AM IDT)
• Sachal Mahajan (7/5/2022 4:42 PM IDT)
• *Mtv Europe (7/5/2022 5:55 PM IDT)
• *Kang Jin Cho (7/5/2022 7:08 PM IDT)
• *Hansraj Nahata (7/5/2022 7:44 PM IDT)
• *Alexander Daryin (7/5/2022 11:36 PM IDT)
• *Guang-Zhong Sun (8/5/2022 10:37 AM IDT)
• *John Tromp (8/5/2022 8:36 PM IDT)
• *Phil Benamy (9/5/2022 4:45 AM IDT)
• *Annie Fan (9/5/2022 5:47 AM IDT)
• *Sanjay Rao (9/5/2022 10:34 AM IDT)
• Gianpaolo Galli (9/5/2022 1:04 PM IDT)
• *Rajesh Sathiyanarayanan (9/5/2022 7:52 PM IDT)
• *Fabio Filatrella (9/5/2022 9:12 PM IDT)
• *Lavanya Kannan (9/5/2022 11:10 PM IDT)
• *Richard Liu (10/5/2022 6:43 AM IDT)
• *Elliot Hong (11/5/2022 2:47 AM IDT)
• Matvey Kovalev (11/5/20226:49 PM IDT)
• Alireza Soroudi (11/5/2022 6:56 PM IDT)
• *Carl Löndahl (11/5/2022 11:49 PM IDT)
• *Alex Gliesch (12/5/2022 12:24 AM IDT)
• *Christopher Leonard (12/5/2022 1:26 AM IDT)
• *Austin Lee (12/5/2022 1:52 AM IDT)
• *Michael Chirozzi (12/5/2022 5:15 AM IDT)
• *Markó Horváth (12/5/2022 11:54 AM IDT)
• *Andras Varga (12/5/2022 12:00 PM IDT)
• *Peter Moser (12/5/2022 10:38 PM IDT)
• *Merve ÖZER (12/5/2022 10:52 PM IDT)
• *Ellen Liu (13/5/2022 12:47 AM IDT)
• *Marco Bellocchi (13/5/2022 12:54 AM IDT)
• Daniel Lincke (13/5/2022 4:09 AM IDT)
• *Lawrence Au (13/5/2022 10:36 AM IDT)
• *Chuck Carroll (13/5/2022 5:51 PM IDT)
• *Jordan Dworaczyk (13/5/2022 6:01 PM IDT)
• *Emil Nicolae Nichita (13/5/2022 8:42 PM IDT)
• *Matt Delevoryas (13/5/2022 9:05 PM IDT)
• *Joaquim Neves Carrapa (14/5/2022 2:20 AM IDT)
• *Cameron Devereaux (14/5/2022 11:00 PM IDT)
• *Chiho Haruta (15/5/2022 5:27 AM IDT)
• *Sava Alexandru (16/5/2022 12:23 AM IDT)
• *Kai Guttmann (16/5/2022 12:28 AM IDT)
• *Stéphane Higueret (16/5/2022 10:33 AM IDT)
• *Andy Greig (16/5/2022 12:53 PM IDT)
• *Antonio Garcia (16/5/2022 7:50 PM IDT)
• *Nir Paz (17/5/2022 1:50 AM IDT)
• *Ali Gurel (18/5/2022 6:27 AM IDT)
• *Thomas Lysensoone (18/5/2022 3:28 PM IDT)
• *Guillaume Escamocher (18/5/2022 9:53 PM IDT)
• *Jose Coelho (19/5/2022 1:00 AM IDT)
• *Albert Stadler (19/5/2022 12:36 PM IDT)
• Deep Kankaria (20/5/2022 5:08 PM IDT)
• *Dezhi Zhao (21/5/2022 1:55 AM IDT)
• *Gianpaolo Galli (21/5/2022 10:42 AM IDT)
• *Yoav Alroy (21/5/2022 3:42 PM IDT)
• *Andrei Tsygankov (21/5/2022 4:44 PM IDT)
• *Aaron Kim (21/5/2022 5:15 PM IDT)
• *Jan Fricke (21/5/2022 10:47 PM IDT)
• *Jan Fricke (22/5/2022 11:27 AM IDT)
• *Sebastian Bohm & Martí Bosch (23/5/2022 11:39 AM IDT)
• *Daniel Scheinerman (24/5/2022 5:34 PM IDT)
• *Gareth Ma (24/5/2022 6:33 PM IDT)
• *Klaus Hoffmann (25/5/2022 6:09 PM IDT)
• *Shahab Tasharrofi (25/5/2022 6:30 PM IDT)
• *Issa Bou Zeid (26/5/2022 12:38 AM IDT)
• *Itzik Lichtenstein (26/5/2022 6:55 AM IDT)
• *Pattu Patnaik (26/5/2022 10:47 AM IDT)
• *David Hentrich (26/5/2022 4:41 PM IDT)
• *Pål Hermunn Johansen (26/5/2022 4:42 PM IDT)
• *Nayan Maiti (26/5/2022 6:02 PM IDT)
• *Eran Vered (26/5/2022 6:46 PM IDT)
• *Elias Papavassilopoulos (26/5/2022 8:22 PM IDT)
• *Julius Fritz Barth (27/5/2022 7:15 AM IDT)
• *Prashant Deshpande (27/5/2022 8:47 PM IDT)
• *Reda Kebbaj (28/5/2022 10:20 AM IDT)
• *Wei Liu (28/5/2022 1:04 PM IDT)
• *Paolo Farinelli (28/5/2022 8:08 PM IDT)
• *Vincent Thai (28/5/2022 9:11 PM IDT)
• Dipto Thakurta (28/5/2022 11:05 PM IDT)
• *Adam Wang (29/5/2022 7:06 AM IDT)
• *Okan Oymak (29/5/2022 9:17 PM IDT)
• *Noam Zaks (30/5/2022 4:32 PM IDT)
• *Motty Porat (30/5/2022 11:06 PM IDT)
• *David F.H. Dunkley (31/5/2022 2:05 AM IDT)
• *Andrew Milas (31/5/2022 10:10 AM IDT)
• *Arun Sivaramakrishnan (31/5/2022 11:09 AM IDT)
• *Todd Will (31/5/2022 6:28 PM IDT)
• *Frédéric Quesnel (31/5/2022 11:24 PM IDT)
• Radu-Alexandru Todor (1/6/2022 3:08 AM IDT)
• *Kindulov Mikhail (3/6/2022 1:59 AM IDT)
• Jason Bono (3/6/2022 8:16 PM IDT)
• Vivek Nema (5/6/2022 4:09 PM IDT)
• *Ranjit Eswaran (6/6/2022 7:37 PM IDT)