毒酒问题 Poison Wine

毒酒问题---1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。问最少需要多少只老鼠可在一周内找出毒酒
如对1000桶按1~1000编码，需要10位二进制数。

因此只需要取10只老鼠，每只老鼠只喝其对应位数为1的编号的酒。
即10只老鼠按以下编码：

第一只 00000 00001
第二只 00000 00010
第三只 00000 00100
第四只 00000 01000
...
第十只 10000 00000

每只老鼠只喝其编码与酒编码做位与运算非0的酒。如果毒酒的编码在某一位为1，则监控该位的老鼠必喝，结果为1.

即把10只老鼠的结果，按位填入一个10位二进制数中，其结果即为毒酒编号。

例如：编号为10001 00011的酒是毒酒。则对应的只有第一只，第二只，第六只，第十只死亡。其对应位数置1，即为10001 00011
http://www.matrix67.com/blog/archives/4361

这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒药瓶子的二进制编号中，右起第二位是 0 ⋯⋯每只老鼠的死活都能确定出 10 位二进制数的其中一位，由此便可知道毒药瓶子的编号了。

    现在，有意思的问题来了：如果你有两个星期的时间（换句话说你可以做两轮实验），为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二次实验了。

    答案：7 只老鼠就足够了。事实上，7 只老鼠足以从 3⁷ = 2187 个瓶子中找出毒药来。首先，把所有瓶子从 0 到 2186 编号，然后全部转换为 7 位三进制数。现在，让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子，让第二只老鼠喝掉所有三进制数右起第二位是 2 的瓶子，等等。一星期之后，如果第一只老鼠死了，就知道毒药瓶子的三进制编号中，右起第一位是 2 ；如果第二只老鼠没死，就知道毒药瓶子的三进制编号中，右起第二位不是 2，只可能是 0 或者 1 ⋯⋯也就是说，每只死掉的老鼠都用自己的生命确定出了，三进制编号中自己负责的那一位是 2 ；但每只活着的老鼠都只能确定，它所负责的那一位不是 2 。于是，问题就归约到了只剩一个星期时的情况。在第二轮实验里，让每只活着的老鼠继续自己未完成的任务，喝掉它负责的那一位是 1 的所有瓶子。再过一星期，毒药瓶子的三进制编号便能全部揭晓了。

    类似地，我们可以证明， n 只小白鼠 t 周的时间可以从 (t+1)ⁿ 个瓶子中检验出毒药来。

http://bbs.emath.ac.cn/thread-1511-1-1.html
国王为10天后的生日宴会准备了1000桶酒，不幸的是，其中两桶被下了毒。为了确定两桶毒酒，有人提议用死刑犯试毒。毒的潜伏期为10天。
问:至少需要多少个死刑犯才能确保找出毒酒？方案如何实行？
http://www.zhihu.com/question/19731686
http://www.cnblogs.com/graphics/archive/2010/03/28/1699048.html

1、现有1000个苹果，10个盒子，现在要你将1000个苹果装入10个盒子中，使得用户无论购买多少个苹果（1-1000），都能由若干个盒子拼装而成（卖的时候是整个盒子卖，不能拆盒子的包装）

解法：考虑1， 2， 4， 8这四个数，由这四个数可以组成1-15之间任意一个数，也即1，2， 4 ... 2n 可以组成1-2⁽ⁿ⁺¹⁾-1之间所有的数。所以这十个盒子分别放入

1， 2， 4， 8， 16， 32， 64， 128， 256， 489个苹果，即可组成1-1000内所有的数。

Probability Puzzles

http://geeksquiz.com/puzzle-21-3-ants-and-triangle/
Puzzle 21 | (3 Ants and Triangle)
There are 3 ants sitting on three corners of a triangle. All ants randomly pick a direction and start moving along edge of the triangle. What is the probability that any two ants collide?

Hint: Every ant has two choices (pick either of two edges going through the corner on which ant is initially sitting).
Answer:
Collision doesn’t happen only in following two cases
1) All ants move in counterclockwise direction.

2) All ants move in clockwise direction.

Since every ant has two choices (pick either of two edges going through the corner on which ant is initially sitting), there are total 23 possibilities.

Out of 23 possibilities, only 2 don’t cause collision. So the probability of collision is 6/8

Wolf, sheep, cabbage - Algoritmy.net

Wolf, sheep, cabbage - Algoritmy.net
Wolf, sheep, cabbage is a logic puzzle, in which the player (boatman) has to transport a wolf, a sheep and a cabbage from one river bank to the other. In the game the player must obey these rules:

