PrepBro
← Назад к вопросам

За какое минимальное количество взвешиваний из 9 монет можно найти фальшивую

2.3 Middle🔥 111 комментариев
#Основы Java

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

# Минимальное количество взвешиваний для поиска фальшивой монеты

Краткий ответ

Минимум 2 взвешивания достаточно, чтобы найти фальшивую монету из 9, если известно, что она легче или тяжелее оригинальной.

Теоретический анализ

Информационная теория (информационная энтропия)

Каждое взвешивание может дать 3 результата:

  • Левая сторона тяжелее
  • Правая сторона тяжелее
  • Обе стороны равны

С N взвешиваниями можно различить максимум 3^N случаев:

  • 3^1 = 3 случая
  • 3^2 = 9 случаев
  • 3^3 = 27 случаев

У нас 9 монет, значит 9 возможных вариантов (какая из 9 фальшивая).

3^2 = 9, поэтому теоретически возможно за 2 взвешивания.

Алгоритм за 2 взвешивания

Предусловие

Знаем, что фальшивая монета либо легче, либо тяжелее (не знаем какая).

Первое взвешивание

Разделяем 9 монет на 3 группы по 3 монеты каждая:

  • Группа A: монеты 1, 2, 3
  • Группа B: монеты 4, 5, 6
  • Группа C: монеты 7, 8, 9

Взвешиваем: Группа A против Группы B

Возможные результаты:

Вариант 1: A = B (Равны)

Значит фальшивая в группе C (монеты 7, 8, 9)

Второе взвешивание: Монета 7 против Монеты 8

  • Если 7 > 8: монета 8 фальшивая (легче)
  • Если 7 < 8: монета 7 фальшивая (тяжелее)
  • Если 7 = 8: монета 9 фальшивая

Вариант 2: A > B (A тяжелее)

Фальшивая либо в A (тяжелая), либо в B (лёгкая)

Означает: либо одна из {1,2,3} тяжелая, либо одна из {4,5,6} лёгкая

Второе взвешивание: Монета 1 против Монеты 2

  • Если 1 > 2: либо 1 тяжелая (если фальшивая в A), либо 6 лёгкая (если в B)
  • Если 1 < 2: либо 2 тяжелая (если в A), либо 5 лёгкая (если в B)
  • Если 1 = 2: монета 3 тяжелая (если в A) или 4 лёгкая (если в B)

Третье взвешивание потребуется — значит 2 недостаточно в этом случае!

Правильный алгоритм для всех случаев

Разберёмся по-другому. Если неизвестно, тяжелее или легче фальшивая, то нужно минимум 3 взвешивания.

Но часто в задаче уточняют: известно, что одна из 9 монет легче всех остальных (не тяжелее, а именно легче).

Случай 1: Знаем, что фальшивая ЛЕГЧЕ

Это даёт нам дополнительную информацию!

Первое взвешивание: Группа A (1,2,3) против Группы B (4,5,6)

  • A = B: Фальшивая в C (7,8,9), и она легче

    • Второе взвешивание: Монета 7 против Монеты 8
    • Если 7 < 8: монета 7 фальшивая
    • Если 7 > 8: монета 8 фальшивая
    • Если 7 = 8: монета 9 фальшивая
    • Ответ за 2 взвешивания

  • A > B: Фальшивая в B (более лёгкая), поскольку она легче

    • Второе взвешивание: Монета 4 против Монеты 5
    • Если 4 < 5: монета 4 фальшивая
    • Если 4 > 5: монета 5 фальшивая
    • Если 4 = 5: монета 6 фальшивая
    • Ответ за 2 взвешивания

  • A < B: Фальшивая в A (более лёгкая)

    • Второе взвешивание: Монета 1 против Монеты 2
    • Если 1 < 2: монета 1 фальшивая
    • Если 1 > 2: монета 2 фальшивая
    • Если 1 = 2: монета 3 фальшивая
    • Ответ за 2 взвешивания

Заключение

  • Если известно, тяжелее или легче фальшивая: 2 взвешивания достаточно
  • Если неизвестно, тяжелее или легче: нужно 3 взвешивания (информационно-теоретический минимум: 3^3 = 27 >= 9*2 случаев)
  • Сложность алгоритма: O(log₃ n) взвешиваний для n монет

Реализация на Java

Вот функция, которая демонстрирует алгоритм:

public class CoinProblem {
    enum Result { LEFT_HEAVIER, RIGHT_HEAVIER, EQUAL }
    
    // Имитируем взвешивание
    private int fakeCoinIndex;  // 0-8 (индекс фальшивой монеты)
    private int weighingCount = 0;
    
    // Взвешиваем две группы монет
    public Result weigh(int[] leftCoins, int[] rightCoins) {
        weighingCount++;
        
        int leftWeight = 0, rightWeight = 0;
        for (int idx : leftCoins) {
            leftWeight += (idx == fakeCoinIndex) ? 1 : 2;  // фальшивая = 1, реальная = 2
        }
        for (int idx : rightCoins) {
            rightWeight += (idx == fakeCoinIndex) ? 1 : 2;
        }
        
        if (leftWeight > rightWeight) return Result.LEFT_HEAVIER;
        if (leftWeight < rightWeight) return Result.RIGHT_HEAVIER;
        return Result.EQUAL;
    }
    
    public int findFakeCoin(boolean isFakeLighter) {
        // Первое взвешивание: A (0,1,2) vs B (3,4,5), C (6,7,8)
        Result result1 = weigh(new int[]{0, 1, 2}, new int[]{3, 4, 5});
        
        int[] candidates = new int[3];
        
        if (isFakeLighter) {
            if (result1 == Result.EQUAL) {
                candidates = new int[]{6, 7, 8};
            } else if (result1 == Result.LEFT_HEAVIER) {
                candidates = new int[]{3, 4, 5};
            } else {
                candidates = new int[]{0, 1, 2};
            }
        }
        
        // Второе взвешивание для определения из 3 монет
        Result result2 = weigh(new int[]{candidates[0]}, new int[]{candidates[1]});
        
        if (isFakeLighter) {
            if (result2 == Result.LEFT_HEAVIER) return candidates[1];
            if (result2 == Result.RIGHT_HEAVIER) return candidates[0];
            return candidates[2];
        }
        
        return -1;  // Не найдена
    }
    
    public static void main(String[] args) {
        CoinProblem problem = new CoinProblem();
        problem.fakeCoinIndex = 4;  // Фальшивая монета номер 4
        
        int fake = problem.findFakeCoin(true);  // Знаем, что легче
        System.out.println("Найдена фальшивая монета: " + fake);
        System.out.println("Количество взвешиваний: " + problem.weighingCount);
    }
}

Общий случай: n монет

Для поиска одной фальшивой из n монет (если известна лёгкость/тяжесть):

  • Минимум взвешиваний: ⌈log₃(n)⌉
  • Для 9 монет: ⌈log₃(9)⌉ = ⌈2⌉ = 2
  • Для 27 монет: ⌈log₃(27)⌉ = ⌈3⌉ = 3
  • Для 81 монет: ⌈log₃(81)⌉ = ⌈4⌉ = 4

Практическое значение

Эта задача иллюстрирует:

  • Divide and Conquer (разделяй и властвуй)
  • Информационный подход к сложности
  • Оптимальные алгоритмы поиска