1. Найти количество способов расставить два крестика в квадрате 3×3 так, что две расстановки считаются одинаковыми если одна из другой получается в результате некоторого поворота. 2.У дерева п вершин, а диаметр равен три. Сколько висячих вершин у этого дерева? (вершин со степенью 1)

1. Чтобы рассчитать количество способов расставить два крестика в квадрате 3×3 с учетом вращений, можно использовать метод, называемый методом группировки или методомBurnside. В квадрате 3×3 9 клеток. Мы будем расставлять два крестика, выбирая 2 из 9. Это можно сделать \( \binom{9}{2} = 36 \) способов без учета симметрий. Теперь учтем симметрии квадрата: у квадратов 3×3 есть 4 поворота (0°, 90°, 180°, 270°) и 4 отражения, что дает 8 симметрий (группа вращений и отражений). 1. **Поворот на 0°**: все 36 размещений остаются неизменными. 2. **Поворот на 90°**: нет ни одного варианта, где бы два крестика не меняли свои положения (так как они будут занимать разные места в результате поворота). 3. **Поворот на 180°**: два крестика должны находиться в противоположных местах. Такие пары: (1, 9), (2, 8), (3, 7), (4, 6). Всего 4 фиксированных размещения. 4. **Поворот на 270°**: аналогично повороту на 90°, фиксированных размещений нет. 5. **Отражения**: если отразить относительно горизонтали, вертикали и диагоналям, то фиксированные размещения вновь отсутствуют кроме случаев, когда крестики стоят в определенных симметричных местах. Всего будет 8 фиксированных размещений для отражений. Суммируя, фиксированные размещения по всем симметриям: - 0°: 36 - 90°: 0 - 180°: 4 - 270°: 0 - 4 отражения: 8 Теперь можем посчитать: \[ \frac{36 + 0 + 4 + 0 + 8}{8} = \frac{48}{8} = 6 \] Следовательно, количество способов расставить два крестика в квадрате 3×3 с учетом поворотов равно 6. 2. У дерева с \( n \) вершинами и диаметром 3, обозначим количество висячих вершин (вершин со степенью 1) как \( k \). В дереве с диаметром 3 максимальное расстояние между двумя вершинами составляет 3, что означает, что между ними может быть не более 2 промежуточных вершин. Рассмотрим структуру дерева: - Концы диаметра — это 2 вершины диаметра. - Чтобы получить максимальную длину и обеспечить наличие висячих вершин, каждая из этих двух вершин (концы диаметра) может быть соединена с одной или более висячими вершинами. Тем не менее, каждая дополнительная висячая вершина будет добавлять к количеству вершин дерева, не увеличивая его диаметр. Поэтому для достижения условия, что диаметр равен 3, необходимо сосредоточить висячие вершины вокруг концов этих двух максимумов. Таким образом, максимальное количество висячих вершин \( k \) в таком дереве может быть приведено к следующему: - Если дохождение от одной верхней (конечной) вершины до другой (конечной) вершины происходит через 3 промежуточные или более сложные связи, существовать должны по меньшей мере 2 висячих. Формула: - Для минимума связи: \( k = 2 \) (при внедрении только двух вершин). Таким образом, общее количество висячих вершин может варьироваться в зависимости от конкретного расположения, учитывая минимумы, максимумы и ограничения связей. Следовательно, можно утверждать, что в таком дереве с диаметром равным три как минимум будет 2 висячие вершины, однако максимальное число не ограничено конкретными циклами или схемами.