Задача М1112‍‍

Ответ: в случае а) — можно, в случае б) — нельзя.

Заметим, что если $c=a+b+ab$‍,‍ то $c+1=(a+1)(b+1)$‍.‍ Поэтому вместо чисел, записанных на доске, удобно рассматривать числа, на 1 большие. Тогда каждое новое число равно произведению двух уже имеющихся. Вначале имелись числа $2=1+1$‍‍ и $3=2+1$‍;‍ значит, все последующие числа имеют вид $2^n\cdot3^m$‍‍ ($n$‍‍ и $m$‍‍ — натуральные). Остаётся проверить данные числа: $13121+1=2\cdot3^8$‍,‍ а $12131+1=2^2\cdot3^2\cdot337$‍.‍

в) В силу сказанного выше, достаточно доказать, что имеется бесконечно много натуральных чисел $n\gt1$‍,‍ не представимых в виде $(x+1)(y+1)$‍‍ с натуральными $x$‍‍ и $y$‍.‍ Но этому условию удовлетворяют все простые числа (и только они), а их, как известно, бесконечно много. (Напомним евклидовскую идею доказательства бесконечности множества простых чисел: если $p_1$‍,‍ $\ldots$‍,‍ $p_k$‍‍ — простые, то число $p_1\cdot\ldots\cdot p_k+1$‍‍ имеет делителем простое число, отличное от $p_i$‍.)‍

г)Если $z=x+y+2xy$‍,‍ то $2z+1=(2x+1)(2y+1)$‍.‍ Рассуждая так же, как в задаче в), мы убеждаемся, что наше утверждение эквивалентно тому, что множество простых чисел вида $2z+1$‍‍ (т. е. нечётных) бесконечно.

Докажите самостоятельно утверждения задач в) и г); для любого натурального $a$‍‍ множество чисел, не представимых в виде $x+y+axy$‍,‍ бесконечно.