|
Название: Бедные чиновники Отправлено: fortpost от Январь 18, 2012, 23:12:55 В прямоугольном зале в 10 рядах по 10 кресел в каждом сидят 100 чиновников, получающих разные зарплаты. Чиновник считает себя высокооплачиваемым, если, опросив всех соседей (справа, слева, спереди, сзади и по диагоналям), он убеждается, что зарплату больше его получает не более чем один из соседей. Какое наибольшее число чиновников могут считать себя высокооплачиваемыми?
Название: Re: Бедные чиновники Отправлено: Торлоки от Январь 18, 2012, 23:52:12 Неохота подсчитывать , но ведь эта задача напоминает известную задачу о 8 ферзях ,только в данном случае доска 10 на 10 . Получается , максимум- 10 чиновников
Название: Re: Бедные чиновники Отправлено: Торлоки от Январь 18, 2012, 23:56:55 Поторопился с ответом ) в данном случае не ферзи . а короли. На доске 8 на 8 ответ- 16 , а тут получается 25
Название: Re: Бедные чиновники Отправлено: Валерий от Январь 19, 2012, 00:36:42 del
Название: Re: Бедные чиновники Отправлено: Sirion от Январь 19, 2012, 00:42:05 очевидно, что в любом квадрате 2х2 может быть не более двух высокооплачиваемых чиновников
отсюда на всей доске их не более 50 пример для 50: ЗПi,j=(i mod 2)*50+10*(i div 2)+j - где ЗПi,j - зарплата чиновника в итой строке и житом столбце (строки и столбцы нумеруются от 0 до 9) |