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