• The player can use a boat to transport the objects, but he may take at maximum one thing with him every time.
• If the sheep remains unguarded on the same bank as the cabbage, than the sheep will eat the cabbage.
• If the wolf remains unguarded on the same bank as the sheep, than the wolf will eat the sheep.

From the algorithmic point of view the puzzle can be easily solved by a backtracking algorithm. The backtracking algorithm in every step tries to transport one thing to the other bank and then it checks the consistency of the partial solution. If the solution is consistent, than it repeats the step (transports another thing). If not, than the backtracking algorithm returns to the preceding decision and changes it (transports something else, or returns to the previous decision, if all possible objects were already tried out). Using this technique of organized trials and failures the algorithm finds the solution.

public static void solveSheepCabbageWolf(){

05.sheepCabbageWolf(false, false, false, false, new LinkedList<String>());

06.}

07./**

08.* Solves the sheep-cabbage-wolf riddle and prints out its solution (the actual worker method)

09.* @param sheep true if the sheep is on the right bank, false otherwise

10.* @param cabbage true if the cabbage is on the right bank, false otherwise

11.* @param wolf true if the wolf is on the right bank, false otherwise

12.* @param farmer true if the farmer (boat) is on the right bank, false otherwise

13.* @param solution partial solution

14.* @return false if the partial solution is invalid

15.*/

16.private static boolean sheepCabbageWolf(boolean sheep, boolean cabbage, boolean wolf, boolean farmer, Deque<String> solution) {

17.if (sheep && cabbage && wolf && farmer) {

18.printSolution(solution);

19.return true;

20.}

21.if (!checkConsistency(sheep, cabbage, wolf, farmer)) {

22.return false;

23.}

24.if (solution.isEmpty() || !solution.peek().equals("boatman")) {

25.solution.addFirst("boatman");

26.if (sheepCabbageWolf(sheep, cabbage, wolf, !farmer, solution)) {

27.return true;

28.}

29.solution.pop(); //backtrack

30.}          

31.if (sheep == farmer && (solution.isEmpty() || !solution.peek().equals("sheep"))) {

32.solution.addFirst("sheep");

33.if (sheepCabbageWolf(!sheep, cabbage, wolf, !farmer, solution)) {

34.return true;

35.}

36.solution.pop(); //backtrack

37.}

38.if (cabbage == farmer && (solution.isEmpty() || !solution.peek().equals("cabbage"))) {

39.solution.addFirst("cabbage");

40.if (sheepCabbageWolf(sheep, !cabbage, wolf, !farmer, solution)) {

41.return true;

42.}

43.solution.pop(); //backtrack

44.}

45.if (wolf == farmer && (solution.isEmpty() || !solution.peek().equals("wolf"))) {

46.solution.addFirst("wolf");

47.if (sheepCabbageWolf(sheep, cabbage, !wolf, !farmer, solution)) {

48.return true;

49.}

50.solution.pop(); //backtrack

51.}    

52.return false;

53.}

63.private static boolean checkConsistency(boolean sheep, boolean cabbage, boolean wolf, boolean farmer) {

64.if (sheep == cabbage && sheep != farmer) {

65.return false;

66.} else if (sheep == wolf && sheep != farmer) {

67.return false;

68.}

69.return true;

70.}

http://yongouyang.blogspot.com/2013/04/solving-farmer-wolf-goat-cabbage-riddle.html
It is a task that given an initial state, a final state, and a set of rules, one will start from the initial state and try to reach to the final state by passing through some intermediate states. Each move will transform from one state to the other, and there might be multiple valid moves from a given state. Such a collection of interconnected states can be represented by State Space Graph. 
Let's use 'f', 'c', 'g', 'w' to denote the farmer, the cabbage, the goat, and the wolf, and use '|' to separate the river where left of the '|' denotes west bank and right of the '|' denotes east bank. Initially, they are all at the west bank of the river, which is represented as 'fcgw |' as shown below. We can solve the riddle by figuring out what the possible and valid moves are, using either Breadth-First Search or Depth-First Search, on a state space graph shown below 

 

Depth First Search

I use DFS to find the first possible solution to the riddle, where it looks like this

or with a possibility of backtracking like this

Breadth First Search

I can build a complete state space graph using BFS, excluding the red states as shown below

http://www.eprisner.de/WZK/WZK4.html

http://connor-johnson.com/2014/05/29/puzzle-the-wolf-the-goat-and-the-cabbage/

http://www.geeksforgeeks.org/missionaries-and-cannibals/

Question: In this problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, that the missionaries present on the bank cannot be outnumbered by cannibals. The boat cannot cross the river by itself with no people on board.

Read full article from Wolf, sheep, cabbage - Algoritmy.net