Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

May 2022 - Challenge

<< February


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]


We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

 

Challenge: 28/04/2022 @ 14:00 PM EST
Solution: 04/06/2022 @ 12:00 PM EST
List Updated: 11/05/2022 @ 13:45 PM EST

People who answered correctly:

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)
*Paul Revenant (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 AM IDT)
*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)
*Andreas Stiller (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)
*Joe Hypoman (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)