12 шариков 1 как его найти

Для начала нужно пронумеровать шары 1,2,3,…,12

Делим все шары по 4 штуки в каждую группу (1 2 3 4) (5 6 7 8 ) (9 10 11 12)

Теперь взвешиваем первые две группы (1,2,3,4 и 5,6,7,8)

Если они равны, то нужный шар нужно искать в оставшейся группе.

Далее взвешиваем по два шара из третьей группы (9,10 и 11,12) — тут шар 11 не то, что нам нужен.

Если они равны, то нужный шар 12. Если нет, то запоминаем состояние весов (тяжелее/легче).

Взвешиваем шары (9,10). Если они равны, то нужный шар 11.

Если состояние весов не изменилось, то нужный шар 9. Если состояние весов изменилось, то нужный 10.

Время на прочтение
2 мин

Количество просмотров 27K

Совершенно случайно узнал об интересной задаче, которая очень даже может взбодрить.

Задача:

На столе лежат 12 совершенно одинаковых по виду шаров, но один из них — фальшивый. Он отличается от остальных шаров по весу (мы не знаем, легче он или тяжелее). В вашем распоряжении имеются чашечные весы без гирь. Нужно найти аномальный шар за минимальное количество взвешиваний (подсказка — решение можно найти за 3 взвешивания).

Перед тем, как решить задачу за 5 минут, внимательно прочтите условие.
У меня на всё ушло 6 часов (долго, не претендую на гениальность).

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   = 0123456789ABn");
            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;
    }
}

В нашем мире существует множество разных проблем и одна из таких проблем – это проблема тринадцати шаров.

Не про многие математические задачи, даже весьма знаменитые, сложные и важные, известно, как и когда они возникли. Так, никто не знает (и вряд ли когда-нибудь узнает), кто впервые задал вопрос о квадратуре круга или поинтересовался возможностью доказать пятый постулат Евклида. Даже в новейшие времена про важные задачи остаётся неизвестным, кто впервые их сформулировал. Тем удивительнее тот факт, что дата и даже обстоятельства возникновения задачи тринадцати шаров в пространстве, возникла в конце XVI в.

И в наше время эта проблема остаётся актуальной, так как при всей простоте и наглядности поставленного вопроса, он, как это часто бывает с просто формулируемыми математическими задачами, оказался очень трудным. Даже доказать, что четырнадцатый шар не может поместиться, — не простая задача, требующая хорошего знания геометрии.

Проблема: Сколько непересекающихся шаров одного и того же радиуса может касаться фиксированного шара того же радиуса?

Цель моей работы – рассмотрение вариантов расположения шаров в пространстве, так как я изучаю стереометрию.

Задачи: 1)изучить литературу по данному вопросу и выяснить, что по теме имеется в современной науке.

2)Провести опыты с помощью равных шаров

3)С использованием компьютерной программы провести опыты по определению контактного числа шара.

Работа состоит из введения, основной части и заключения, списка использованной литературы и приложений.

Основная часть

Задача. Дана окружность. Сколько непересекающихся окружностей такого же радиуса можно к ней «прислонить»? Иными словами, каково максимальное число непересекающихся окружностей фиксированного радиуса может касаться некоторой окружности того же радиуса.

Это очень простая задача. Может быть, мы не стали бы ее разбирать так подробно, если бы она не была одним из простейших примеров чрезвычайно интересного класса задач современной геометрии – задач, в которых требуется определить контактное число той или иной фигуры. Дадим теперь точное определение того, что называется контактным числом.

Определение: Контактным числом фигуры Ф (под фигурой мы понимаем произвольную замкнутую область на плоскости, в трёхмерном пространстве или даже в евклидовом пространстве произвольной размерности) называется максимальное натуральное число к(Ф) непересекающихся фигур, равных Ф, которые касаются Ф.

Обозначение к(Ф) происходит от английского названия чисел kissing numbers, то есть «числа поцелуев». Надо отдать должное поэтической натуре англичан.

Задачу нахождения контактных чисел можно различным образом видоизменять, усложнять или упрощать. Например, можно рассматривать не произвольные фигуры, равные данной, а только те, которые получаются из нее параллельным переносом на некоторый вектор. Или же можно рассматривать не только фигуры, касающиеся данной, но и фигуры, касающиеся тех, которые касаются данной и т. д. Некоторые из таких задач уже решены, про подавляющее большинство других ничего не известно. Например, можно показать, что любая фигура на плоскости может касаться не более чем с 8, но не менее чем с 6 (рис. 2) своими образами при параллельных переносах, причем восемь касаний возможны, если и только если данная фигура – параллелограмм. С другой стороны, мало что известно про контактное число произвольного треугольника. Ясно только, что оно должно зависеть от отношения его самой длинной и самой короткой сторон.

