Поступить в 8й класс...

Ian · Сообщение **Ian** » 01 июн 2020, 10:47

...одной из московских школ, не решив этих задач, нельзя

: 0ur8jQvtsHc.jpg (138.69 KiB) 26146 просмотра

Причем как решить 4-ю -мы все без понятия. А в задаче 1 нашли 32 способа и вроде это максимум.

zykov · Сообщение **zykov** » 01 июн 2020, 18:52

Для номер 3 вышло (перебором) 9 вертикальных и 6 горизонтальных.

zykov · Сообщение **zykov** » 01 июн 2020, 18:59

Ian писал(а):Source of the post одной из московских школ, не решив этих задач, нельзя

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

zykov · Сообщение **zykov** » 01 июн 2020, 19:53

Ian писал(а):Source of the post как решить 4-ю -мы все без понятия

Видимо имеется ввиду, что четыре фишки на одной прямой не обязаны идти подряд.
По логике выходит, что каждая фишка должна входить ровно в две прямых (вообще в среднем, но проще если ровно): (4*5)/2=10.
Это значит, что не может быть две параллельных прямых (например две разных вертикальных), т.к. они не имеют общих точек.
Значит кроме 4 направлений - вертикаль, горизонталь, две диагонали по 45 градусов - должно быть ещё 1 направление под углом.
Например можно сделать так (из "." перенесли в "x"):

Код: Выбрать все

0 0 0 0 0 0 x
0 0 0 0 0 x 0
0 0 0 0 0 x 0
0 0 0 1 0 0 0
0 0 . 0 1 0 0
0 . 0 0 0 1 0
1 . 0 1 0 1 1

Будет две главных диагонали, нижняя горизонталь, вторая справа вертикаль и наклонная от верхнего правого угла в центр низа.

zykov · Сообщение **zykov** » 01 июн 2020, 20:38

zykov писал(а):Source of the post Для номер 3 вышло (перебором) 9 вертикальных и 6 горизонтальных.

Пусть у нас $n$

вертикальных и $n-a$

горизонтальных линий (соседние имеют фиксированную дистанцию). При этом $0 \leq a \leq n-2$ .
Если горизонтальных больше, то просто повернем картинку набок.
Количество квадартов размера 1 будет $(n-1)(n-1-a)$

.
Количество квадартов размера 2 будет $(n-2)(n-2-a)$

.
И так далее до квадратов размера $n-a-1$

Т.е. всего квадратов $s(n,a) = \sum_{k=a+1}^{n-1} k(k-a) = (\sum_{k=a+1}^{n-1} k^2) - a (\sum_{k=a+1}^{n-1} k) = \frac{( n-a-1) ( n-a) ( 2 n+a-1)}{6}$ .

$s(7,0) = 91$

,

Ian · Сообщение **Ian** » 01 июн 2020, 21:48

Про номер 3 точно так. А 4 это вообще феноменально

zykov · Сообщение **zykov** » 01 июн 2020, 22:21

Ian писал(а):Source of the post А 4 это вообще феноменально

Могу пояснить логику построения.
Т.к. нам разрешено переносить малое количество фишек, то без надобности их не будем трогать.
Так, те фишки что уже стоят на двух прямых, будут зафиксированны (обозначим "x").
В качестве прямых выберем те прямые, где уже много фишек - две главные диагонали и нижнюю горизонталь.
Это фиксирует три фишки - центр и два нижних угла.
Ещё выберем вертикаль. У нас по 2 фишки во 2ой, 4ой и 6ой.
Если пробовать 4ую, то проблемы. Так что выберем 6ую вертикаль (или можно было бы равнозначно 2ую).
Это фиксирует ещё две фишки в 6ой вертикали (нижняя так же в горизонтали, другая на диагонали).

Код: Выбрать все

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 x 0 0 0
0 0 1 0 1 0 0
0 1 0 0 0 x 0
x 1 0 1 0 x x

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

Код: Выбрать все

