📜 ⬆️ ⬇️

12 balls

Quite by chance I found out about an interesting task that can even cheer up.

Task:
On the table are 12 absolutely identical in appearance balls, but one of them is fake. It differs from other balls in weight (we do not know if it is lighter or heavier). At your disposal there are cup scales without weights. It is necessary to find an anomalous ball for the minimum number of weighings (hint - the solution can be found in 3 weighings).
Before you solve the problem in 5 minutes, carefully read the condition.
It took me 6 hours (long, I do not pretend to be a genius).
Mathematical justification of the solution and a brief history of the problem

My java solution with tests
LINK - for checking online
public class Balls { private static final int A = 10; private static final int B = 11; private static final int LEFT_BIGGER = 1; private static final int RIGHT_BIGGER = 2; private static final int SAME = 4; public static void printTest() { System.out.println(Balls.test(true)); System.out.println(Balls.test(false)); } public static String test(boolean weight) { int[] array = new int[12]; StringBuilder builder = new StringBuilder(); for (int i = 0; i < array.length; ++i) { for (int w = 0; w < array.length; ++w) { array[w] = 5; } array[i] += weight ? 2 : -2; Balls balls = new Balls(array); builder.append("pos = 0123456789AB\n"); builder.append("array = "); for (int w : array) { builder.append(w); } builder.append('\n'); builder.append("res = "); balls.calculateNumber(); int number = balls.getResultPosition(); for (int w = 0; w < array.length; ++w) { builder.append(w == number ? '*' : ' '); } builder.append(" // number = "); builder.append(number); builder.append("; steps = "); builder.append(balls.getStepsCount()); builder.append('\n'); } return builder.toString(); } private int[] in; private int steps; private int number = -1; public Balls(int[] in) { this.in = in; } public void calculateNumber() { this.steps = 0; int step1 = compare(sum(0, 1, 2, 3), sum(4, 5, 6, 7)); switch (step1) { case SAME: { int step2 = compare(sum(0, 1), sum(8, 9)); switch (step2) { case SAME: { number = compare(in[0], in[B]) == SAME ? A : B; break; } default: { number = compare(in[0], in[9]) == SAME ? 8 : 9; break; } } break; } case LEFT_BIGGER: { int step2 = compare(sum(0, 1, 4), sum(2, 3, 5)); switch (step2) { case LEFT_BIGGER: { int tempState = compare(in[0], in[1]); number = tempState == SAME ? 5 : tempState == LEFT_BIGGER ? 0 : 1; break; } case RIGHT_BIGGER: { int tempState = compare(in[2], in[3]); number = tempState == SAME ? 4 : tempState == LEFT_BIGGER ? 2 : 3; break; } case SAME: { number = compare(in[6], in[7]) == LEFT_BIGGER ? 7 : 6; break; } } break; } case RIGHT_BIGGER: { int step2 = compare(sum(0, 1, 4), sum(2, 3, 5)); switch (step2) { case LEFT_BIGGER: { int newState = compare(in[2], in[3]); number = newState == SAME ? 4 : newState == LEFT_BIGGER ? 3 : 2; break; } case RIGHT_BIGGER: { int tempState = compare(in[0], in[1]); number = tempState == SAME ? 5 : tempState == LEFT_BIGGER ? 1 : 0; break; } case SAME: { number = compare(in[6], in[7]) == LEFT_BIGGER ? 6 : 7; break; } } break; } } } public int getResultPosition() { return number; } public int getStepsCount() { return steps; } private int compare(int l, int r) { ++steps; return l > r ? LEFT_BIGGER : l < r ? RIGHT_BIGGER : SAME; } private int sum(int... array) { int result = 0; for (int i : array) { result += in[i]; } return result; } } 


')

Source: https://habr.com/ru/post/255155/


All Articles