Одна из самых простых, но важных (в том числе и для приложений) задач такого рода – задача нахождения контактного числа n – мерного евклидова шара (или сферы). Напомним, что n – мерным шаром радиуса R центром в точке A(a1;. ; an) называется множество Bn(R;A), состоящее из всех последовательностей по n вещественных чисел (x1; x2;. ; xn), удовлетворяющих условию (x1 — a1)2 +. + (xn – an)2 ≤ R2. Два таких шара с центрами в A и B и радиусами R1 и R2 называются касающимися, если

— и пересекающимися, если

Тогда для каждого натурального числа n мы можем рассмотреть шар Bn = Bn(1;O), где O = = (0;. ; 0), и попытаться найти максимальное число касающихся этого шара непересекающихся шаров радиуса 1. Именно это число называется контактным числом и обозначается k(Bn). Обычно его сокращают до kn. Утверждение задачи 1 можно теперь сформулировать в виде формулы k2 = 6.

Данная статья посвящена задаче нахождения контактного числа трехмерного шара. Ответ на этот вопрос известен уже примерно 50 лет: k3 = 12.

Задачу о нахождении контактного числа трехмерного шара часто называют задачей «тринадцати шаров». Это связано с тем, что на самом деле не так уж и сложно найти конфигурацию, при которой данный шар касается двенадцати таких же.

История задачи

В конце XVI в. , когда знаменитый английский политик, военный, придворный и поэт сэр Уолтер Рэли задал своему помощнику чисто практический вопрос: «Как лучше хранить пушечные ядра?» Этим помощником был Томас Хариот.

Рэли попросил Хариота разобраться со складированием пушечных ядер. В рукописи, датированной воскресеньем 12 декабря 1591 г. , Хариот представил таблицу, позволяющую определить, сколько ядер помещается в пирамиде с заданным ребром основания и наоборот, сколько ядер надо положить в основание пирамиды, если надо наиболее экономным способом перевести заданное количество ядер (между прочим, эта таблица на 50 лет предвосхитила открытие треугольника Паскаля).

Однако Хариот не остановился на этом и стал исследовать вопрос о наиболее плотной упаковке ядер. Задача всплыла в его переписке с другим выдающимся ученым той эпохи – Иоганом Кеплером. Она сильно заинтересовала Кеплера. Для начала Кеплер попробовал определить, сколько шаров касается каждого шара в стандартной упаковке – когда каждый следующий слой шаров располагается в «прорехах» между шарами предыдущего слоя. Оказалось, что таких шаров 12. Очень быстро Кеплер придумал ещё один способ расположения шаров, при котором каждый шар касается 12 других. Я проверил и убедился практически с моделями пушечных ядер. Проще всего описать этот способ следующим образом: поместите один шар снизу от данного (он должен касаться данного в «южном полюсе»), затем поместите 5 шаров вокруг данного (снизу от экватора) так, чтобы они касались данного и предыдущего рассмотренного, а так же все касались друг друга. Пять таких шаров надо расположить в выемках между данным шаром и пятью только что рассмотренными. Наконец, сверху надо положить ещё один шар (рис. 4). Итого 1 + 5 + 5 + 1 = 12 шаров. Все эти шары касаются друг друга, и упаковка кажется весьма плотной и не похожей на упаковку ядер в пирамиде. Однако Кеплеру удалось показать, что эти две конфигурации ядер совпадают. Однако доказать свою гипотезу он не смог. Таким образом, уже в начале XVII в. было известно несколько способов расположить 12 шаров в пространстве вокруг данного центрального шара. Но прошло еще почти сто лет, прежде чем возник вопрос о возможности добавить к этой конфигурации тринадцатый шар.

Проблема тринадцати шаров появилась на свет 4 мая 1694г. В Тринити колледже в Кембридже в ходе спора между сэром Исааком Ньютоном и его современником, шотландским математиком Девидом Грегори.

Одной из обсуждаемых тем было распределение звезд на небосклоне. Звезды предполагались шарами определённой величины, и требовалось определить, сколько звёзд может быть расположено на том или ином удалении от Земли. От этой проблемы перешли к более простой задаче: сколько непересекающихся шаров одного и того же радиуса может касаться фиксированного шара того же радиуса?

Считается, что Ньютон полагал невозможным существование более 12 таких шаров, а Грегори оспаривал это мнение. Как бы то ни было, гипотеза о несуществовании тринадцатого шара получила название гипотезы Ньютона.

Одной из возможных причин скептицизма Грегори является тот факт, что 12 шаров, касающихся данного, расположены крайне неплотно. Конечно, все шары в конфигурации на рисунке 4 касаются друг друга (так же, как и ядра, окружающие любое из ядер в пирамиде на рисунке 3). Кажется, что ни один из них нельзя сдвинуть, не оторвав от поверхности центрального шара. Но ведь существуют и другие способы расположения шаров. Более того их бесконечно много!

Предположим, что все шары, касаются данного пронумерованы. Тогда существует способ поменять местами любые два из них, не изменив положения остальных, перекатывая все шары вдоль поверхности центрального шара.

Современное состояние проблемы

