[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?

[Joe's Student]

Hmm... this is oddly familiar. I wonder what gave you this idea.... .

Edited May 17, 2009 by Joe's Student

[Guest]

3

[Guest]

The first answer is three

[Guest]

Is the second one 15?

[Guest]

Why not:

1)3 and

2)6?

I see nothing that wrong in these solutions.

[Guest]

Could someone explain how they arrived at 3 for the first answer?

In my understanding, as an example, say you eliminate 5 duds with the first scan, another 5 in the second, and with the third scan get one W reading. Now you're left with one W in five, and one W in two (of the unscanned). What am I missing?

[Guest]

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?

Is it possible for one object to have both W and D properties?

[Yoruichi-san]

Hmm... this is oddly familiar. I wonder what gave you this idea.... .

:whistling:

No reason BD can't benefit from my creative Madness as well ;P

Is it possible for one object to have both W and D properties?

No. Sorry, forgot to specify that in the OP.

And you're looking for the worst case scenario, not the best one (i.e. all 15 you scan are duds). There is no guarantee the 2 W are next to each other and you're going to scan the other 15. You want to come up with a strategy that allows you to minimize your # of scans no matter where the W's are.

Edited May 18, 2009 by Yoruichi-san

[CaptainEd]

Let's number the objects 1-17. Let's plan on testing the five centered on 3, 8, and 13. Here are the possible results:

