Ponder This Challenge - April 2018 - 9 Balloons

There are nine balloons in nine different colors. Each balloon has a different lifting capability, from one through nine grams (1, 2, 3...9) respectively. Alice knows the lifting capacities of each balloon, and she wants to use the smallest possible combinations of balloons to prove to Bob the identity of the 1-gram balloon. She can tie together any subset of balloons to a 9.5-gram weight that will stay put if and only if the total lifting power of the balloons is less than 9.5 grams. Otherwise the weight will lift off and fly away.
How does Alice prove to Bob the color of the 1-gram balloon by doing as few "experiments" as possible?
Each demonstration should use a subset of the balloons that does not lift the weight. Supply your answer as a list of weights per experiment.

For example, here is a (non-optimal) solution for a similar problem with only six balloons with 1-6 gram lifting capacities and a 6.5-gram weight:
1,2
1,3
1,4
1,5

In each one of the four experiments, Alice uses a subset of the balloons that does not lift the weight and that has a total lift capacity of six grams or less. Therefore, Bob can conclude that the balloon that is common to all the experiments must be the one with the 1-gram lift capacity.
Two wrong answers for the six-balloon example include the following:

1. A single experiment: "1,2,3" - this is the only combination of three balloons that won't lift the weight, but Bob can't know from this experiment alone which of the three balloons has the 1-gram lifting capacity.
2. Three experiments: "1,2" "1,3" and "1,5" - Bob can't distinguish between that and "2,1" "2,3" and "2,4". Both sets of experiments look exactly the same to him, so he can't be sure if the repeated balloon has a 1-gram or 2-gram lifting capacity.

Solution

• Click here to view the solution

  There are five different solutions:

  1,2,4  1,2,5  1,3,4  1,3,5
  1,2,4  1,2,6  1,3,4  1,3,5
  1,2,5  1,2,6  1,3,4  1,3,5
  1,2,6  1,3,4  1,3,5  2,7
  1,2,6  1,3,4  1,3,5  4,5
  

  Here's an example of a correctness proof for the first solution: In all four experiments, we have one balloon appearing four times and four balloons appearing twice.
  4*A+2*(B+C+D+E) = 2*(A+B+C+D+E)+2*A >= 2*(1+2+3+4+5)+2*A = 30+2*A.

  On the other hand, since 1,2,4 ≠ 1,2,5≤9, and 1,3,4 ≠ 1,3,5 ≤ 9, and 1,2,4 ≠ 1,3,4, and 1,2,5 ≠ 1,3,5 the sum of all four is at most 7+8+8+9, so 30+2*A≤32, so A=1.

  "srcmake" wrote a blog post about the solution: www.srcmake.com/home/ponder-this-april-2018 and even prepared a nice video. Thanks for the solution and for keeping it unpublished till the end of the month, so as not to spoil it for other solvers.

  Bert Dobbelaere suggested six experiments to fully determine all nine balloons:

  2,3,4  1,3,5  1,2,6  1,7  2,7  1,8
  

Solvers

