[Yoruichi-san]

1) You have 17 objects arranged single file in a circle. You know 2 of these objects have the property W. You have a detector which will run a scan on exactly 5 adjacent objects and tell you how many of the 5 have the property W (but not which ones, of course). What is the minimum number of scans that would guarantee you find out which 2 objects have the property W?

2) Again, you have 17 objects arranged single file in a circle. You know 2 have the property W, and you also know 3 have the property D. Your detector also has a setting for detecting D, but you can only run on one setting at a time (i.e. you can either scan the 5 target objects for W or D, but not both simultaneously). What is the minimum number of scans that would guarantee you find which 2 objects have the property W and which 3 objects have the property D?

[Guest]

This IS powerful! Correct me if I'm wrong: if the result is 000, then we have to find 2 objects in 9ABCDEFG, which I think will take 5 tests--still 8 overall, as there was no #4 above.

I think we can overcome this:

Change the previous 3 test's order:

#1 01234

#2 45678

#3 23456

After #2 if we get 00 then no need to #3.

Then we will have 5 tests unused, this is enough for 2 W's in 8 objects.

[Guest]

8

for (1)

[Guest]

8

for (1)

I had posted a less result above, yourishi hasn't approved it but didn't find a flaw.

[Yoruichi-san]

I had posted a less result above, yourishi hasn't approved it but didn't find a flaw.

Lol...sorry, been busy...and I'm no one's ishi... ;P

Anyways, I like both your solution and Capt. Ed's...there's more than one method to find the W in that many moves actually...and you've come upon several good ones . To be honest, I think you guys have figured this out better than I have...:whistling:...What are your expectation values for the number of scans with those methods?

And feel free to move on to 2)

[Guest]

And feel free to move on to 2)

I have found a solution to guarantee you find 2W's in 7 scans. Please correct me if I'm wrong

First scan is always 12345. If the answer is 2 then <7 scans is trivial.

If the answer is 0. It's pretty easy. We now divide the remaining 12 boxes into three groups of 4 by testing 56789 and 14/15/16/17/1. Based on the results, we will know there is either 1,2, or 0 in 6789, 14/15/16/17 or 10/11/12/13. There will also be plenty of known empty boxes next to the sequence of 4 boxes that contain a W. For example, lets assume that 56789 and 14/15/16/17/1 both return 1. To determine where in 6789 W is, we test 34567. If we get 0, then we test 45678. If 0 again then W is in 9. If we get a 1 on the test of 34567, then we test 23456 to determine whether W is in 6 or 7. Repeat this method for 14/15/16/17/1 and we get an answer in 7 scans.

The hard part is if we get an answer of 1 for the first test. In this case, the next test is 9/10/11/12/13. If that test returns 1, then we test 56789. If 56789 returns 0, we know that there is exactly 1 W in 1234 and 1 W in 10/11/12/13. It will take up to 2 scans to determine the location in each of these four box sequences, getting us our answer in 7 total scans. If the answer to 56789 is 2, then we are done as W must be in 5 and 9. If the answer to 56789 is 1 then we know that there is either a W in 5 and a W in 10/11/12/13 or a W in 9 and a W in 1234. The next test is 17/1234. If we get 0 then W is in 5 and we have 3 tests left for 10/11/12/13. If the result of 17/1234 is 1, then we know W is in 9 and we have 3 test left for 1234.

The toughest scenario is if 12345 returns 1 and 9/10/11/12/13 returns 0. Our next test is, again, 56789. If we get a result of 2, then we know W is in exactly 5 and a W in 678, with plenty of tests left. If 56789 returns 1, we know that either there is W in 5 and a W in 14/15/16/17 or a W in 1234 and one in 678. Our 4th test is 789/10/11. If we get a 0 back, the fifth test is 6789/10. If 0 again, then W is in 5 and we have 2 tests left to determine where W is in 14/15/16/17. If the fifth test returns 1, then we know W is in 6 and we have 2 tests left for 1234. If the fourth test of 789/10/11 returns 1, then we test 89/10/11/12 to determine whether W is in 7 or 8 and we have 2 tests left for 1234.

I think I covered all possibilities and I never had to go past 7 tests. I hope you were all able to follow.

[Guest]

I have found a solution to guarantee you find 2W's in 7 scans. Please correct me if I'm wrong

First scan is always 12345. If the answer is 2 then <7 scans is trivial.

If the answer is 0. It's pretty easy. We now divide the remaining 12 boxes into three groups of 4 by testing 56789 and 14/15/16/17/1. Based on the results, we will know there is either 1,2, or 0 in 6789, 14/15/16/17 or 10/11/12/13. There will also be plenty of known empty boxes next to the sequence of 4 boxes that contain a W. For example, lets assume that 56789 and 14/15/16/17/1 both return 1. To determine where in 6789 W is, we test 34567. If we get 0, then we test 45678. If 0 again then W is in 9. If we get a 1 on the test of 34567, then we test 23456 to determine whether W is in 6 or 7. Repeat this method for 14/15/16/17/1 and we get an answer in 7 scans.

The hard part is if we get an answer of 1 for the first test. In this case, the next test is 9/10/11/12/13. If that test returns 1, then we test 56789. If 56789 returns 0, we know that there is exactly 1 W in 1234 and 1 W in 10/11/12/13. It will take up to 2 scans to determine the location in each of these four box sequences, getting us our answer in 7 total scans. If the answer to 56789 is 2, then we are done as W must be in 5 and 9. If the answer to 56789 is 1 then we know that there is either a W in 5 and a W in 10/11/12/13 or a W in 9 and a W in 1234. The next test is 17/1234. If we get 0 then W is in 5 and we have 3 tests left for 10/11/12/13. If the result of 17/1234 is 1, then we know W is in 9 and we have 3 test left for 1234.

The toughest scenario is if 12345 returns 1 and 9/10/11/12/13 returns 0. Our next test is, again, 56789. If we get a result of 2, then we know W is in exactly 5 and a W in 678, with plenty of tests left. If 56789 returns 1, we know that either there is W in 5 and a W in 14/15/16/17 or a W in 1234 and one in 678. Our 4th test is 789/10/11. If we get a 0 back, the fifth test is 6789/10. If 0 again, then W is in 5 and we have 2 tests left to determine where W is in 14/15/16/17. If the fifth test returns 1, then we know W is in 6 and we have 2 tests left for 1234. If the fourth test of 789/10/11 returns 1, then we test 89/10/11/12 to determine whether W is in 7 or 8 and we have 2 tests left for 1234.

I think I covered all possibilities and I never had to go past 7 tests. I hope you were all able to follow.

I left out one scenario:

If 12345 returns 1, 9/10/11/12/13 returns 0 and 56789 returns 0 then we know 1 W is in 1234 and 1 W is in 14/15/16/17. We still have four scans left, and will use 2 for each group.