Треугольники в кубе

Задача

Рис. 1.

Рис. 1.

Куб 4×4×4 разбит на единичные кубики, все вершины которых отмечены точками. Сколько существует равносторонних треугольников с вершинами в отмеченных точках? Например, на рис. 1 изображены три таких треугольника.


Подсказка

Какими числами могут выражаться длины сторон равносторонних треугольников? Здесь пригодится тот факт, что сторона такого треугольника — это диагональ некоего прямоугольного параллелепипеда.

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


Решение

Заметим, что сторонами равносторонних треугольников могут быть либо диагонали прямоугольных параллелепипедов, либо диагонали их граней. Набор параллелепипедов (напомню, что куб — это частный случай параллелепипеда) ограничен: от самого маленького 1×1×1 до самого большого 4×4×4. Используя формулу расстояния между двумя точками в трехмерном пространстве можно утверждать, что возможны длины сторон треугольников, которые можно представить в виде \(\sqrt{x^2+y^2+z^2}\) , где x, y и z целые числа из множества {0, 1, 2, 3, 4}. Небольшой перебор случаев показывает, что сторонами равносторонних треугольников могут быть только числа: \(\sqrt2\), \(\sqrt6\), \(\sqrt8\), \(\sqrt{14}\), \(\sqrt{18}\), \(\sqrt{24}\), \(\sqrt{26}\), \(\sqrt{32}\).

Посчитаем количество треугольников каждого размера \(a\) отдельно.

Рис. 2.

Рис. 2.

1) Если \(a=\sqrt2\), то сторонами равносторонних треугольников являются диагонали единичных кубов. В кубе с ребром 1 можно насчитать 8 равносторонних треугольников, плоскость каждого из них отсекает одну из восьми вершин куба (рис. 2).

Куб 4×4×4 состоит из 64 единичных кубов, поэтому все узлы кубической решетки 4×4×4 определяют 8·64 = 512 равносторонних треугольников со стороной \(\sqrt2\).

Рис. 3.

Рис. 3.

2) Если \(a=\sqrt6\), то сторонами таких равносторонних треугольников являются диагонали параллелепипедов 1×1×2. Такие треугольники легко обнаружить в кубе 2×2×2. На рисунке 3 изображено сечение этого куба, являющееся правильным шестиугольником со стороной \(\sqrt2\) (серый контур). Каждые три его вершины, взятые через одну, определяют два правильных треугольника (красный и синий) со стороной \(\sqrt6\). Каждая сторона этих треугольников — это диагональ одного из параллелепипедов 1×1×2 внутри куба 2×2×2. Таких треугольников в кубе 2×2×2 всего 8, потому что существует четыре сечения, являющиеся правильными шестиугольниками и в каждом — по два треугольника.

Вдоль каждого ребра куба 4×4×4 можно выделить три куба 2×2×2, поэтому в кубе 4×4×4 можно выделить \(3^3=27\) кубов 2×2×2. Так как в каждом из этих кубов есть 8 равносторонних треугольника, то всего в кубе 4×4×4 имеется 8·27 = 216 треугольников со стороной \(\sqrt6\).

Рис. 4.

Рис. 4.

3) Если \(a=\sqrt8\), то ситуация напоминает случай 1, только здесь размеры треугольника и куба в два раза больше. В кубе с ребром 2 по-прежнему можно насчитать 8 равносторонних треугольников, один из них изображен на рис. 4.

В куб 4×4×4 можно выделить 27 кубов 2×2×2, поэтому в этом случае все узлы кубической решетки 4×4×4 определяют 8·27 = 216 равносторонних треугольников со стороной \(\sqrt8\).

