I found this problem to be both interesting and sort of cute. So, I'm sharing here. There are at least two solutions that I know of (ignoring isomorphisms). I didn't find it too difficult, but who knows what everyone else thinks of it.
You have 10 visually indistinguishable balls lined up in front of you. Let's mark then ball #1 through #10. Two adjacent balls have been deemed special. Your job is to determine which balls are the special ones.
You are given a single consultation with an oracle to help you out. The oracle accepts a specific type of query, which is of the form: How many of the balls in this list { ... } are special? You are allowed to submit two questions at once, and you will receive two answers at once.
For example, if the special balls are #1 and #2, a valid consultation with the oracle would be:
1) How many of the balls in {#1, #2, #3, #9} are special?
2) How many of the balls in {#1, #5, #6} are special?
The oracle's response in this case will be Question #1 = 2, Question #2 = 1.
Notice that you are not allowed to formulate Question #2 based on the response of Question #1. Both questions must be submitted simultaneously.
Enjoy!
No comments:
Post a Comment