Математическое и загадочное

[Рогожников Евгений]

Всё верно. Но есть более интересный вариант этой задачи. Условие полностью идентичное кроме одной детали. Заранее неизвестно сколько мешков с фальшивыми монетами. Нужно также за одно взвешивание найти все мешки с фальшивыми монетами. 

[E.K.]

14 hours ago, Рогожников Евгений said:

Скорее уж её могли бы давать на собеседовании в Яндекс

-Еда

 

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

 

On 24.01.2022 at 14:31, Рогожников Евгений said:

Пусть есть число х. Пусть 2 входит в разложении x в степени n , а 3 в степени m .  Тогда раскрасим число x в цвет (n+2*m) mod(3)

Остается показать, что такая раскраска подойдет.  

Тут просто достаточно перебрать 3 варианта и убедиться, что в каждом будет разный цвет. В каждом случае это очевидно

x и 2х

x и 3x

2x и 3x

 

Элегантно! Любое число X можно представить в виде: X = 2^n * 3^m * p

Нужно показать, что {X/3, X/2, 2X/3} =>

 

2^(n-1)*3^m*p

2^n*3^(m-1)*p

2^(n+1)*3^(m-1)*p

 

дают меньше трёх разных значений при (n+2*m) mod(3)

Смотрим:

 

(n - 1 + 2m)                     = (n + 2m - 1)

(n + 2m - 2)                     = (n + 2m - 2)

(n + 1 + 2m - 2)               = (n + 2m - 1)

 

Первый (X/3) и третий (2/3 X) дают одинаковый модуль, т.е. одинаковый цвет. Всё верно. Весьма просто и элегантно..

 

У меня сложнее получилось.

 

Посмотрим на первые 6 натуральных чисел:

Покрасим 1 в... ну, допустим, вертикальный цвет. 2 в 2 раза больше единицы, посему вертикальным цветом покрашена быть не может. Пусть будет покрашена горизонтальным цветом. 3 в 3 раза больше 1 - тоже не может быть "вертикальной". Но двойка это 2/3 от тройки, то есть, они тоже должны быть разного цвета. Итого, пусть это будет "плюсовой" цвет.

 

1-2-3 покрасили, 4 непонятно, 5 тем более - а вот 6 ->

6 не может быть цвет 2 (-) и 3 (+), посему только вертикально (|). Тут же смотрим на 4ку и видим, что она не может быть (-) по причине 2ки и (|) из-за 6ки. Вывод: 4ка только (+).

Умножаем весь ряд на 2 (при этом 5ку выкинем за ненадобностью).

8 непонятно, 12 однозначно (-) (по причине 4 и 6), а оттуда получается 8ка, она будет (|). Если проделать ещё одну-две итерации, то видно (а туда и формулу можно притянуть), что цвета степеней двойки идут по циклу: ( | - + | - + ...)

 

Примерно аналогичной алхимией получаем, что цвета степеней тройки идут в обратном порядке: ( | + - | + - ...)

 

Теперь рисуем табличку. По горизонтали - степени тройки, по вертикали - степени двойки, в каждой ячейке 2^n * 3^m  =>

Что означает, что у ячейки цвет не такой, как у её номера/3, номера/2 и 2/3 её номера? Что цвет отличается от ячейки слева (1/3), сверху (1/2), внизу слева (2/3). Дальше доказательство сводится к фразе "Смотри!"

Итого, мы покрасили все натуральные числа вида 2^n*3^m. А каждое число можно представить в виде q*2^n*3^m. Для каждого такого q рисуем табличку аналогичную верхней. Только всё умножаем на q.

 

Вроде всё.

 

UPD. Ещё элегантней, имхо, выглядит вот так:

Красить надо в цвет (n-m) mod(3)

[E.K.]

17 hours ago, Рогожников Евгений said:

Всё верно. Но есть более интересный вариант этой задачи. Условие полностью идентичное кроме одной детали. Заранее неизвестно сколько мешков с фальшивыми монетами. Нужно также за одно взвешивание найти все мешки с фальшивыми монетами. 

Ну, очевидно, надо брать поочерёдно столько монет, чтобы все возможные комбинации давали различные суммы. Например, 1-2-4-...-2^n. Взвешиваем, вычисляем недостаток, раскладываем его в бинарном виде - и вот он, список мешков c фальшивками.

 

А можно ещё усложнить задачу: Неизвестно сколько вообще мешков было и также неизвестно сколько среди них с фальшивыми монетами.

[Рогожников Евгений]

4 часа назад, E.K. сказал:

 

А можно ещё усложнить задачу: Неизвестно сколько вообще мешков было и также неизвестно сколько среди них с фальшивыми монетами

Ну да. Скидываем 2^ n с каждого  мешка с номером n. Это даст ответ. 

 

[E.K.]

Есть 30 карточек, на которых написаны целые числа от 1 до 30, каждое по одному разу. Нужно выложить часть из них по кругу так, чтобы для любых двух соседних карточек одно число делилось на другое нацело. Какое максимальное количество карточек получится выложить таким образом?

 

