Algorithm Debate CounterfeitBall

We present the problem first in English followed by a logical formulation.

Plain English

You are given n balls with the same appearance and weight except that one counterfeit ball has a slightly different weight. You are also given a scale which you use to find the counterfeit ball which is either heavier or lighter than the other balls. The scale allows for the following basic operation: you compare the weights of two sets of balls: the balls in the left bowl and the balls in the right bowl of the scale. The scale says which set is lighter or whether they have the same weight. How many basic operations do you need in the worst-case to find the counterfeit ball and also know if it is heavier or lighter than normal balls? You want to minimize the number of basic operations that are needed in the worst-case.

We are looking for a ternary decision tree (ternary because we have 3 cases: left side is heavier, both sides are equal, right side is heavier) that correctly identifies the counterfeit ball and correctly says whether it is heavier or lighter. We want the decision tree to have minimum depth over all possible decision trees. Each node in the decision tree represents a basic weighting operation.

Logical Formalism

We use data structures to formulate the claim. We need the structure of natural numbers which are predefined in our programming language, e.g., Integer in Java. We need a structure for ternary decision trees, e.g., defined by a Java class called TDT. TDT has several methods, including a method to compute the depth. 
// at most q basic weighting operations needed
Claim CounterfeitBall(n in Nat AND greater than 2, q in Nat)=
Exists a ternary decision tree T
  ForAll m in [1..n], 
    m is the index of a counterfeit ball such that
    T correctly finds m and tells that it is heavier or lighter
    with at most q basic operations

// q basic weighting operations needed and q is minimum
Claim MinCounterfeitBall(n in Nat AND greater than 2, q in Nat)=
CounterfeitBall(n,q) and 
(ForAll q'< q: !(CounterfeitBall(n,q')))

// produce general claim for the best solution.
// claim is trivially true.
Claim MinCounterfeitBall()=
ForAll n (n in Nat AND greater than 2)
  Exists q (q in Nat)
    MinCounterfeitBall(n,q)

Sample Debate

Karl and Zhengxing both make the claim MinCounterFeitBall() which claims that they can find a correct ternary decision tree of depth q when given any n balls. Because the claim is trivially true, both Karl and Zhengxing want to be verifiers. By a random flip, Zhengxing will be the forced Falsifier and challenge Karl.

Verifier: Karl
Falsifier: Zhengxing
Admin: Bingran

Move 1: Zhengxing provides a scenario when there are 4 balls (i.e., n=4) and asks Karl to give his answer.

Move 2: Karl, as the Verifier, provides 2 as his answer.

Move 3: Zhengxing, after evaluating Karl's claim, thinks it is false. Therefore he chooses to attack the left side of MinCounterfeitBall(n,k) which consists of a logical "and".

Move 4: Karl is required to deliver his ternary decision tree which will then be inspected by Zhengxing. Karl provides his weighting strategy (a JSON string of his ternary decision tree) to Zhengxing to be verified.

Move 5: Zhengxing can't find any flaw in Karl's decision tree so he admits that he loses. He chooses m=3 for which Karl's decision tree gives the correct answer. Karl has won as Verifier. Both Karl and Zhengxing keep their algorithm for constructing decision trees, secret.

THE ADMIN STEPS IN: Though Karl wins, his answer is wrong in fact. Bingran, as the admin, after the debate ends, points out an incorrectness in Karl's decision tree: the decision tree only has 7 leaves, which means it could only find the counterfeit ball in 7 possbile scenarios while there are 8 in total. (i.e., 1st ball is a lighter counterfeit, 1st ball is a heavier counterfeit, ..., 4th ball is a heavier counterfeit).

There are two duties of admin:
  • Point out any violation of debate rules during the debate. (e.g., Verifier makes a move first for a ForAll claim)
  • Point out any incorrectness of debators' solution after the debate. (e.g., one leaf is missing from a decision tree)

    • Decision Tree Representation

    There several ways to present your weighting solution for MinCounterfeitBall(n,q). We choose a JSON notation.

    JSON String. Make your ternary decision tree into an object and use JSON to encode it.

    Decision tree object has 5 attributes:

    Leaf object has 2 attributes: Here is the json string Karl gave Zhengxing in the above example: 
    {
  "left_balls": [
    1
  ],
  "right_balls": [
    2
  ],
  "heavier": {
    "left_balls": [
      1
    ],
    "right_balls": [
      3
    ],
    "heavier": {
      "counterfeit_ball": 1,
      "weight": "heavier"
    },
    "equal": {
      "counterfeit_ball": 2,
      "weight": "lighter"
    }
  },
  "lighter": {
    "left_balls": [
      1
    ],
    "right_balls": [
      3
    ],
    "lighter": {
      "counterfeit_ball": 1,
      "weight": "lighter"
    },
    "equal": {
      "counterfeit_ball": 2,
      "weight": "heavier"
    }
  },
  "equal": {
    "left_balls": [
      1
    ],
    "right_balls": [
      3
    ],
    "heavier": {
      "counterfeit_ball": 3,
      "weight": "lighter"
    },
    "lighter": {
      "counterfeit_ball": 3,
      "weight": "heavier"
    },
    "equal": {
      "counterfeit_ball": 4,
      "weight": "heavier"
    }
  }
}
    There are only 7 leaves in Karl's ternary decision tree which renders Karl's decision tree incorrect.

    The figure shows the structure of Karl's ternary decision tree.

    Ternary decision tree FYI, A good online JSON visualizer: http://www.jsoneditoronline.org. If you use Java, you could use Gson to convert your object into Json String .