August 2016
<<July August September>>
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