1. Главная
  2. Библиотека
  3. Теория вероятностей
  4. На доске расставляют несколько фишек. Две фишки считают...
Разбор задачи

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

  • Предмет: Теория вероятностей
  • Автор: Кэмп
  • #Теория вероятностей и математическая статистика
  • #Теория графов
На доске расставляют несколько фишек. Две фишки считаются близко расположенными, если из клетки, занятой одной из них, можно прийти в клетку, занятую другой фишкой, за 1 или за 2 хода. Каждый ход - это либо перемещение в соседнюю по диагонали клетку, либо

Условие:

На доске 7×77 \times 7 расставляют несколько фишек. Две фишки считаются близко расположенными, если из клетки, занятой одной из них, можно прийти в клетку, занятую другой фишкой, за 1 или за 2 хода. Каждый ход - это либо перемещение в соседнюю по диагонали клетку, либо ход шахматного коня (буквой I). Какое наибольшее число фишек можно расставить на такую доску, чтобы никакие две фишки не были близко расположенными?

Решение:

Наша задача состоит в том, чтобы расставить на доске 7×7 фишки так, чтобы ни для какой пары фишек существовала последовательность из одного или двух разрешённых ходов, переводящих одну фишку в другую. Разрешённые ходы – это перемещение на соседнюю по диагонали клетку (то есть смещения (1,1),(1,–1),(–1,1),(–1,–1)) и шахматный ход конём (смещения (2,1),(2,–1),(–2,1),(–2,–1),(1,2),(1,–2),(–1,2),(–1,–2)). Таким образом, если между двумя фишками разность координат окажется равной одному из векторов, которые можно получить суммой одного или двух таких разрешённых ходов, эти фишки считаются “близк...

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

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

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

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

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

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

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

Топ 3 ошибок

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

Не нашел нужную задачу?

Воспользуйся поиском

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