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.

// 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)

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: KarlFalsifier: 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: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:

- left_balls: set of balls (given by indices) put on the left side of the scale
- right_balls: set of balls (given by indices) put on the right side of the scale
- heavier: decision tree or leaf if balls on the left are heavier than balls on the right side
- lighter: decision tree or leaf if balls on the left are lighter than balls on the right side
- equal: decision tree or leaf if balls are of the same weight on both sides

- counterfeit_ball: number of counterfeit_ball
- weight: "lighter" or "heavier", indicates weight of counterfeit ball compared to normal balls

{ "left_ball": [ 1 ], "right_ball": [ 2 ], "left_heavier": { "left_ball": [ 1 ], "right_ball": [ 3 ], "left_heavier": { "counterfeit_ball": 1, "weight": "heavier" }, "equal_heavy": { "counterfeit_ball": 2, "weight": "lighter" } }, "right_heavier": { "left_ball": [ 1 ], "right_ball": [ 3 ], "right_heavier": { "counterfeit_ball": 1, "weight": "lighter" }, "equal_heavy": { "counterfeit_ball": 2, "weight": "heavier" } }, "equal_heavy": { "left_ball": [ 1 ], "right_ball": [ 3 ], "left_heavier": { "counterfeit_ball": 3, "weight": "lighter" }, "right_heavier": { "counterfeit_ball": 3, "weight": "heavier" }, "equal_heavy": { "counterfeit_ball": 4, "weight": "heavier" } } }There are only 7 leaves in Karl's ternary decision tree which renders Karl's decision tree incorrect. 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 .