Гипотеза Ньютона очень долго оставалась недоказанной.

Первая работа, в которой была сделана попытка доказать гипотезу, появилась только в 1872г. Эта работа была написана немецким математиком Рудольфом Гоппе. Доказательство было длинное и трудное, в добавок к этому оно содержало ошибку.

Первое правильное доказательство было приведено в 1953г знаменитым голландским математиком Ван дер Варденом и известным немецким логиком К. Шютте.

За 50 лет, прошедших с момента появления на свет этого доказательства, теорема о тринадцати шарах была передоказана много раз самыми разными способами.

Я хочу изучить эту проблему, с помощью опытов выяснить: возможно, ли соприкосновение двенадцати шаров одного и того же радиуса с одним фиксированным шаром того же радиуса.

Изучая литературу, я провел опыты с теннисными шарами: 1) В этом опыте я брал шары и наклеивал их беспорядочно на один центральный шар. Таким образом, у меня получилось, что таких шаров всего 11, но конфигурация очень не плотная.

2) Проводя опыт пользуясь описанием его в исторической справке, я выяснил, что таких шаров 12. 3)Этот опыт очень похож на первый, но шары я наклеивал последовательно. Сначала я наклеил 6 шаров вокруг данного так, что все они касаются соседних им шаров. Далее, сверху и снизу я наклеил еще по три шара, они так же касаются центрального и других соседних им шаров. Итак, у меня получилась конфигурация из 12 шаров.

Таким образом, в каждом опыте мне удалось прислонить к центральному шару не более 13 шаров одного и того же радиуса.

В будущем я планирую провести некоторые опыты с помощью компьютерной программы AutoCAD R14 RU.

По завершению своей работы я пришел к следующему выводу – контактное число шара равно 12.

Таким образом, я убедился, почему задачу по нахождению контактного числа шара называется «проблема тринадцати шаров»

В дальнейшем я решил изучить некоторые факты сферической геометрии непосредственно касающихся «проблемы тринадцати шаров» и с помощью компьютерной программы провести подробное исследование «проблемы тринадцати шаров».

Привожу решения к интересной задаче, описанной в моём предыдущем посте:Имеется 12 шаров и рычажные весы. Известно, что один из шаров отличается по весу от остальных, при этом неизвестно тяжелее он или легче.
Каким образом, при помощи лишь трёх взвешиваний найти отличающийся шар?
_________________________________________________________________________________________

Задача достаточно сложна, хотя решить её в состоянии буквально каждый.
Правильный ответ дали kvicks и kolay, с чем я их и поздравляю!
P.S.: Если вы ещё не сдалишь, и, возможно, найдёте решение — поделитесь им в предыдущем посте.

Моё решение:
(для упрощения привожу самую сложную из возможных ситуаций, решения более лёгких ситуаций очевидны)
Делим 12 шаров на 3 группы по 4 шара в каждой.

(лллл) — (тттт)      // (0000) — отбрасываемые

(ллтт) — (лт00)      // (лт)

Если левая чаша окажется легче остаются (ллт) если же тяжелее то (ттл).
Допустим левая чаша оказалась легче. Отбрасываем один лёгкий и взвешиваем шарики следующим образом с добавлением нейтральных:
(лт) — (00)            // (л)

Если левая чаша оказалась легче, то искомый шар (л), если тяжелее то (т), если чашы равны — отброшенный.

Решение kvicks:
(лллл) — (тттт)      // (0000)
(лттт) — (т000)      // (ллл)
(т) — (т)                 // (т)

взвешиваем 4 и 4. если равновесие то шар в оставшихся четырёх, из них берём два и меняем на 2 на одной из чашек весов, если равновесие остаётся, из оставшихся двух берём один и меняем с шаром на весах.
если не равновесие то из однй чаши берём три шара и убираем, на их место перекладываем три шара из другой чаши, на место этих кладём 3 нормальных шара. Если неравновесие меняется, то отличающийся шар в трёх, что мы переложили. если вдруг равновесие — то он в трёх что мы убрали. Если неравновесие осталось то он в тех двух что мы не поменяли. Если он в двух — то мы просто менаяем один на нормальный.
Если он в трёх что мы убрали, то тут надо вспомнить из какой чаши весов мы их убрали — тяжёлой или лёгкой (например тяжёлой) — и тогда взвесить два из этих трёх друг против друга — либо равновесие (тогда оставшийся, либо тот, что на перевешивающей чаше). Если он в трёх, что мы переложили, то тогда один из этих трёх мы перекладываем обратно (тогда неравновесие опять меняется) , один меняем на нормальный (наступает равновесие если он) и один оставляем (чаша весов не меняется если он)

Решение kolay:
(лллл) — (тттт)       // (0000)
(тттлл) — (т0000)   // (лл)
(л) — (л)                  // (т)

— Первое взыешивание:
две кучки по 4 шара на весах и 4 шара на земле. (????/????)????

Этой задачей поделился со мной Влад. Он на фото.