В таблице расставлены 16 различных натуральных чисел. Для каждой строки и каждого столбца таблицы нашли наибольший общий делитель расположенных в нем чисел. Оказалось, что все найденные восемь чисел различны. Для какого наибольшего n можно утверждать, что в такой таблице найдется число не меньше n?
(А. Храбров)
Если в каком-то ряду наибольший общий делитель равен n, то в нем есть четыре числа, делящихся на n, a, значит, число, не меньшее, чем 4n. Поскольку наибольшие общие делители во всех рядах различны, один из них заведомо не меньше 8. Тогда в соответствующем ему ряду должно быть число, не менышее 32. Приведем теперь пример таблицы, в которой все числа не
5 | 10 | 15 | 20 |
30 | 6 | 18 | 12 |
7 | 14 | 21 | 28 |
8 | 16 | 24 | 32 |
Замечание. Наибольшие общие делители заведомо должны быть числами от 1 до 8, а ряды с НОДами 6, 7 и 8 должны быть составлены из тех чисел, которые стоят в соответствующих рядах в таблице из примера (возможно в другом порядке).
Ответ: 32.