2 (don't need to go on the 8 and 13); it will take 4 more tests to locate the 2 = 5 tests

1,1 (don't need to go on to 13); will take 3 tests to locate the 1 in a group of 5, thus 6 more tests = 8

1,0,1; need 3 more tests twice = 9

1,0,0; need 3 to find the one in 1-5, 1 to find the one in 16,17 = 7

0,2 (don't need to go on to 13). need 4 more to find the two = 6 tests

0,1,1; need 3 more twice = 9

0,1,0; need 3 more and 1 more

0,0,1; need 3 more and 1 more

0,0,0; we know it's 16,17

The maximum number of tests is 9.

Somebody doesn't get the problem. Maybe it's me.

[Guest]

Let's number the objects 1-17. Let's plan on testing the five centered on 3, 8, and 13. Here are the possible results:

1,0,1; need 3 more tests twice = 9

0,1,1; need 3 more twice = 9

The maximum number of tests is 9.

I think that in these worst arrangements, 8 testings will be enough.

Test first 5 object, if you get 1, then leave 2 objects just beside these and test next 5. (#8,9..12) If you get 1, no need to test others and 2+6=8 is enough.

If you get 0 on these first or second tests, then after third test, you will have two "5" group of objects, those are adjacent. In your terms: 1,0,0 or 0,1,1.

Lets call them 0123456789. We have one positive in 01234 and other in 56789, and have used 3 tests.

Now test 34567, at worst scenario, we get 1, otherwise, it's easy. Then test 0-1-2 in two tests, if you get 1 then test 5-6-7 in two tests and get all at total 8 tests. If you get 0 after 0-1-2, then test 8-9, you will get 1 because there is one in 34567 and none in 012 so 8-9 must be 1. Then test 3-4 and get all at 8 tests.

I hope I've managed to explain this thoroughly.

I'll work on second part when have time.

[CaptainEd]

I think that in these worst arrangements, 8 testings will be enough.

Test first 5 object, if you get 1, then leave 2 objects just beside these and test next 5. (#8,9..12) If you get 1, no need to test others and 2+6=8 is enough.

If you get 0 on these first or second tests, then after third test, you will have two "5" group of objects, those are adjacent. In your terms: 1,0,0 or 0,1,1.

Lets call them 0123456789. We have one positive in 01234 and other in 56789, and have used 3 tests.

Now test 34567, at worst scenario, we get 1, otherwise, it's easy. Then test 0-1-2 in two tests, if you get 1 then test 5-6-7 in two tests and get all at total 8 tests. If you get 0 after 0-1-2, then test 8-9, you will get 1 because there is one in 34567 and none in 012 so 8-9 must be 1. Then test 3-4 and get all at 8 tests.

I hope I've managed to explain this thoroughly.

I'll work on second part when have time.

Good Job!

You've made the worst case (two separated groups, each with 1, requiring 6 more tests) happen early (ie. after only 2 tests), so that the total is 8. And you've made the next worst case (two adjacent groups, each with 1) solvable in 5 more tests, rather than 6.

(edited to correct formatting)

Edited May 18, 2009 by CaptainEd

[Yoruichi-san]

CaptainEd and Nobody have made good progress . In light of the observations, let me tack on an additional question: Can you find a strategy that minimizes the expected number of scans, given that all objects have equal probability of being W?

[Guest]

Just saw this and it's pretty late here, but the first thing that comes to my mind is

I could be wrong but... working by elimination from the sides.

P(W) = 2/17

4 - 2-6

9 - 7-11

14 - 12-16

(3 scans)

Eliminate: 1/17

P(W) = 2/15

5 - 3-7

13 - 11-15

(2 scans)

Eliminate: 2/16/7/11

P(W) = 2/11

6 - 4-8

12 - 10-14

(2 scans)

Eliminate: 3/15/10/8/9

P(W) = 2/6

And so forth. If my calculations are correct, it takes about 9 steps to confirm it - more than the 8 suggested by nobody. Hmm... What if we scatter it?

Oh well, sleep now. Will work on it more tomorrow.

[CaptainEd]

I think that in these worst arrangements, 8 testings will be enough.

Test first 5 object, if you get 1, then leave 2 objects just beside these and test next 5. (#8,9..12) If you get 1, no need to test others and 2+6=8 is enough.

If you get 0 on these first or second tests, then after third test, you will have two "5" group of objects, those are adjacent. In your terms: 1,0,0 or 0,1,1.

Lets call them 0123456789. We have one positive in 01234 and other in 56789, and have used 3 tests.

Now test 34567, at worst scenario, we get 1, otherwise, it's easy. Then test 0-1-2 in two tests, if you get 1 then test 5-6-7 in two tests and get all at total 8 tests. If you get 0 after 0-1-2, then test 8-9, you will get 1 because there is one in 34567 and none in 012 so 8-9 must be 1. Then test 3-4 and get all at 8 tests.

I hope I've managed to explain this thoroughly.

I'll work on second part when have time.

Now that I try to work on Y-san's question about minimized expectation,

how you locate 2 balls in 10. That is, when you have

1 in 01234

1 in 56789

1 in 34567 (the worst case, as you say)

I don't know what it means to test 0-1-2 in 2 tests.

Edited May 27, 2009 by CaptainEd

[Guest]

Now that I try to work on Y-san's question about minimized expectation,

how you locate 2 balls in 10. That is, when you have

1 in 01234

1 in 56789

1 in 34567 (the worst case, as you say)

I don't know what it means to test 0-1-2 in 2 tests.

Sorry, how silly am I? There is a serious flaw. I can test 0-1-2 and get which of them is + in 2 tests if I know that one of them is quite +. But I don't know this. So at present 9 tests are required.

[CaptainEd]

Sorry, how silly am I? There is a serious flaw. I can test 0-1-2 and get which of them is + in 2 tests if I know that one of them is quite +. But I don't know this. So at present 9 tests are required.

Nobody, you hit the key--solving adjacent groups in 5 rather than 6 is a worthy and achievable goal.

Background:

we've tested 01234 and got "1"

we've tested 56789 and got "1"

I'll abbreviate that result as

01234-56789

meaning that there is one ball in 01234 and one in 56789.

Per Nobody, our next test is

(#1) 34567

and, as he said, it's easy if we get 0 or 2. The worst case is a result of 1. There are two cases:

012-567 OR 34-89

We want to solve it in 5 more tests

(#2) 12345

results could be

2: 12-5, solve in 1 more

0: 0-67, solve in 1 more

1: 12-5 OR 34-89

(#3) 45678

2:4-8 (done)

0:3-9 (done)

1:12-5 OR 4-8

(#4) 1

1:1-5 (done)

0:2-5 OR 4-8

(#5) 12

1:2-5 (done)

0:4-8 (done)

I'm even more strongly convinced that 8 is the maximum required for the W problem. (I imagine D being far, far away...)

edit: oops, I'm wrong, result of #3:1 yields 12-5 OR 3-8 OR 4-9. Still checking...

Edited May 27, 2009 by CaptainEd

[Guest]

Let's number the objects 1-17. Let's plan on testing the five centered on 3, 8, and 13. Here are the possible results:

2 (don't need to go on the 8 and 13); it will take 4 more tests to locate the 2 = 5 tests

1,1 (don't need to go on to 13); will take 3 tests to locate the 1 in a group of 5, thus 6 more tests = 8

1,0,1; need 3 more tests twice = 9

1,0,0; need 3 to find the one in 1-5, 1 to find the one in 16,17 = 7

0,2 (don't need to go on to 13). need 4 more to find the two = 6 tests

0,1,1; need 3 more twice = 9

0,1,0; need 3 more and 1 more

0,0,1; need 3 more and 1 more

0,0,0; we know it's 16,17

The maximum number of tests is 9.

Somebody doesn't get the problem. Maybe it's me.

you cant tell because the w's and d's are at random so you dont know exactly how many times you have to scan them to find them so it could be one or it could be four so u never kno for the d's and then you have to scan them again for the w's so it would be a mystery unless you knew where they were

[CaptainEd]

Nobody, you hit the key--solving adjacent groups in 5 rather than 6 is a worthy and achievable goal.

I'm even more strongly convinced that 8 is the maximum required for the W problem. (I imagine D being far, far away...)

edit: oops, I'm wrong, result of #3:1 yields 12-5 OR 3-8 OR 4-9. Still checking...

Background:

we've tested 01234 and got "1"

we've tested 56789 and got "1"

I'll abbreviate that result as 01234-56789

meaning that there is one ball in 01234 and one in 56789.

Per Nobody, our next test is (#1) 34567

and, as he said, it's easy if we get 0 or 2. The worst case is a result of 1. There are two cases:

012-567 OR 34-89

We want to solve it in 5 more tests

(#2) 12345

results could be

2: 12-5, solve in 1 more

0: 0-67, solve in 1 more

1: 12-5 OR 34-89

(#3) 45678

2:4-8 (done)

0:3-9 (done)

1:12-5 OR 3-8 OR 4-9

(#4) 89

1:3-8 OR 4-9 solve in 1 more

0:12-5 solve in 1 more

[CaptainEd]

Background:

we've tested 01234 and got "1"

we've tested 56789 and got "1"

I'll abbreviate that result as 01234-56789

meaning that there is one ball in 01234 and one in 56789.

Per Nobody, our next test is (#1) 34567

and, as he said, it's easy if we get 0 or 2. The worst case is a result of 1. There are two cases:

012-567 OR 34-89

We want to solve it in 5 more tests

(#2) 12345

results could be

2: 12-5, solve in 1 more

0: 0-67, solve in 1 more

1: 12-5 OR 34-89

(#3) 45678

2:4-8 (done)

0:3-9 (done)

1:12-5 OR 3-8 OR 4-9

(#4) 89

1:3-8 OR 4-9 solve in 1 more

0:12-5 solve in 1 more

Sorry to waste your time, gang.

#2 12345

:1 really results in

0-5 OR 12-67 OR 34-89

[Guest]

Background:

We want to solve it in 5 more tests

(#2) 12345

results could be

2: 12-5, solve in 1 more

0: 0-67, solve in 1 more

1: 12-5 OR 34-89

A result of 1 on test #2 makes the 12-5 combination impossible.

EDIT: Looks like you beat me to it.

Edited May 27, 2009 by hookemhorns

[CaptainEd]

edit: wrong yet again

Edited May 27, 2009 by CaptainEd

[CaptainEd]

I plan to stop posting proposed answers until I've reviewed one several times!

However, here's a thought that might trigger a better thought: The number 17 is exactly the number you could cover if you made 4 tests with one-jar overlap. That is, if you tested

0-4, 4-8, 8-12, 12-16

This doesn't just jump up and tell me how to test them all in 8, nor does it point me in the direction of minimum-expectation test plan, but perhaps it will help someone.

[CaptainEd]

Please bear with me. I really think I've checked this...

* Name the objects 0123456789ABCDEFG

* Represent a hypothesis as {set 1} - {set 2}, example "0123-5678" means the set 0123 contains one object with attribute W, and 5678 contains the other.

* Represent the scope of a test by naming the entire set tested, example "01234" means that the test covers those 5 adjacent objects.

Tests #1-#4:

(#1) 01234

(#2) 45678

(#3) 89ABC

(#4) CDEFG

The largest count you could see would be

1,2,1,0 (if the answer is 4-8), or

0,1,2,1 (if 8-C).

1,1,1,1 (if 4-C)

In these, no more tests are needed.

Similarly, the result

2,1,0,0 implies 0123-4

and all other patterns with adjacent 2,1 have the same principle. For these, it takes 2 more tests to locate the 1 out of 4, so 8 tests max.

1,1,0,0 implies 0123-5678 (as the overlapping object would cause a 2 count in one side or the other). Once again, 2 tests to locate the one in 0123, 2 more to locate the one in 5678, 8 tests max.

So the only difficult ones to find are

1,0,1,0 and 1,0,0,1

In the first case, we know the overlap objects are definitely not W, so we are starting with

0123-9AB

It will take 2 tests for each group, 8 tests max

In the second case, we also know the overlap objects are not W, so we are still starting with

0123-DEFG

Once again, 2 tests twice, 8 tests max.

Clearly, if the early tests exhaust all possible W objects, we can ignore further tests. But first I'm just looking for minimizing the maximum.

Edited May 28, 2009 by CaptainEd

[Guest]

8 tests max.

Tests #1-#4:

(#1) 01234

(#2) 45678

(#3) 89ABC

(#4) CDEFG

Very good job!

I tried minimizing that, though not quite sure.

#1 01234

#2 23456

#3 45678

Leave the others yet.

Obviously the worst scenario will be not finding 2 or 0 results.

100-->0 or 1

010-->not possible

001-->7 or 8

110-->2 or 3

011-->5 or 6

111-->4

101-->0 or 1 and 7 or 8, no need to test others, so easy.

#4 test one of the relevant pairs above and get first W.

#5-6-7 Remaining 9ABCDEFG are total 8 objects. Each time dividing by 2 you can get W in 3 tests.

I couldn't see a flaw here, but sure it's possible.

More minimizing may be also possible???

[CaptainEd]

Very good job!

I tried minimizing that, though not quite sure.

#1 01234

#2 23456

#3 45678

Leave the others yet.

Obviously the worst scenario will be not finding 2 or 0 results.

100-->0 or 1

010-->not possible

001-->7 or 8

110-->2 or 3

011-->5 or 6

111-->4

101-->0 or 1 and 7 or 8, no need to test others, so easy.

#4 test one of the relevant pairs above and get first W.

#5-6-7 Remaining 9ABCDEFG are total 8 objects. Each time dividing by 2 you can get W in 3 tests.

I couldn't see a flaw here, but sure it's possible.

More minimizing may be also possible???

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.