1. Главная
  2. Библиотека
  3. Геометрия
  4. Дана колода из 300 карт, на каждой из которых записано...
Разбор задачи

Дана колода из 300 карт, на каждой из которых записано натуральное число от 1 до 300 (каждое число встречается по одному разу). Петя раскладывает пасьянс. Для этого Петя выкладывает карты в прямоугольник ( 3 строки, 100 столбцов) так, что числа на картах

  • Предмет: Геометрия
  • Автор: Кэмп
  • #Теория вероятностей и математическая статистика
  • #Теория оптимизации
Дана колода из 300 карт, на каждой из которых записано натуральное число от 1 до 300 (каждое число встречается по одному разу). Петя раскладывает пасьянс. Для этого Петя выкладывает карты в прямоугольник ( 3 строки, 100 столбцов) так, что числа на картах

Условие:

Дана колода из 300 карт, на каждой из которых записано натуральное число от 1 до 300 (каждое число встречается по одному разу). Петя раскладывает пасьянс. Для этого Петя выкладывает карты в прямоугольник 3×1003 \times 100 ( 3 строки, 100 столбцов) так, что числа на картах в каждом столбце возрастают сверху вниз, а также любое число в нижней строке больше любого числа в верхней строке. Удачностью пасьянса называется сумма всех чисел на карточках в верхней и нижней строках. Какой максимальной удачности пасьянс может выложить Петя?

Решение:

Найдем максимальное значение удачности, то есть сумму чисел на верхней и нижней строках, при условии, что все 300 карт раскладываются в прямоугольник 3×100 так, чтобы в каждом столбце числа были в строго возрастающем порядке (верхнее меньше среднего, среднее меньше нижнего), а любое число нижней строки было больше любого числа верхней строки.

Заметим, что все 300 чисел распределены между тремя строками. Обозначим:
Т – верхняя строка (100 чисел),
С – средняя строка (100 чисел),
Н – нижняя строка (100 чисел).

Условие «любое число нижней строки...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое ключевое условие позволяет свести задачу максимизации удачности к минимизации суммы чисел в средней строке?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Выбери предмет