↓Skip to main content
  1. Posts/

Puzzle Toad-1 Managers and Engineers

·1 min·
Table of Contents

Puzzle Toad-1 Managers and Engineers #

题目翻译 #

FBI 已经包围了 Norne 公司的总部. 公司大楼里有 $n$ 个人, 这些人要么是工程师, 要么是经理. 所有的电脑文件文件都被删除了, 并且所有的文档都被经理们撕碎了. FBI 的审问小组面临的问题是: 如何把大楼里的工程师和经理区分开, 以便关押所有的经理, 并且释放所有的工程师. 大楼里的 $n$ 个人中每个人都知道其它人的身份. 审问的方式是询问 $i$ 号人物: $j$ 号人物1的真实身份是经理还是工程师? 工程师总是讲真话, 但困难点在于, 经理不一定讲真话. 事实上, 这些经理都是邪恶的天才, 他们会想方设法地迷惑审问者.

  1. 假设一半以上的人都是工程师, 能否找到一个策略, 使得最多使用 $n - 1$ 个问题就能找到一个工程师?
  2. 假设一半的人是经理, 能否通过一定数量的询问找出一个工程师?
  3. 找出一个工程师之后, 自然可以得到所有人的身份. 有没有办法能够用更少的问题确定某个人的身份?

解答 #

  1. 设置一个栈 $st$ 存储待处理的人. 在最开始, 随便选一个人放到 $st$ 里. 接下来 $n - 1$ 次操作中, 我们每次从剩下的没有参与询问的人中选一个, 记为 $x$ , 同时询问当前栈顶 $y$ : $x$ 是工程师还是经理? 如果答案是工程师, 就把 $x$ 放到栈顶, 否则把 $y$ 弹出栈顶. 经过 $n - 1$ 轮询问之后, 栈顶一定是一个工程师. 这种询问模式的核心在于, 如果答案是经理, 则至少去掉了一个经理. 由于工程师人数比经理人数多, 最后留在栈顶的一定是工程师.

  2. 否. 经理永远说谎即可, 最终只能划分成两个大小相等的集合, 而不能具体区分其身份.

  3. 如果 $n$ 为偶数, 可以去掉一个人, 转化为 $n - 1$ 规模的问题, 可以少问一次; 如果栈空而只剩下一个人未询问, 这个人也必定是工程师, 可以少问一次.