Avgvst 2016

Batalov · 2016-07-31, 16:37

https://www.research.ibm.com/haifa/p...ugust2016.html

a1call · 2016-07-31, 19:12

That does not make sense. The wording implies that the scale is not a balance scale.
With a single Measurment reading for 10 bags any Measurment not involving any of the 10 bags will leave unmeasured bags unknown. If all 10 bags are measured at once then there would be no way to distinguish between them. The best you could do is to determine the number of counterfeit bags but not to know which specific bags are counterfeit.

BTW There seem to be a typo (or two) in the title or am I missing something.

firejuggler · 2016-07-31, 19:42

The wording imply a scale with 2 plate.

Batalov · 2016-07-31, 19:43

Quote:

Originally Posted by a1call

... or am I missing something.

That one.

Batalov · 2016-07-31, 19:47

Quote:

Originally Posted by Ponder This

...using a single measurement with an accurate weighing scale.

LMGTFY ... "an accurate weighing scale" -->

firejuggler · 2016-07-31, 20:09

ah, this *accurate scale* has a limit?

Batalov · 2016-07-31, 20:35

None is implied by PT, but it is clear that within this problem a 20.470 kg limit will do fine, with precision of 1 g.
Such scales are quite routine. Our labs have scales that are doing a few grams but up to the fifth, I think, decimal digit behind dot, so they are more precise.

a1call · 2016-08-01, 02:48

The problem implies that for N<1024 it would take more than a single Measurment to solve. So the actual problem would require more than a single Measurment and no maximum is specified which makes the solution trivial. The problem is the N>=1024 being solved in a single Measurment does not make sense specially with an unknown number of fake coin bags.

I just don't understand the parameters of the problem.

LaurV · 2016-08-01, 03:20

The 1024 is just an example, same as they use to give every month examples, for every challenge. It does not imply that you would need more measurements if N is smaller. It may be true or not, but the example itself implies nothing. Of course, we learned in elementary school how to solve the "example". In fact, the condition is very weak, even if N>=512, you could do it with a single scale very simply, you take 2^(n-1) coins from the n-th bag, and you have only 10 bags... So you don't need N >= 1024. When N>=512, you could take 1 coin from the first bag, 2 from the second, 4 from the third, etc, and 512 from the 10th bag, then you scale them together. At the end you have 1023 coins and expect to get 10230 grams if all coins are good, but you will get less. You get one gram less for each bad coin. Write the difference in binary and you know exactly how many bags have wrong coins, and which bags they are. If for example you get 29 grams less, which in binary is 11101, you know that there are 4 bags with bad coins, and those are the first, the third, forth and fifth.

Now, you have less coins in each bag. But you also know that there are at most 3 bags with bad coins. So, it should not be difficult to devise a scheme where you can point to the cheating bags, with only one scaling.

This problem, same like the one last month, is actually very nice.

a1call · 2016-08-01, 03:28

Thank you LaurV,
Somehow I was under the impression that bags where to be weighted and not the coins.
The example does make sense now.
Thanks again for the clarification.

R. Gerbicz · 2016-08-04, 19:15

New update:

"Update (4/8): To get a '**' find a solution for the minimal N."

2016-07-31, 16:37	#1
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2661₁₆ Posts	Avgvst 2016 https://www.research.ibm.com/haifa/p...ugust2016.html

2016-07-31, 19:12	#2
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2×19×59 Posts	That does not make sense. The wording implies that the scale is not a balance scale. With a single Measurment reading for 10 bags any Measurment not involving any of the 10 bags will leave unmeasured bags unknown. If all 10 bags are measured at once then there would be no way to distinguish between them. The best you could do is to determine the number of counterfeit bags but not to know which specific bags are counterfeit. BTW There seem to be a typo (or two) in the title or am I missing something. Last fiddled with by a1call on 2016-07-31 at 19:17

2016-08-01, 03:20	#9
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2×17×293 Posts	The 1024 is just an example, same as they use to give every month examples, for every challenge. It does not imply that you would need more measurements if N is smaller. It may be true or not, but the example itself implies nothing. Of course, we learned in elementary school how to solve the "example". In fact, the condition is very weak, even if N>=512, you could do it with a single scale very simply, you take 2^(n-1) coins from the n-th bag, and you have only 10 bags... So you don't need N >= 1024. When N>=512, you could take 1 coin from the first bag, 2 from the second, 4 from the third, etc, and 512 from the 10th bag, then you scale them together. At the end you have 1023 coins and expect to get 10230 grams if all coins are good, but you will get less. You get one gram less for each bad coin. Write the difference in binary and you know exactly how many bags have wrong coins, and which bags they are. If for example you get 29 grams less, which in binary is 11101, you know that there are 4 bags with bad coins, and those are the first, the third, forth and fifth. Now, you have less coins in each bag. But you also know that there are at most 3 bags with bad coins. So, it should not be difficult to devise a scheme where you can point to the cheating bags, with only one scaling. This problem, same like the one last month, is actually very nice. Last fiddled with by LaurV on 2016-08-01 at 03:49

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
July 2016	Xyzzy	Puzzles	4	2016-08-06 22:51
June 2016	Xyzzy	Puzzles	16	2016-07-07 02:51
EM 2016	Cybertronic	Soap Box	1	2016-06-26 21:03
May 2016	Xyzzy	Puzzles	6	2016-06-06 19:02
April 2016	Xyzzy	Puzzles	10	2016-05-05 05:42

2016-07-31, 19:42	#3
firejuggler "Vincent" Apr 2010 Over the rainbow 2·3·11·43 Posts	The wording imply a scale with 2 plate.

2016-07-31, 20:09	#6
firejuggler "Vincent" Apr 2010 Over the rainbow 2·3·11·43 Posts	ah, this accurate scale has a limit?

2016-07-31, 20:35	#7
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23141₈ Posts	None is implied by PT, but it is clear that within this problem a 20.470 kg limit will do fine, with precision of 1 g. Such scales are quite routine. Our labs have scales that are doing a few grams but up to the fifth, I think, decimal digit behind dot, so they are more precise.

2016-08-01, 02:48	#8
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2242₁₀ Posts	The problem implies that for N<1024 it would take more than a single Measurment to solve. So the actual problem would require more than a single Measurment and no maximum is specified which makes the solution trivial. The problem is the N>=1024 being solved in a single Measurment does not make sense specially with an unknown number of fake coin bags. I just don't understand the parameters of the problem.

2016-08-01, 03:28	#10
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 4302₈ Posts	Thank you LaurV, Somehow I was under the impression that bags where to be weighted and not the coins. The example does make sense now. Thanks again for the clarification.

2016-08-04, 19:15	#11
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 11000100000₂ Posts	New update: "Update (4/8): To get a '**' find a solution for the minimal N."