У меня пока получилось 22 карточки..

[Рогожников Евгений]

Тоже нашёл цепочку в 22. Также удалось доказать, что 25 построить не получится. Ведь 17, 19, 23, 29 не могут быть в цепочке. Также если рассмотреть пары (11, 22) и (13, 26) , то если в цепочке есть число из одной пары, то другая пара в цепочку не попадёт. 

 

Вообще, задача явно подпадает под решение  через граф. Надо рассмотреть граф. Вершины - это наши числа. Ребром соединяем, если одно из чисел делится на другое. Но с ходу доказать невозможность цепочки длиной 23 не получается. Хотя, думаю, что нужно просто повнимательней посмотреть

Изменено 4 февраля, 2022 пользователем Рогожников Евгений

[E.K.]

Сотрудница компании просит помощи..

 

> Задача №8. 3-й класс!!! Я два раза перечитывала, чтобы понять, что хотят)

[oit]

Да вроде понятно условие.

И не сложная

[Рогожников Евгений]

Ну да. Совсем простая. В 3-м классе, наверно, сложно решить. Но возможно. У меня дочь сейчас, как раз, в третьем учится. Так что знаю о чем говорю 😁

[Рогожников Евгений]

Ну да. Совсем простая. В 3-м классе, наверно, сложно решить. Но возможно. У меня дочь сейчас, как раз, в третьем учится. Так что знаю о чем говорю 😁недавно была олимпиада для 3-го класса. Задачи вот такие. Правда моя решила только 2. Но у неё были одноклассники которые решили 5 и 6 задач. 

 

Изменено 6 февраля, 2022 пользователем Рогожников Евгений

[E.K.]

Про 30 цифр у меня получилось вот так:

 

18 9 27 3 21 7 1 13 26 2 30 15 5 10 20 4 16 8 24 12 24 6

 

Сразу выкидываются простые, которые больше 30/2=15: {17, 19, 23, 29}. Поскольку с одной стороны у них однозначно окажется единица, а с другой нечто большее 30.

 

Остаются простые 11 и 13, у которых с одной стороны должна быть единица, а с другой 22 и 26. Что-то вроде: < 22 11 1 13 26 > - и других вариантов тут быть не может. Однако, такая комбинация требует продолжением двоек с обеих сторон, а в наличии только одна двойка.. Посему, отбрасываем.

 

Также остаются простые 5 и 7, которые вокруг себя также генерят не очень большое количество возможностей:

 

5 -> 10, 15, 20, 25, 30.

7 -> 14, 21, 28.

 

Ага, а тут мне блямкает, что ->

 

 

Мне любопытно, пойду посмотрю...

[E.K.]

Ничосе детей задачками мучают... У меня тоже есть дочка, но она (к счастью) пока только во 2м классе

 

Так вот, продолжая тему 1-30. Получается, что из 11-22 и 13-26 можно выбрать только один вариант. То есть, минус еще 2 числа. Итого, 30 минус простых 4>15 и минус ещё два = 24 числа осталось на столе.

 

Ага, но там ещё какая-то засада была с 7-14-21-28...

[Рогожников Евгений]

Интересно. У меня другая цепочка

1 13 26 2 14 7 21 3 27 9 18 6 12 24 8 4 20 10 30 15 5 25

 

Ясно, что не вошли 17, 19, 23,29. А также 11 и 22, которые можно заменить на 13 и 26. 

 

и у меня не вошли 16 и 28.

у вас же не вошли 25 и 14

 

и это явно неспроста. 

 

Мои рассуждения следующие. Цепочка 22 уже есть. Пытаемся найти более чем длинную.  1 всегда войдёт в цепочку. К ней можно присоединить 1 13 26 2  или 1 11 22 2. И это обязательно. В противном случае у нас не войдёт ни одно из чисел 11, 22, 13, 26 и тогда цепочка будет уже не длиннее 22.

 

Далее получаем первую вилку с числом 25. Это число или входит в цепочку или нет. Это и есть вилка. И, нам удалось построить цепочки длины 22 в обоих случаях. 

 

Приведу свои рассуждения для случая

Если 25 входит в цепочку.  В этом случает она будет соседом 1. И мы получаем вот такую цепочку

 

5 25 1 11 22 2

 

Так как 1 получила обоих соседей, то 

Далее интересны числа 21 и 27. Они оба должны иметь соседом 3 и мы растим вторую под цепочку

 

7 21 3 27 9

 

и у нас уже выпадает 3 из числа возможных соседей. 

 

и тогда внимание падает на 15. Чтобы она вошла в цепочку то ей останутся соседи 5 и 30. И мы ещё нарастим первую подцепочку

 

30 15 5 25 1 11 22 2

 

 

[E.K.]

Какая фигура на картинке лишняя?

 

[santax]

первая: только она не 'уникальная'. У 2й обводка не черная; 3я - круг; 4я-зеленая; 5я - маленькая.