4) Если \(a=\sqrt{14}\), то сторонами таких равносторонних треугольников являются диагонали параллелепипедов 1×2×3. Отыскать их можно в двух параллельных сечениях куба 3×3×3, представляющих собой полуправильный шестиугольник (рис. 5). В каждый из этих двух шестиугольников можно двумя способами вписать правильный треугольник со стороной \(\sqrt{14}\), равной диагонали параллелепипеда 1×2×3. Эта пара параллельных сечений перпендикулярна одной из главных диагоналей куба. Учитывая, что у куба четыре таких диагонали, то можно построить четыре пары параллельных сечений, в связи с этим в кубе 3×3×3 можно найти всего 4·4 = 16 правильных треугольников со стороной \(\sqrt{14}\).

Рис. 5.

Рис. 5.

Очевидно, что в кубе 4×4×4 при каждой вершине можно выделить по одному кубу 3×3×3, то есть всего имеется 8 кубов 3×3×3, и в каждом из них по 16 правильных треугольников со стороной \(\sqrt{14}\). Значит, в кубе 4×4×4 имеется 16·8 = 128 правильных треугольников со стороной \(\sqrt{14}\).

5) Если \(a=\sqrt{18}\), то ситуация в этом случае значительно интереснее. Дело в том, что число 18 представляется в виде суммы трех квадратов двумя разными способами: \(18=3^2+3^2+0^2\) и \(18=4^2+1^2+1^2\). Это означает, что сторонами равносторонних треугольников в этом случае могут быть и диагонали граней куба 3×3×3, и диагонали прямоугольного параллелепипеда 4×1×1.

Рассмотрим два подслучая.

    5 а) Равносторонний треугольник составлен из трех диагоналей грани куба 3×3×3. В кубе 3×3×3 имеется 8 таких треугольников (рис. 6, слева). Но, как мы выясняли выше, в кубе 4×4×4 можно выделить 8 кубов 3×3×3, значит, всего треугольников этого типа 8·8 = 64.

Рис. 6.

Рис. 6.

    5 б) Равносторонний треугольник составлен из двух диагоналей прямоугольных параллелепипедов 4×1×1 и одной диагонали грани куба 3×3×3. Такой треугольник полностью расположен в прямоугольном параллелепипеде 4×4×1 (рис. 6, справа). Заметим, что в этом параллелепипеде такой треугольник можно расположить восемью разными способами (четыре поворота и каждый можно отразить симметрично относительно плоскости, проходящей через центр параллелепипеда параллельно квадратным граням 4×4). В кубе 4×4×4 можно выделить 12 параллелепипедов 4×4×1, поэтому треугольников такого типа имеется 8·12 = 96.

Суммарно получаем, что в кубе 4×4×4 всего 64 + 96 = 160 треугольников со стороной \(\sqrt{18}\).

6) Если \(a=\sqrt{24}\), то сторонами равносторонних треугольников являются диагонали параллелепипедов 4×2×2, которые в свою очередь являются диагоналями правильного шестиугольника, вершины которого — середины ребер куба 4×4×4 (рис. 7). В такой шестиугольник можно вписать два равносторонних треугольника, соединяя вершины шестиугольника через одну.

Рис. 7.

Рис. 7.

В кубе 4×4×4 можно расположить четыре «больших» правильных шестиугольника, значит, число равносторонних треугольников со стороной \(\sqrt{24}\), все вершины которых лежат в узлах кубической решетки 4×4×4, равно 2·4 = 8.

7) Если \(a=\sqrt{24}\), то сторонами равносторонних треугольников являются диагонали параллелепипедов 2×2×4. Найти такие треугольники можно в двух параллельных сечениях куба 3×3×3, представляющих собой полуправильный шестиугольник (рис. 8). В каждый из этих двух шестиугольников можно двумя способами вписать правильный треугольник со стороной \(\sqrt{26}\). Эта пара параллельных сечений перпендикулярна одной из диагоналей куба.

Рис. 8.

Рис. 8.

Учитывая, что у куба четыре диагонали, то можно построить четыре пары параллельных сечений, поэтому в кубе 4×4×4 можно указать всего 4·4 = 16 правильных треугольников со стороной \(\sqrt{26}\).

