math.luga.ru : Форум

Ещё одна интересная задача-конкурс.
Расставьте в каждой клетке шахматной доски 8 на 8 цифры 1, 2, 3 так, чтобы нашлось как можно больше трёхклеточных уголков с тремя различными цифрами. Ответы представляйте в таком формате:
12121212
12112211
12121212
31131211
12121212
12312123
22222222
22332323
Число нужных уголков равно 14.
Кто больше?
Небезыинтересно было бы посмотреть и на "компьютерный ответ"...

Так.
1) Будем трёхклеточный уголок называть "молочным", если в нём стоят попарно различные цифры;
2) Все уголки разбиваются на группы по 4 - В квадратике 2 на 2. (Строго писать не буду - понятно, про что говорю.);
3) Из этих 4-х уголков х.б. 2 не "молочные", отсюда не более половины всех уголков "молочные";
4)
1 2 3 1 2 3 1 2
3 1 2 3 1 2 3 1
2 3 1 2 3 1 2 3
1 2 3 1 2 3 1 2
3 1 2 3 1 2 3 1
2 3 1 2 3 1 2 3
1 2 3 1 2 3 1 2
3 1 2 3 1 2 3 1

При такой, например, расстановке, каждый квадратик 2 на 2 имеет вид (точнее, числа в нём по такому принципу расставлены):
a b
c a
И в нём ровно 2 "молочных" уголка.
Т.е.количество "молочных" уголков равно половине всех уголков.
Это есть максимальное возможное количество. (по пункту 3) );
5) Численно: максимально 7*7*2=98 уголков являются "молочными".

ИТАК: 98 уголков - максимум =)

Кстати, для поля N на M (N,M>1) ответ - 2*(N-1)*(M-1). Вот. Вроде как так =)

А тут приз будет? =):D

Иногда люди "думают" быстрее машин =)

Влад писал(а):Иногда люди "думают" быстрее машин =)

Вот именно! Я же и написал эту задачу, чтобы устроить провокацию программистам... Не попался!

PSP писал(а):

Влад писал(а):Иногда люди "думают" быстрее машин =)

Вот именно! Я же и написал эту задачу, чтобы устроить провокацию программистам... Не попался!

А я не придумал ничего кроме тупого перебора... А зачем он тут нужен-то? А если доска больше и не такая? Не... Тут надо просто тупо решить =) "Умного" ничего тут не придумаешь, наверное... =)

Влад - молодец! Хотя и учится на втором курсе мат-меха, но не разучился решать школьные задачи. (И это я пишу без какой-либо иронии.)