• Dan Dima (28/03/18 05:36 PM IDT)
• Guillaume Escamocher (28/03/18 05:43 PM IDT)
• Dieter Beckerle (28/03/18 06:02 PM IDT)
• Serge Thill (28/03/18 06:54 PM IDT)
• Uoti Urpala (28/03/18 08:36 PM IDT)
• Bert Dobbelaere (28/03/18 09:16 PM IDT)
• Pavel Glasnov (28/03/18 09:22 PM IDT)
• Todd Will (28/03/18 10:39 PM IDT)
• Rob Pratt (28/03/18 10:40 PM IDT)
• Muralidhar Seshadri (29/03/18 10:31 AM IDT)
• Hanlin Ren (29/03/18 03:13 PM IDT)
• Alper Halbutogullari (29/03/18 05:10 PM IDT)
• Yash Pote (29/03/18 05:25 PM IDT)
• George W Barnett (29/03/18 09:44 PM IDT)
• Michael Liepelt (29/03/18 11:03 PM IDT)
• Paul Shaw (30/03/18 02:23 AM IDT)
• Hizami Anuar (30/03/18 04:00 AM IDT)
• Kang Jin Cho (30/03/18 05:30 AM IDT)
• Yan-Wu He (30/03/18 05:20 AM IDT)
• Lorenz Reichel (30/03/18 08:24 AM IDT)
• Yuval Nezri (30/03/18 09:52 AM IDT)
• Nguyen Khac Tung (30/03/18 10:29 AM IDT)
• Alex Fleischer (30/03/18 12:30 PM IDT)
• Daniel Chong Jyh Tar (30/03/18 01:12 PM IDT)
• Tetsuo Mioka (30/03/18 04:02 PM IDT)
• Dominik Reichl (30/03/18 06:15 PM IDT)
• Francis Golding (30/03/18 07:34 PM IDT)
• Clive Tong (30/03/18 10:14 PM IDT)
• JJ Rabeyrin (30/03/18 23:22 PM IDT)
• Rogerio Ponce da Silva (31/03/18 02:58 AM IDT)
• Junjiajia Long (31/03/18 09:03 AM IDT)
• Harrison Klein (31/03/18 10:56 AM IDT)
• Lakshman Inkulu (31/03/18 01:40 PM IDT)
• Rickard Björklund (31/03/18 03:25 PM IDT)
• Guangzhong Sun (31/03/18 04:56 PM IDT)
• Andrei Tsygankov (31/03/18 07:10 PM IDT)
• Yuxuan Shui (31/03/18 07:30 PM IDT)
• Ayal Zaks & Noam Zaks (31/03/18 08:46 PM IDT)
• Eden Saig (31/03/18 09:49 PM IDT)
• Joaquim Neves Carrapa (31/03/18 09:56 PM IDT)
• Vladimir M. Milovanović (01/04/18 02:12 AM IDT)
• Graham Hemsley (01/04/18 10:18 AM IDT)
• Anatoliy Vesnin (01/04/18 12:04 PM IDT)
• James Dow Allen (01/04/18 15:16 PM IDT)
• Anoop Ghanwani (01/04/18 07:50 PM IDT)
• Andreas Stiller (01/04/18 09:57 PM IDT)
• Ian Sleightholme (01/04/18 10:00 PM IDT)
• Bryce Fore (02/04/18 12:54 AM IDT)
• Tyler Mullen (02/04/18 05:10 AM IDT)
• Azamat Berdyshev (02/04/18 06:01 AM IDT)
• Paolo Farinelli (02/04/18 06:04 AM IDT)
• Xiu-Han Wang (02/04/18 06:25 AM IDT)
• Parth Trivedi (02/04/18 07:11 AM IDT)
• Xiao Liu (02/04/18 03:50 PM IDT)
• Radu-Alexandru Todor (02/04/18 04:44 PM IDT)
• Patrik Holopainen (02/04/18 09:36 PM IDT)
• Anna Wegloop (02/04/18 10:34 PM IDT)
• Tariq Ramlall (02/04/18 10:43 PM IDT)
• Reiner Martin (02/04/18 11:49 PM IDT)
• Shirish Chinchalkar (03/04/18 12:44 AM IDT)
• Cynthia Beauchemin (03/04/18 02:10 AM IDT)
• Sanandan Swaminathan (03/04/18 04:56 AM IDT)
• Gil Citro (03/04/18 04:57 AM IDT)
• Arnon Amir (03/04/18 05:32 AM IDT)
• Kaifei Chen (03/04/18 05:51 AM IDT)
• Ksg Sarma (03/04/18 07:36 AM IDT)
• Soumitra Agarwal (03/04/18 10:09 AM IDT)
• Chris Nott (03/04/18 10:30 AM IDT)
• Bharat Kumar Aryasomayajula (03/04/18 05:00 PM IDT)
• Amir Sarid (03/04/18 07:04 PM IDT)
• Almog Yair (04/04/18 04:01 AM IDT)
• Shyam Shah (04/04/18 05:27 AM IDT)
• Luke Pebody (04/04/18 05:56 AM IDT)
• Benjamin Lui (04/04/18 03:53 PM IDT)
• Andrei Pilka (04/04/18 04:04 PM IDT)
• Steven Langerwerf (04/04/18 06:37 PM IDT)
• David Friedman (04/04/18 07:24 PM IDT)
• Franciraldo Cavalcante (04/04/18 10:30 PM IDT)
• Klaus Hoffmann (04/04/18 11:13 PM IDT)
• Gerhard&Klaus Hoffmann (04/04/18 11:13 PM IDT)
• Li Li (05/04/18 09:30 AM IDT)
• Davin Choo (05/04/18 03:23 PM IDT)
• Gumpina Rama Krishna Chaitanya (05/04/18 03:51 PM IDT)
• Solomon Liu (05/04/18 06:10 PM IDT)
• Jiao Zi-Nan (05/04/18 06:11 PM IDT)
• Walter Sebastian Gisler (05/04/18 06:48 PM IDT)
• Peter Gerritson (05/04/18 09:25 PM IDT)
• Frank Mayer (06/04/18 04:34 AM IDT)
• Prof.V.P. gohil (06/04/18 12:04 PM IDT)
• Prashant Wankhede (06/04/18 09:55 AM IDT)
• Nadia Vettier Brauner (06/04/18 07:12 PM IDT)
• Tero Patana (07/04/18 12:51 AM IDT)
• Bryce Herdt (07/04/18 07:05 AM IDT)
• Sai Kishore Datti (07/04/18 08:27 AM IDT)
• Sasi Teja Alluri (07/04/18 08:59 AM IDT)
• Dan Ismailescu (07/04/18 04:15 PM IDT)
• David Greer (07/04/18 09:23 PM IDT)
• Motty Porat (07/04/18 10:49 PM IDT)
• J. Eric Ivancich (08/04/18 01:20 AM IDT)
• Orr Zeitler (08/04/18 07:39 AM IDT)
• Bart De Vylder (08/04/18 11:59 AM IDT)
• Guenter Nowak (08/04/18 04:18 PM IDT)
• Kandala Viswakanth (08/04/18 04:22 PM IDT)
• Pål Hermunn Johansen (08/04/18 09:01 PM IDT)
• Arthur Vause (09/04/18 12:06 AM IDT)
• Brian Mathason (09/04/18 12:35 AM IDT)
• Tom Sirgedas (09/04/18 07:02 AM IDT)
• Michael Chirozzi (10/04/18 00:11 AM IDT)
• Chris Shannon (10/04/18 09:09 AM IDT)
• Mathias Schenker (10/04/18 11:52 AM IDT)
• Vladimir Volevich (10/04/18 12:01 PM IDT)
• Rafael Rubio (10/04/18 06:03 PM IDT)
• William Heller (10/04/18 10:29 PM IDT)
• Erik Hostens (11/04/18 11:10 AM IDT)
• Sri Mallikarjun J. (12/04/18 04:34 PM IDT)
• Liubing Yu (12/04/18 05:39 PM IDT)
• Claudio Hüni (13/04/18 10:09 AM IDT)
• Robert Lang (13/04/18 12:47 PM IDT)
• Gabriel Maia (13/04/18 06:45 PM IDT)
• Hasan Unlu (14/04/18 11:24 AM IDT)
• Susanne Wienand (14/04/18 11:25 AM IDT)
• Joonsoo Lee (14/04/18 08:52 PM IDT)
• Jim Clare (15/04/18 03:00 AM IDT)
• Govind A N (15/04/18 06:09 AM IDT)
• Joehyun Kim (15/04/18 03:19 PM IDT)
• Surya Kareenahalli (15/04/18 06:28 PM IDT)
• Tiffany Lee (15/04/18 06:32 PM IDT)
• Seo Yeong Kwag (15/04/18 08:37 PM IDT)
• Adrienne Ko (15/04/18 09:55 PM IDT)
• Pradeep Chandra Gorrepati (16/04/18 12:53 PM IDT)
• Nir Lavee & Omer Shechter (16/04/18 03:52 PM IDT)
• Yongxing Jim Wang (17/04/18 05:46 AM IDT)
• Marcel Caria (17/04/18 12:58 PM IDT)
• Karl D’Souza (17/04/18 08:47 PM IDT)
• Jiajun Li (18/04/18 04:02 PM IDT)
• Erick Lima (18/04/18 06:38 PM IDT)
• Rudy Cortembert (19/04/18 11:57 AM IDT)
• Esmie Jose (19/04/18 10:56 PM IDT)
• Joseph DeVincentis (20/04/18 08:48 PM IDT)
• Florian Fischer (21/04/18 01:20 AM IDT)
• Roland Postle (21/04/18 01:56 AM IDT)
• Siddhartha Srivastava (22/04/18 03:14 PM IDT)
• Luo Jin (23/04/18 06:58 AM IDT)
• Ioan Marius Popdan (23/04/18 11:07 PM IDT)
• David F.H. Dunkley (24/04/18 12:35 AM IDT)
• Amit Bhatia (24/04/18 02:56 PM IDT)
• Shouky Dan & Tamir Ganor (24/04/18 15:03 PM IDT)
• Karim Alaoui (24/04/18 07:55 PM IDT)
• Laila Echammari & Anders Bisbjerg Madsen (24/04/18 10:17 PM IDT)
• Daniëlle van den Berg (25/04/18 04:26 PM IDT)
• Kai Guttmann (26/04/18 01:38 AM IDT)
• Charles Joscelyne (26/04/18 10:09 AM IDT)
• Alexander Raß (26/04/18 04:02 PM IDT)
• Stephen Dalton (26/04/18 11:21 PM IDT)
• Ritesh Ranjan (26/04/18 11:33 AM IDT)
• Anees Shaikh (27/04/18 12:34 PM IDT)
• Jio Jeong (28/04/18 05:24 PM IDT)
• Jae Yong Park (29/04/18 06:21 PM IDT)
• Christian Kuehnert (30/04/18 09:18 AM IDT)
• Rainer Rosenthal (30/04/18 08:50 PM IDT)
• Hugo Pfoertner (30/04/18 08:54 PM IDT)
• Buzea Alina (30/04/18 09:05 PM IDT)
• Oscar Volpatti (01/05/18 06:01 AM IDT)