在 Puzzle Toad 发现一些有趣的问题，基本上都很烧脑，记录一下。
有n个人，每个人不是经理就是工程师，每个人都知道其他人的职业。可以询问第i个人第j 个人是工程师还是经理。工程师总是说实话，但经理会说谎。问：
Part 1:
A correct, optimal, and elegant solution was submitted by Chris Peikert, Grant Wang, and Abhi Shelat of MIT. A number of others submitted partial solutions.
Here's an n-1 query solution to part 1. Maintain three sets of people: UNSEEN, STACK, and DISCARD. Initialize the process by picking one arbitrarily to be the STACK, everything else is UNSEEN. Repeat the following step until UNSEEN is empty:
Pick an UNSEEN element x, remove it from UNSEEN. Ask the top of the STACK y about x. If y says "manager" pop y off the stack and DISCARD both x and y. If it says "engineer" add x to the top of the STACK.
After all elements have been processed in this way (n-1 comparisons), the top of the stack must be an engineer.
Why does this work? First observe that whenever we discard a pair, at least one of them is a manager. So among the rest of them (STACK and UNSEEN) a majority must still be engineers. So at the end, when UNSEEN is empty, there must be an engineer in the stack, therefore the top of the stack must be an engineer.
This can be improved to n-2 simply by stopping one earlier. When there's one UNSEEN left, if the stack is empty, that UNSEEN one is an engineer. Otherwise, the top of the stack must be an engineer.
If is n is even and n>=4, as a first step we can just throw out one person, and appy this algorithm to the remaining n-1 obtaining n-3 comparisons. This gives the optimal algorithm.
This is optimal. The proof appears in the solution of homework assignment 7 of Steven Rudich's course 15-251 taught at CMU in the spring semester of 2002. See Solution 7.
Part 2:
If half or more of the people are managers, then the problem cannot be solved. The managers can ensure this simply by always lying. Now there's way to separate the two sets of people. Each one simply claims the others are Managers.
Part 3:
I don't know any better solution than to simply using the solution to Part 1 to identify everybody.
有n个人，每个人不是经理就是工程师，每个人都知道其他人的职业。可以询问第i个人第j 个人是工程师还是经理。工程师总是说实话，但经理会说谎。问：
- 如果有超过一半的人为工程师，有什么策略可以保证在询问次数最多n-1的情况下，找到 一个工程师？
- 如果经理占一半人数，是否可以找出一个工程师？如果能，怎么找？
- 如果发现一个工程师，则可以通过他识别其他人的职业。是否有一种方法识别出所有人 的职业，但只需更少的询问次数？
Part 1:
A correct, optimal, and elegant solution was submitted by Chris Peikert, Grant Wang, and Abhi Shelat of MIT. A number of others submitted partial solutions.
Here's an n-1 query solution to part 1. Maintain three sets of people: UNSEEN, STACK, and DISCARD. Initialize the process by picking one arbitrarily to be the STACK, everything else is UNSEEN. Repeat the following step until UNSEEN is empty:
Pick an UNSEEN element x, remove it from UNSEEN. Ask the top of the STACK y about x. If y says "manager" pop y off the stack and DISCARD both x and y. If it says "engineer" add x to the top of the STACK.
After all elements have been processed in this way (n-1 comparisons), the top of the stack must be an engineer.
Why does this work? First observe that whenever we discard a pair, at least one of them is a manager. So among the rest of them (STACK and UNSEEN) a majority must still be engineers. So at the end, when UNSEEN is empty, there must be an engineer in the stack, therefore the top of the stack must be an engineer.
This can be improved to n-2 simply by stopping one earlier. When there's one UNSEEN left, if the stack is empty, that UNSEEN one is an engineer. Otherwise, the top of the stack must be an engineer.
If is n is even and n>=4, as a first step we can just throw out one person, and appy this algorithm to the remaining n-1 obtaining n-3 comparisons. This gives the optimal algorithm.
This is optimal. The proof appears in the solution of homework assignment 7 of Steven Rudich's course 15-251 taught at CMU in the spring semester of 2002. See Solution 7.
Part 2:
If half or more of the people are managers, then the problem cannot be solved. The managers can ensure this simply by always lying. Now there's way to separate the two sets of people. Each one simply claims the others are Managers.
Part 3:
I don't know any better solution than to simply using the solution to Part 1 to identify everybody.
没有评论:
发表评论