0 0 0 0 0 0 0
0 0 0 0 0 x 0
0 0 0 0 0 0 0
0 0 0 x 0 0 0
0 0 . 0 1 0 0
0 1 0 0 0 x 0
x 1 0 1 0 x x

Осталось 4 свободных фишки. В 6ой верикали нам нужна ещё одна. И нужна 5ая прямая.
Если снизу слева переместить свободную в 6ую вертикаль, то у нас 4 варианта.
Один из этих 4ёх срабатывает хорошо.

Код: Выбрать все

0 0 0 0 0 0 0
0 0 0 0 0 x 0
0 0 0 0 0 1 0
0 0 0 x 0 0 0
0 0 . 0 1 0 0
0 1 0 0 0 x 0
x . 0 1 0 x x

У нас получаются 3 свободных фишки на одной косой прямой. И мы можем передвинуть 4ую свободную фишку вдоль диагонали (в самый верхний угол), чтобы она тоже встала на эту прямую.

Код: Выбрать все

0 0 0 0 0 0 x
0 0 0 0 0 x 0
0 0 0 0 0 x 0
0 0 0 x 0 0 0
0 0 . 0 x 0 0
0 . 0 0 0 x 0
x . 0 x 0 x x

Теперь каждая фишка принадлежит ровно к двум прямым.

Ian · Сообщение **Ian** » 02 июн 2020, 04:07

Мне кажется важнее Ваше замечание что кроме углов наклона прямых 0,45,90 и 135 градусов должен быть представлен еще один угол (в данном случае, как сказали бы ученики более старших классов, arctg2). И я вообще этот путь отбрасывал, считая, что этот угол не уместится на таком маленьком поле. Тогда , естественно, некоторая точка должна содержаться минимум в трех прямых, сделать это легко почти для любой из точек, но как плохо станет остальным двум прямым набрать себе точек

zykov · Сообщение **zykov** » 02 июн 2020, 10:31

Ian писал(а):Source of the post Мне кажется важнее Ваше замечание что кроме углов наклона прямых 0,45,90 и 135 градусов должен быть представлен еще один угол (в данном случае, как сказали бы ученики более старших классов, arctg2)

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

zykov · Сообщение **zykov** » 02 июн 2020, 15:07

zykov писал(а):Source of the post Ещё одно замечание, что каждая из четырёх точек любой прямой является точкой пересечения этой прямой с одной из четырёх оставшихся прямых.

Это кстати исходное предположение, что каждая прямая пересекает 4 других.
Значит нет параллельных. Значит четырёх стандартных направлений (по 45 градусов) недостаточно.

zykov · Сообщение **zykov** » 04 июн 2020, 13:18

Да, это замечание легко доказать.
Предположим, что две какие-то прямые не имеют общих фишек (параллельные или пересекаются не в фишке). Тогда они используют 8 фишек. Оставшиеся две фишки могут максимум дать одну прямую, но никак не три прямых. Значит любые две прямые имеют ровно одну общую фишку (две фишки не могут, т.к. тогда они совпадут).
Предположим, что какие-то три прямые пересекаются в одной общей фишке. Тогда они используют 1+3*3=10 фишек. Т.е. не остается фишек для двух других прямых (из этих фишек другая прямая могла бы взять максимум 3 фишки - по одно с каждой из трёх прямых).
Значит одна фишка принадлежит не более чем двум прямым. На самом деле ровно двум, т.к. фишек на прямой четыре, а всего прямых пять (т.е. других прямых, кроме рассматриваемой, четыре).

Ian · Сообщение **Ian** » 04 июн 2020, 18:34

Да, конечно.
В задаче 1 пригодится опыт магических квадратов, правда магические нужно из разных чисел, но рассуждения аналогичны

zykov · Сообщение **zykov** » 21 июн 2020, 08:27

А что насчёт первой и второй?
В первой у меня как-то сложно выходит.
Во второй наоборот как-то просто (может не правильно).