8) Если \(a=\sqrt{32}\), то очевидно, что равносторонний треугольник составлен их диагоналей граней куба 4×4×4. Таких треугольников — 8 штук, один из которых изображен на рис. 9.

Рис. 9.

Рис. 9.

Остается подвести итоги, подсчитав общее число равносторонних треугольников во всех восьми случаях вместе:
    со стороной \(\sqrt{2}\) имеется 512 треугольников;
    со стороной \(\sqrt{6}\) имеется 216 треугольников;
    со стороной \(\sqrt{8}\) имеется 216 треугольников;
    со стороной \(\sqrt{14}\) имеется 128 треугольников;
    со стороной \(\sqrt{18}\) имеется 160 треугольников;
    со стороной \(\sqrt{24}\) имеется 8 треугольников;
    со стороной \(\sqrt{26}\) имеется 16 треугольников;
    со стороной \(\sqrt{32}\) имеется 8 треугольников.

Итого: 1264 равносторонних треугольников, вершинами которых являются отмеченные точки.


Послесловие

 

3
Показать комментарии (3)
Свернуть комментарии (3)

  • vnesterovsky  | 19.05.2024 | 23:39 Ответить
    Ваша постановка задачи приглашает к решению грубой силой.
    И вправду, каких-то 5^9 вариантов!

    Я не выдержал, и сделал решение на C#:
    var results = ParallelEnumerable.Range(2, 15).
    Select(size =>
    (
    size,
    count: ParallelEnumerable.Range(0, size * size * size).
    SelectMany(i => Enumerable.Range(i + 1, size * size * size - i - 1).
    SelectMany(j => Enumerable.Range(j + 1, size * size * size - j - 1).
    Where(k =>
    (x: i % size, y: i / size % size, z: i / (size * size) % size) is var a &&
    (x: j % size, y: j / size % size, z: j / (size * size) % size) is var b &&
    (x: k % size, y: k / size % size, z: k / (size * size) % size) is var c &&
    (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z) is var ab &&
    (a.x - c.x) * (a.x - c.x) + (a.y - c.y) * (a.y - c.y) + (a.z - c.z) * (a.z - c.z) is var ac &&
    (b.x - c.x) * (b.x - c.x) + (b.y - c.y) * (b.y - c.y) + (b.z - c.z) * (b.z - c.z) is var bc &&
    ab == ac && ab == bc))).
    Count()
    ));

    Console.WriteLine($"Size\tCount");

    foreach(var (size, count) in results)
    {
    Console.WriteLine($"{size}\t{count}");
    }
    Я перебираю сетки с размерами от 2, и до 16. В каждой сетке перебираю тройки различных точек, и считаю те, что образуют правильные треугольники.

    Программа исполняется меньше минуты на моём лаптопе.

    Вот мои результаты:
    Size Count
    2 8
    3 80
    4 368
    5 1264
    6 3448
    7 7792
    8 16176
    9 30696
    10 54216
    11 90104
    12 143576
    13 220328
    14 326680
    15 471232
    16 664648
    Ответ Вашей задачи: 1264
    Ответить
    • vnesterovsky > vnesterovsky | 20.05.2024 | 23:08 Ответить
      Добавлю. Решение грубой силой сразу же намекает, что формула видимо является полиномом пятой степени.

      Простые рассуждения подтверждают это.
      Формула действительно выводится как сумма ряда четвёртых степеней.
      Ответить
      • Nik > vnesterovsky | 22.05.2024 | 22:12 Ответить
        Я перебираю сетки с размерами от 2, и до 16. В каждой сетке перебираю тройки различных точек, и считаю те, что образуют правильные треугольники.

        Программа исполняется меньше минуты на моём лаптопе.
        Спасибо за таблицу значений.
        Всё верно!
        Согласен, что для программиста это легкая задача!
        Ответить
Написать комментарий
Элементы

© 2005–2025 «Элементы»