Математический форум Math Help Planet
http://mathhelpplanet.com/

Ноутбук с фильмами
http://mathhelpplanet.com/viewtopic.php?f=50&t=61640
Страница 1 из 1

Автор:  boroda33 [ 12 сен 2018, 20:31 ]
Заголовок сообщения:  Ноутбук с фильмами

20 одноклассников написали списки с 5 фильмов, которые им нравятся. Выяснилось, что любые 2 списка имеют не более 2 m одинаковых фильмов. Классный руководитель загрузил все эти фильмы на ноутбук. Какое минимальное количество фильмов может быть на ноутбуке, если а) m=1; в)m=2.

Автор:  boroda33 [ 17 сен 2018, 16:56 ]
Заголовок сообщения:  Задача на количество фильмов

20 одноклассников написали списки с 5 фильмов, которые им нравятся. Выяснилось, что любые 2 списка имеют не более m одинаковых фильмов. Классный руководитель загрузил все эти фильмы на ноутбук. Какое минимальное количество фильмов может быть на ноутбуке, если а) m=1; в)m=2.

Автор:  Slon [ 17 сен 2018, 18:58 ]
Заголовок сообщения:  Re: Ноутбук с фильмами

Это Вам в школе задали?
Что за тему Вы проходите?

Автор:  boroda33 [ 17 сен 2018, 19:05 ]
Заголовок сообщения:  Re: Ноутбук с фильмами

Да, задание к турниру по математике задали 5 задач в школе, уже испробовал несколько идей, наименшое количество получил 81 фильм, прошу помощи или идеи возможно ктото их имеет!!!

Автор:  Slon [ 17 сен 2018, 19:20 ]
Заголовок сообщения:  Re: Ноутбук с фильмами

А как 81 получилось?
Хотя понятно, неужели меньше никак?
Для какого числа Вы можете доказать, что столько не бывает?

Автор:  boroda33 [ 17 сен 2018, 19:27 ]
Заголовок сообщения:  Re: Ноутбук с фильмами

Нашел иное решение 57 фильмов пока самое наименьшее количество.


Принял что каждый ученик имеет по пять пар фильмов совместных, таких полноценных пар получилось 60 (учитывая что фильм первого ученика и друго и наоборот второго и первого это одно и то же) - тогда таких фильмов 45
Осталось еще 6 пар учеников, которые между собой имеют 3 общие фильмы !!
И еще по 3 каждый которых нельзя отнести ни к кому, ведь у каждого уже есть по 5 !!

Автор:  boroda33 [ 17 сен 2018, 19:28 ]
Заголовок сообщения:  Re: Ноутбук с фильмами

Возможно у Вас получится меньшее количество, буду благодарен за идею !!!

Автор:  Slon [ 18 сен 2018, 14:24 ]
Заголовок сообщения:  Re: Ноутбук с фильмами

посмотрите конечные геометрии, тогда поймете что в первом пункте ответ 21

Автор:  boroda33 [ 18 сен 2018, 16:36 ]
Заголовок сообщения:  Re: Ноутбук с фильмами

Как там может бить ответ 21 фильм??

Автор:  swan [ 19 сен 2018, 14:42 ]
Заголовок сообщения:  Re: Ноутбук с фильмами

ОК.
Давайте я вам покажу как получить 25 фильмов.

Выпишем числа в квадрат [math]5\times 5[/math]

[math]\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{matrix}[/math]

Наша задача найти 20 пятерок чисел, любые две из которых пересекаются не более чем по одному числу.
В центре каждой клеточки поставим точку. Из геометрии нам известно, что две прямые пересекаются не более чем в одной точке. Давайте посмотрим сколько прямых, содержащих 5 точек, мы сможем провести?

5 горизонтальных:
1. [math]\begin{matrix} 1 & 2 & 3 & 4 & 5 \end{matrix}[/math]
2. [math]\begin{matrix} 6 & 7 & 8 & 9 & 10 \end{matrix}[/math]
3. [math]\begin{matrix} 11 & 12 & 13 & 14 & 15 \end{matrix}[/math]
4. [math]\begin{matrix} 16 & 17 & 18 & 19 & 20 \end{matrix}[/math]
5. [math]\begin{matrix} 21 & 22 & 23 & 24 & 25 \end{matrix}[/math]

5 вертикальных:
6. [math]\begin{matrix} 1 & 6 & 11& 16& 21\end{matrix}[/math]
7. [math]\begin{matrix} 2& 7 & 12& 17 & 22\end{matrix}[/math]
8. [math]\begin{matrix} 3& 8& 13 & 18& 23\end{matrix}[/math]
9. [math]\begin{matrix} 4 & 9 & 14 & 19 & 24\end{matrix}[/math]
10. [math]\begin{matrix} 5 & 10 & 15 & 20 & 25 \end{matrix}[/math]
2 диагональных:
11. [math]\begin{matrix} 1 & 7 & 13& 19& 25\end{matrix}[/math]
12. [math]\begin{matrix} 5& 9 & 13& 17 & 21\end{matrix}[/math]
Вроде всё?
Выручает следующий трюк: склеим между собой левый и правый края квадрата, получив цилиндр.
А если склеить вдобавок верхний и нижний край, то получим бублик (тор).
Здесь мы тоже можем провести ещё 4 +4 "диагонали", которые будут "параллельны" главным диагоналям:

13. [math]\begin{matrix} 1 & 10 & 14 & 18 & 22 \end{matrix}[/math]
14. [math]\begin{matrix} 2 & 6 & 15 & 19 & 23 \end{matrix}[/math]
15. [math]\begin{matrix} 3 & 7 & 11 & 20 & 24 \end{matrix}[/math]
16. [math]\begin{matrix} 4 & 8 & 12 & 16 & 25 \end{matrix}[/math]

17. [math]\begin{matrix} 5& 6& 12& 18& 24\end{matrix}[/math]
18. [math]\begin{matrix} 4 & 10 & 11 & 17 & 23 \end{matrix}[/math]
19. [math]\begin{matrix} 3 & 9 & 15 & 16 & 22 \end{matrix}[/math]
20. [math]\begin{matrix} 2 & 8& 14 & 20 & 21 \end{matrix}[/math]

Итого: у нас есть 20 прямых на торе, проходящих через 25 точек. Каждая прямая содержит пять точек, а пересекаются любые две этих прямые не более чем в одной точке. Каждой точке теперь сопоставляем фильм, а прямой - список.

Попробуйте развить эту идею и получить результат, указанный Slon

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/