Во второй:
На ту ёлку, где стало 179 снеговиков, они могли перебегать не более чем с 5 ёлок (стоящих близко к углам правильного шестиугольника, но угол между соседними чуть более 60 градусов и радиусы чуть различаются).
На этих пяти было в сумме 179. На других 174 было на каждой минимум по одному. Значит всего в лесу было минимум 179+174=353.
(Почему вопрос про 300? Просто так, чтобы запутать? Или я ошибаюсь?)

zykov · Сообщение **zykov** » 21 июн 2020, 09:09

По первой:
Очевидно, что в каждой вертикали, в каждой горизонтали и на каждой главной диагонали должно быть по 5 фишек.
Один из вариантов, это когда в одной из клеток (для каждой вертикали, горизонтали, диагонали) стоит ровно 5 фишек, в других нет фишек.
Если рассматривать только вертикали и горизонтали, то это соответствует перестановкам из 4. Их количество 4!=24.
Если ещё рассмотреть диагонали, то часть таких перестановок не подходит (например тривиальная перестановка, где на основной диагонали выбрано 4 раза). Перебором можно получить, что подходит 8 перестановок.
Например такая:
1000
0001
0100
0010
Из неё можно получить ещё одну зеркальной симметрий относительно диагонали проходящей через угол с 1.
И из каждой из этих двух можно получить ещё по 3 зеркальной симметрией относительно вертикали, горизонтали или обоих сразу (эквивалентно центральной симметрии) - угловая 1 перемещается в один из трёх других углов.

Если по этим 8 перестановкам поставить 5 фишек на 1 и не ставить фишки где 0, то будет 8 вариантов.
Ещё можно поставить 2 фишки на 1 и поставить 1 фишку где 0, то будет ещё 8 вариантов.

Но ещё можно ставить в одну позицию 2 фишки, в другую 3 фишки.
Для этого нужно заметить, что из 8 перестановок можно выделить два набора по 4 перестановки - эти 4 получаются отражениями в вертикали и горизонтали из друг друга. Внутри каждого из таких наборов по 4 эти перестановки попарно не пересекаются (а из разных наборов - пересекаются).
Значит из 4 перестановок из одного набора можно взять 2 перестановки и поставить 2 фишки по одной перестаовке и 3 по другой (или наоборот).
Будет $2C_4^2 = 2 \cdot 6=12$ вариантов. И ещё столько же со второго набора - всего 24 варианта.
Аналогично можно сделать для 1 фишки и 4 фишек - ещё 24 варианта.

Ещё есть варианты, когда в каждую вертикаль (горизонталь, диагональ) ставим по 0, 1, 1, 3 фишек или по 0, 1, 2, 2 фишек.
(Другими словами, суммируем эти 4 набора с весами 0, 1, 1, 3 или 0, 1, 2, 2. До этого мы делали тоже самое с весами 0, 0, 0, 5, с весами 1, 1, 1, 2 и с весами 0, 0, 2, 3 и 0, 0, 1, 4.)
Тут для 0, 1, 1, 3 будет $3C_4^3 = 3 \cdot 4=12$ вариантов. И ещё столько же со второго набора - всего 24 варианта.
Аналогично 24 варианта для 0, 1, 2, 2.

Т.е. всего будет $2(C_1^1 C_4^1 + 2 C_2^1 C_4^2 + 2 C_3^1 C_4^3 + C_4^1 C_4^4) = 112$

вариантов.

zykov · Сообщение **zykov** » 21 июн 2020, 10:05

Да, ещё могли бы быть смешанные варианты (в одной вертикали например 0, 0, 2, 3, а в другой 0, 0, 1, 4).
Вроде как их быть не может. Но надо бы доказать.

zykov · Сообщение **zykov** » 21 июн 2020, 11:37

zykov писал(а):Source of the post Вроде как их быть не может. Но надо бы доказать.

Это просто не верно.
Я комбинировал непересекающиеся перестановки, чтобы получить однородные комбинации фишек.
Но можно скомбинировать и пересекающиеся тоже.
Например можно получить такой квадрат:
5 0 0 0
0 0 3 2
0 2 0 3
0 3 2 0

