Ponder This Challenge - August 2016 - Finding bags of counterfeit coins

Ponder This Challenge:

A king receives 10 bags of N golden coins each. Each coin should weigh exactly 10 grams, but some bags contain (only) counterfeit coins that weigh exactly 9 grams each.

If N>=512 then one can identify the counterfeit bags using a single measurement with an accurate weighing scale. (How?)

Our challenge this month is to find a way to identify the counterfeit bags, when we know that there are at most three such bags out of the ten, and when N=174.

Bonus '*' for solving it with even smaller N.

Solution

• Click here to view the solution

  A solution for the first question (find an arbitrary subset of counterfeit bags) can be found by weighing 2**i coins from the i-th bag (1,2,4,8,16,32,64,128,256,512). The number of missing grams is a binary encoding of the set of counterfeit bags. One can do better than 512 by using the Conway-Guy sequence (see http://oeis.org/A096858).

  To solve the second problem (up to three bags), we need to find a set of 10 numbers all <= N where the sum of all the subsets of at most three items are different.

  One can look for such numbers by backtracking. The first answer you'd get is 1,2,4,8,84,103,122,146,160,174; but there are more:
  5,10,20,40,75,113,150,161,162,174
  5,10,20,40,80,106,150,172,173,174
  5,10,20,40,80,107,151,153,155,174
  5,10,20,40,80,116,152,160,163,174
  5,10,20,40,80,126,150,152,173,174
  5,10,89,109,129,150,162,168,171,174
  6,12,24,46,86,115,166,168,169,170
  6,12,24,48,88,117,170,172,173,174
  6,12,24,48,90,121,152,172,173,174
  7,14,28,56,94,133,166,170,172,174
  7,14,28,56,105,138,170,171,172,174
  7,14,28,61,94,133,170,171,172,174
  10,20,40,80,85,136,160,172,173,174
  12,13,24,61,99,134,154,164,169,174
  13,26,38,50,97,100,166,168,170,174

  To get a '*' you should have found a better solution:
  5,10,20,40,75,112,149,160,161,173
  5,10,20,40,80,121,155,157,164,173
  5,10,20,40,85,114,152,156,160,173
  3,6,12,24,82,92,127,132,152,172
  3,6,12,24,92,111,130,164,168,172
  5,10,20,40,75,103,150,166,169,172
  5,10,20,40,75,124,148,150,171,172
  5,10,20,40,86,95,138,154,170,172
  6,12,24,46,86,115,168,169,170,172
  5,10,20,40,75,123,124,145,147,171
  5,10,20,40,75,123,147,149,170,171
  5,10,20,40,80,117,150,159,163,171
  5,10,20,40,75,118,152,154,161,170
  5,10,20,40,75,119,151,157,163,170
  5,10,20,40,75,122,146,148,169,170
  6,12,24,48,90,125,145,160,165,170
  7,14,28,56,101,134,166,167,168,170
  10,20,40,65,80,138,149,150,166,172
  10,20,40,80,85,138,150,166,169,172
  20,40,45,80,90,148,160,166,169,172
  24,26,47,48,96,131,151,161,166,171
  5,10,20,40,80,118,150,156,162,169
  5,10,20,40,75,121,145,147,168,169
  7,14,28,56,100,133,165,166,167,169
  5,10,20,40,75,102,145,164,166,168
  5,10,20,40,75,116,150,152,159,168
  5,10,20,40,80,109,147,151,155,168
  10,20,40,45,80,122,141,160,164,168
  16,23,32,64,98,128,148,158,163,168
  5,10,20,40,75,103,144,147,150,166
  5,10,20,40,80,114,148,150,157,166
  5,10,20,40,75,113,145,151,157,164
  5,10,20,40,80,111,143,149,155,162
  5,10,20,40,75,109,143,145,152,161
  and the best solution ('**') is 5,10,20,40,75,106,138,144,150,157

Solvers

• **Lorenz Reichel (31/07/2016 05:27 PM IDT)
• **Paolo Farinelli (31/07/2016 08:11 PM IDT)
• **Robert Gerbicz (31/07/2016 09:36 PM IDT)
• **Oleg Vlasii (31/07/2016 10:50 PM IDT)
• **Uoti Urpala (31/07/2016 11:48 PM IDT)
• **Florian Fischer (01/08/2016 01:59 AM IDT)
• **Hanlin Ren (01/08/2016 06:21 PM IDT)
• **Bert Dobbelaere (01/08/2016 06:43 PM IDT)
• *James Dow Allen (01/08/2016 11:04 PM IDT)
• Mathias Schenker (01/08/2016 11:12 PM IDT)
• **Tom Sirgedas (02/08/2016 01:45 AM IDT)
• Isaac Simmons (02/08/2016 05:03 AM IDT)
• Thomas Egense (02/08/2016 10:10 AM IDT)
• Clive Tong (02/08/2016 10:33 AM IDT)
• *Benjamin Lui (02/08/2016 01:54 PM IDT)
• **Amos Guler (03/08/2016 12:20 AM IDT)
• **David F.H. Dunkley (03/08/2016 02:38 AM IDT)
• Shirish Chinchalkar (03/08/2016 04:22 AM IDT)
• **Sean Egan (03/08/2016 04:45 AM IDT)
• Ran Sharon (03/08/2016 06:45 AM IDT)
• **Toke Eskildsen (03/08/2016 08:02 AM IDT)
• *Aditya Gurunathan (03/08/2016 11:45 AM IDT)
• *Liubing Yu (03/08/2016 06:56 PM IDT)
• **Andreas Stiller (04/08/2016 03:49 AM IDT)
• *Balakrishnan Varadarajan (04/08/2016 05:29 AM IDT)
• **Pål Hermunn Johansen (04/08/2016 10:25 PM IDT)
• **Dieter Beckerle (05/08/2016 12:08 AM IDT)
• *Sergey E. Koposov (05/08/2016 01:27 AM IDT)
• Jing Xiao (05/08/2016 05:40 AM IDT)
• Koon Hui Geoffrey Goh (05/08/2016 12:50 PM IDT)
• Reiner Martin (06/08/2016 08:07 AM IDT)
• *Raymond Lo (06/08/2016 11:36 AM IDT)
• **Wilder Boyden (06/08/2016 10:31 PM IDT)
• **Serge Batalov (07/08/2016 10:00 PM IDT)
• Michael D Schuresko (08/08/2016 12:04 AM IDT)
• *Harald Bögeholz (08/08/2016 12:17 PM IDT)
• **Daniel Chong Jyh Tar (08/08/2016 12:44 PM IDT)
• Dejan Stakić (08/08/2016 07:18 PM IDT)
• **José Eduardo Gaboardi de Carvalho (09/08/2016 08:10 PM IDT)
• Todd Will (10/08/2016 12:12 AM IDT)
• **Kang Jin Cho (10/08/2016 09:41 AM IDT)
• Ayaskant Pani (10/08/2016 11:15 PM IDT)
• Tamir Ganor & Shouky Dan (12/08/2016 11:01 AM IDT)
• *Joseph DeVincentis (12/08/2016 10:44 PM IDT)
• **Francis Golding (13/08/2016 11:27 AM IDT)
• Jimmy Waters (13/08/2016 01:45 PM IDT)
• Peter Gerritson (14/08/2016 06:33 PM IDT)
• **David Greer (15/08/2016 12:53 AM IDT)
• *Yuan Li (15/08/2016 11:09 AM IDT)
• *Yuan Li & Ye Fan (15/08/2016 11:09 AM IDT)
• **Aviv Nisgav (15/08/2016 03:00 PM IDT)
• **Gary M. Gerken (16/08/2016 05:09 AM IDT)
• **Yan-Wu He (16/08/2016 07:59 AM IDT)
• Jason Lee (16/08/2016 07:37 PM IDT)
• **Siddharth Joshi (18/08/2016 02:14 PM IDT)
• Itay Hazan (19/08/2016 10:44 AM IDT)
• Fabio Michele Negroni (20/08/2016 09:20 PM IDT)
• Nagendra Gulur (21/08/2016 06:19 AM IDT)
• **Arthur Vause (21/08/2016 05:33 PM IDT)
• **Bryce Fore (22/08/2016 12:12 AM IDT)
• **Emir Haleva (22/08/2016 08:47 AM IDT)
• Alex Fleischer (22/08/2016 10:47 AM IDT)
• *Jim Clare (22/08/2016 01:21 PM IDT)
• **Teake Nutma (22/08/2016 01:44 PM IDT)
• *Claudio Baiocchi (23/08/2016 12:20 PM IDT)
• Nigel Brumpton (24/08/2016 11:39 AM IDT)
• *David Vainapel (26/08/2016 09:57 AM IDT)
• Fabio Filatrella (26/08/2016 12:27 PM IDT)
• *Gale Greenlee (26/08/2016 05:48 PM IDT)
• J. Eric Ivancich (26/08/2016 07:43 PM IDT)
• **Zoltan Haindrich (26/08/2016 10:22 PM IDT)
• **Jess Thrysoee (27/08/2016 03:27 PM IDT)
• Maple Guan July (27/08/2016 09:59 PM IDT)
• **Daniel Bitin (27/08/2016 11:22 PM IDT)
• *Nyles Heise (28/08/2016 07:11 AM IDT)
• Ante Turudic (28/08/2016 08:56 PM IDT)
• **Motty Porat (29/08/2016 12:07 AM IDT)
• Julian Ma & Louise Lam (29/08/2016 02:39 AM IDT)
• **Tommi Libdgren (29/08/2016 10:34 AM IDT)
• Jesse Rearick (30/08/2016 04:19 PM IDT)
• *Steve Dalton (30/08/2016 05:14 PM IDT)
• **LaurV (30/08/2016 08:31 PM IDT)
• **Armin Krauss (31/08/2016 11:44 AM IDT)
• *Jens Voss (31/08/2016 03:24 PM IDT)
• *Erik Wünstel (31/08/2016 05:07 PM IDT)
• *Radu-Alexandru Todor (31/08/2016 10:19 PM IDT)
• **Hugo Pfoertner (01/09/2016 12:26 AM IDT)
• **Rogerio Ponce da Silva (01/09/2016 05:55 PM IDT)