Архив задач олимпиады по математике и криптографии
Отрезки на прямой
На прямой заданы два отрезка, длины которых равны 20162015-1 и 20162018-1. Как с помощью циркуля построить отрезок длины 2015, осуществляя построения только на этой прямой (т.е. без использования точек вне прямой)?
Для любых трех натуральных чисел m,n и a справедливо равенство (am-1 am-1)=a(m,n)-1. Здесь (x,y) – наибольший общий делитель чисел x и y. В условии задачи показатели m и n взаимно просты, поэтому число a(m,n)-1 равняется числу a-1 то есть длине искомого отрезку. Его можно получить по алгоритму Евклида: меньший отрезок откладывают циркулем на большем столько раз, сколько возможно; оставшуюся часть большего отрезка (принимаемую за «остаток от деления») откладывают на меньшем отрезке и т.д. Покажем как можно решить задачу непосредственно (а по сути, перевывести упомянутое равенство в частном случае). Даны два отрезка x=a2015-1 и x=a2018-1, где a=2016 Будем, пока возможно, откладывать меньший отрезок х на большем у. То есть делим у на х с остатком: a2018-1=a³(a2015-1)+ a³-1. Теперь делим меньший отрезок х на остаток: a2015-1=a²(a2013-1)+a²-1. Поскольку 2013 делится на 3, число a2013-1 делится нацело на число a³-1 при этом a²-1 – остаток от деления числа х на a³-1 И, наконец, a³-1=a(a²-1)+a-1. Тем самым доказано, что наибольшей общей мерой данных в условии отрезков будет отрезок длиной a-1.