Вобщем кроме этих 112 однордных есть ещё варианты.

zykov · Сообщение **zykov** » 21 июн 2020, 11:45

zykov писал(а):Source of the post Т.е. всего будет вариантов.

Если брать линейные комбинации не из 4, а сразу из всех 8 перестановок, то будет:
$C_1^1 C_8^1 + 2 C_2^1 C_8^2 + 2 C_3^1 C_8^3 + C_4^1 C_8^4 = 736$

Правда не уверен, что тут нет повторений.

Что-то как-то сложно (и не только для 8-класника).

zykov · Сообщение **zykov** » 21 июн 2020, 13:05

zykov писал(а):Source of the post Правда не уверен, что тут нет повторений.

Построил явно на компьютере все 736 квадрата, попарно сравнил - повторений нет.
Значит точно есть 736 разных комбинаций фишек.

Правда закралось подозрение, вдруг есть ещё комбинации не подпадающие под линейную комбинацию этих 8 перестановок...

zykov · Сообщение **zykov** » 21 июн 2020, 18:02

zykov писал(а):Source of the post Правда закралось подозрение, вдруг есть ещё комбинации не подпадающие под линейную комбинацию этих 8 перестановок...

Так и есть.
Сделал полный перебор на компьютере. Нашлось 1904 расстановки фишек.
Например такое:
1 1 3 0
0 2 0 3
0 1 2 2
4 1 0 0

Честно говоря, даже не знаю как посчитать это количество...

zykov · Сообщение **zykov** » 07 июл 2020, 19:26

zykov писал(а):Source of the post Сделал полный перебор на компьютере. Нашлось 1904 расстановки фишек.

Коментарий по методологии.
Если разрешить в квадрате любые действительные числа, то это будет вектор размера 16.
При этом есть 10 линейных ограничений (4 столбца, 4 строки и 2 диагонали). Правда независимых из них только 9. Это видно из того, что из 4 столбцов можно получить сумму всех 16 значений. Также эту сумму можно получить из 4 строк. Т.е. любое из этих 8 ограничений получается из остальных 7.
Т.е. ограничения дают подпространство размерности 16-9=7.

Далее, для первой строки можно рассмотреть все варианты фишек дающие в сумме 5. Всего таких варинтов 56. Ранее в другом контексте я это показывал:

zykov писал(а):Source of the post $2(C_1^1 C_4^1 + 2 C_2^1 C_4^2 + 2 C_3^1 C_4^3 + C_4^1 C_4^4) = 112 = 2 \cdot 56$

Аналогично для второй строки. Всего будет вариантов $56^2 = 3136$

. Руками трудно перебирать, но на компьютере без проблем.
Тут сразу же можно было бы отбросить из этих 3136 некоторые варианты для которых один из 4 столбцов или одна из 2 диагоналей уже имеет сумму более 5. Но я этого не делал.
Мы зафиксировали 8 значений и два ограничения мы уже учли - первая и вторая строки. Они никак не влияют на оставшиеся 8 значений. Ограничение "сумма третьей строки" можно выбросить, как зависимое. Остается 7 ограничений (4 столбца, нижняя строка и 2 диагонали) и 8 неизвестных. Для любого из этих 8 можно сделать перебор 6 вариантов (от 0 до 5). Тут тоже сразу же можно было бы отбросить варианты, где сумма столбца или диагонали превышают 5. Но я этого не делал - перебирал все $6 \cdot 3136 = 18816$ вариантов.
Далее, для этих выбранных 9 значений оставшиеся 7 находятся как решение линейной системы. Нужно только проверить, что они являются разрешенными - целые от 0 до 5. Дробных у меня не возникало (хотя в обратной матрице есть коэффициенты "одна вторая"). Некоторые получаются отрицательные - они отбрасываются.
В результате получается 1904 уникальных варианта, каждый из которых удовлетворяет ограничениям - 10 линейных ограничений и целое значение от 0 до 5.

Портал Естественных Наук, версия 1.1