1
1

Прошу помощи:

Дана таблица MxN с целыми числами от 1 до P, записанными в каждой ячейке. Каждое число записано по крайней мере в одной ячейке. Пара чисел (a,b), 1 <= a < b <= P называются соседними, если есть хотя бы одна пара ячеек, имеющих общее ребро, таких что ячейки помечены этими числами. Какую нижнюю границу для количества "соседей" вы можете указать? Точна ли эта оценка?

Мои продвижения в решении:

  • Очевидно, P > mn быть не может, поэтому стоит рассмотреть всего два случая: P = mn, P < mn.
  • Я заметил, что если P = mn, то независимо от перестановки чисел, ответ константен.
  • В случае P = mn, ответом будет являться значение выражения n - 1 + (2n - 1)(m - 1). Эту формулу я вывел, выписывая тучу примеров на листочке и считая ответ. Строго доказать я её не могу, к сожалению.
  • Если P < mn, то ответ явно меньше, чем если бы P был равен mn.

задан 4 Май 14:50

возвращен 8 Май 23:20

falcao's gravatar image


269k63751

Возможно, не совсем понял определние соседних ячеек. Но что если расставлять числа максимально жадно, то есть через одну клетку. Потом если есть избыток, то накидовать числа так, чтобы они соприкасались с наименьшим число клеток. То есть они будут давать +2 соседа каждая с начала, потом +3 и +4 в худшем случае.

UPD: Только что заметил, что каждая ячейка заполнена числом от 1 до P, причём каждое число из множества есть в таблице.

(4 Май 14:57) Autocellar
1

@Autocellar, вот пример:

... 5 ...

4 1 2

... 3 ...

В данной конструкции к ответу прибавится +4 за счет четырех соседних ячеек: (1, 2), (1, 3), (1,4) и (1, 5)

А для примера M = 1, N = 3, P = 3, для расстановки: | 1 | 2 | 3 | или | 2 | 3 | 1 | или | 3 | 1 | 2 | и т.д Ответом будет являться всегда 2. Независимо, как я уже сказал, от порядка чисел.

10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Проблема не актуальна". Закрывший - falcao 8 Май 23:20

0

Окей, лучший случай это $%P-1$% сосед. Ставим единицу, окружаем её двойками. Двойку окружаем тройку и так дальше. Оценка не точна, потому что поле не всегда нам позволит такое, но чувствую, что можно ограничить сверху $%2\ast P$%

ссылка

отвечен 4 Май 15:33

10|600 символов нужно символов осталось
Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,482
×970
×502
×140
×20

задан
4 Май 14:50

показан
191 раз

обновлен
8 Май 23:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru