Сюда я раз в 10 лет наваливаю задачек, которые постил в разное время вконтакте под тегом #вотэтазадача Решения, где есть, написаны в комментариях.
вотэтазадача 13. Покрытие прогрессиями.
Не очень сложная, но порадовала. Прикольно ставить крестики на прямой.
Можно ли покрыть множество целых чисел конечным числом арифметических прогрессий, разности которых не равны 1 и кроме того а) различны б) попарно взаимно просты?
а) Можно, пример строится б) Нельзя. Допустим, что можно и разности прогрессий равны d1,d2,...,dn. Можно посчитать вероятность, с которой данное число покрыто какой-то прогрессией. По формуле включения-исключения получаем, что эта вероятность равна 1-(1-1/d1)(1-1/d2)...(1-1/dn)<1, противоречие.
а) Можно, пример строится
ОтветитьУдалитьб) Нельзя. Допустим, что можно и разности прогрессий равны d1,d2,...,dn. Можно посчитать вероятность, с которой данное число покрыто какой-то прогрессией. По формуле включения-исключения получаем, что эта вероятность равна 1-(1-1/d1)(1-1/d2)...(1-1/dn)<1, противоречие.