сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Блок из N под­ряд иду­щих на­ту­раль­ных чисел на­зы­ва­ет­ся хо­ро­шим, если про­из­ве­де­ние каких-то двух из них де­лит­ся на сумму осталь­ных. Для каких N су­ще­ству­ет бес­ко­неч­но много хо­ро­ших бло­ков?

 

(С. Бер­лов)

Спрятать решение

Ре­ше­ние.

Ре­ше­ние 1 (де­ли­мость). Пусть блок k плюс 1, k плюс 2, k плюс 3, \ldots, k плюс N ока­зал­ся хо­ро­шим. Сумма всех чисел этого блока равна

k N плюс дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби .

Пред­по­ло­жим, что про­из­ве­де­ние  левая круг­лая скоб­ка k плюс a пра­вая круг­лая скоб­ка левая круг­лая скоб­ка k плюс b пра­вая круг­лая скоб­ка (где 1 мень­ше или равно a не равно q b мень­ше или равно N пра­вая круг­лая скоб­ка де­лит­ся на сумму осталь­ных чисел блока, т. е. на

s=k левая круг­лая скоб­ка N минус 2 пра­вая круг­лая скоб­ка плюс дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби минус a минус b .

Рас­смот­рим наи­боль­ший общий де­ли­тель чисел k плюс a и s:

 НОД левая круг­лая скоб­ка k плюс a, s пра­вая круг­лая скоб­ка =НОД левая круг­лая скоб­ка k плюс a, s минус a минус b минус левая круг­лая скоб­ка N минус 2 пра­вая круг­лая скоб­ка левая круг­лая скоб­ка k плюс a пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка =
=НОД левая круг­лая скоб­ка k плюс a, дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби минус левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка a минус b пра­вая круг­лая скоб­ка .

Если  левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка a плюс b не равно q дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби , то

 НОД левая круг­лая скоб­ка k плюс a, s пра­вая круг­лая скоб­ка =НОД левая круг­лая скоб­ка k плюс a, дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби минус левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка a минус b пра­вая круг­лая скоб­ка мень­ше или равно \left| дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби минус левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка a минус b| мень­ше или равно дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби плюс
 плюс левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка a плюс b мень­ше или равно 2 N в квад­ра­те .

Ана­ло­гич­но, если  левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка b плюс a не равно q дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби , то  НОД левая круг­лая скоб­ка k плюс b, s пра­вая круг­лая скоб­ка мень­ше или равно 2 N в квад­ра­те . Но тогда

 k N плюс дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби минус a минус b=s= НОД левая круг­лая скоб­ка левая круг­лая скоб­ка k плюс a пра­вая круг­лая скоб­ка левая круг­лая скоб­ка k плюс b пра­вая круг­лая скоб­ка , s пра­вая круг­лая скоб­ка мень­ше или равно левая круг­лая скоб­ка 2 N в квад­ра­те пра­вая круг­лая скоб­ка в квад­ра­те =4 N в сте­пе­ни левая круг­лая скоб­ка 4 пра­вая круг­лая скоб­ка ,

что не­воз­мож­но при боль­ших k, на­при­мер, при k боль­ше 4 N в сте­пе­ни левая круг­лая скоб­ка 4 пра­вая круг­лая скоб­ка . Сле­до­ва­тель­но, при боль­ших k либо

 левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка a плюс b= дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби ,

либо

 левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка b плюс a= дробь: чис­ли­тель: N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби .

Рас­смот­рим пер­вый слу­чай. По­сколь­ку

2 левая круг­лая скоб­ка N минус 1 пра­вая круг­лая скоб­ка a плюс 2 b=N левая круг­лая скоб­ка N плюс 1 пра­вая круг­лая скоб­ка ,

число 2 левая круг­лая скоб­ка b минус a пра­вая круг­лая скоб­ка де­лит­ся на N. По усло­вию 0 мень­ше |b минус a| мень­ше N и, зна­чит, b минус a не де­лит­ся на N. Тогда 2|b минус a|=N и число N четно.

Пусть N=2 n и a мень­ше b. Тогда 1 мень­ше или равно a мень­ше b мень­ше или равно 2 n и b=a плюс n . Возь­мем a=n. Тогда  левая круг­лая скоб­ка k плюс n пра­вая круг­лая скоб­ка левая круг­лая скоб­ка k плюс 2 n пра­вая круг­лая скоб­ка долж­но де­лить­ся на

 s=k левая круг­лая скоб­ка 2 n минус 2 пра­вая круг­лая скоб­ка плюс n левая круг­лая скоб­ка 2 n плюс 1 пра­вая круг­лая скоб­ка минус a минус b= левая круг­лая скоб­ка k плюс n пра­вая круг­лая скоб­ка левая круг­лая скоб­ка 2 n минус 2 пра­вая круг­лая скоб­ка .

То есть k плюс 2 n долж­но де­лить­ся на 2 n минус 2 . Это бы­ва­ет, когда k=2 n плюс левая круг­лая скоб­ка 2 n минус 2 пра­вая круг­лая скоб­ка m . Стало быть, все чет­ные N под­хо­дят.

Ре­ше­ние 2. Пусть N=2 n. Рас­смот­рим блок, со­сто­я­щий из чисел k минус n, k минус n плюс 1,\ldots,  k плюс n минус 1 . Их сумма равна 2 n k минус n, а сумма всех этих чисел, кроме k и k минус n, равна 2 левая круг­лая скоб­ка n минус 1 пра­вая круг­лая скоб­ка k. Тогда число k левая круг­лая скоб­ка k минус n пра­вая круг­лая скоб­ка де­лит­ся на 2 левая круг­лая скоб­ка n минус 1 пра­вая круг­лая скоб­ка k, если k минус n де­лит­ся на 2 левая круг­лая скоб­ка n минус 1 пра­вая круг­лая скоб­ка . Это вы­пол­не­но при k=2 m левая круг­лая скоб­ка n минус 1 пра­вая круг­лая скоб­ка плюс n при любом на­ту­раль­ном m. Таким об­ра­зом, для чет­но­го N мы по­стро­и­ли бес­ко­неч­но много хо­ро­ших бло­ков.

По­ка­жем те­перь, что для N=2 n плюс 1 су­ще­ству­ет лишь ко­неч­ное число хо­ро­ших бло­ков из N чисел. Пусть блок k минус n, k минус n плюс 1, k минус n плюс 2, \ldots,  k плюс n ока­зал­ся хо­ро­шим. Мы убе­дим­ся, что при до­ста­точ­но боль­ших k это не­воз­мож­но. Сумма всех чисел этого блока равна  левая круг­лая скоб­ка 2 n плюс 1 пра­вая круг­лая скоб­ка k . Пред­по­ло­жим, что про­из­ве­де­ние чисел k плюс r_1 и k плюс r_2 (|r|,|r_2| мень­ше или равно n. и r_1 не равно q r_2 пра­вая круг­лая скоб­ка де­лит­ся на сумму остав­ших­ся чисел блока. Тогда число

A = дробь: чис­ли­тель: левая круг­лая скоб­ка k плюс r_1 пра­вая круг­лая скоб­ка левая круг­лая скоб­ка k плюс r_2 пра­вая круг­лая скоб­ка , зна­ме­на­тель: левая круг­лая скоб­ка 2 n плюс 1 пра­вая круг­лая скоб­ка k минус левая круг­лая скоб­ка k плюс r_1 пра­вая круг­лая скоб­ка минус левая круг­лая скоб­ка k плюс r_2 пра­вая круг­лая скоб­ка конец дроби = дробь: чис­ли­тель: k в квад­ра­те плюс левая круг­лая скоб­ка r_1 плюс r_2 пра­вая круг­лая скоб­ка k плюс r_1 r_2, зна­ме­на­тель: левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k минус левая круг­лая скоб­ка r_1 плюс r_2 пра­вая круг­лая скоб­ка конец дроби = дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 n минус 1 конец дроби умно­жить на дробь: чис­ли­тель: k плюс r_1 плюс r_2 плюс \dfracr_1 r_2, зна­ме­на­тель: k конец дроби 1 минус \dfracr_1 плюс r_2 левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k

яв­ля­ет­ся на­ту­раль­ным. Зна­чит, число

 B= левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка A= дробь: чис­ли­тель: k плюс r_1 плюс r_2 плюс \dfracr_1 r_2, зна­ме­на­тель: k конец дроби 1 минус \dfracr_1 плюс r_2 левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k

тоже на­ту­раль­ное. Раз­бе­рем не­сколь­ко слу­ча­ев.

1)  Если r_1 плюс r_2=0 (при этом r_1 r_2 не равно q 0, так как r_1 не равно q r_2 пра­вая круг­лая скоб­ка , то уже при k боль­ше n в квад­ра­те число B=k плюс дробь: чис­ли­тель: r_1 r_2, зна­ме­на­тель: k конец дроби не­це­лое.

2)  Пусть r_1 плюс r_2=2 n минус 1 . При наших огра­ни­че­ни­ях на r_1, r_2 это воз­мож­но, лишь при  левая фи­гур­ная скоб­ка r_1, r_2 пра­вая фи­гур­ная скоб­ка = левая фи­гур­ная скоб­ка n минус 1, n пра­вая фи­гур­ная скоб­ка , тогда r_1 r_2=n в квад­ра­те минус n и

 B= дробь: чис­ли­тель: k в квад­ра­те плюс левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k плюс n в квад­ра­те минус n, зна­ме­на­тель: k минус 1 конец дроби .

По мо­ду­лю k минус 1 чис­ли­тель дроби равен 1 плюс левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка плюс n в квад­ра­те минус n= =n в квад­ра­те плюс n . При боль­ших k это не­ну­ле­вой оста­ток по мо­ду­лю k минус 1, и, зна­чит, число B не­це­лое.

3)  Пусть r_1 плюс r_2= минус левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка . Тогда ана­ло­гич­но  левая фи­гур­ная скоб­ка r_1, r_2 пра­вая фи­гур­ная скоб­ка = левая фи­гур­ная скоб­ка минус n плюс 1, минус n пра­вая фи­гур­ная скоб­ка ,  r_1 r_2=n в квад­ра­те минус n и

 B= дробь: чис­ли­тель: k в квад­ра­те минус левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k плюс n в квад­ра­те минус n, зна­ме­на­тель: k плюс 1 конец дроби .

По мо­ду­лю k плюс 1 чис­ли­тель дроби равен

1 плюс левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка плюс n в квад­ра­те минус n=n в квад­ра­те плюс n .

При боль­ших k это не­ну­ле­вой оста­ток по мо­ду­лю k плюс 1, и, зна­чит, число B опять не­це­лое.

4)  Пусть r_1 плюс r_2 не равно q 0, r_1 плюс r_2 не равно q \pm левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка . В сле­ду­ю­щих рас­суж­де­ни­ях мы вос­поль­зу­ем­ся тем, что при боль­ших k зна­ме­на­тель дроби, за­да­ю­щей число B, очень бли­зок к 1. За­ме­тим, что при |x| мень­ше дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби

 0 мень­ше или равно дробь: чис­ли­тель: 1, зна­ме­на­тель: 1 минус x конец дроби минус 1 минус x= дробь: чис­ли­тель: x в квад­ра­те , зна­ме­на­тель: 1 минус x конец дроби мень­ше или равно 2 x в квад­ра­те .

Взяв x= дробь: чис­ли­тель: r_1 плюс r_2, зна­ме­на­тель: левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k конец дроби , по­лу­ча­ем

 0 мень­ше или равно дробь: чис­ли­тель: 1, зна­ме­на­тель: 1 минус \dfracr_1 плюс r_2 левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k конец дроби минус 1 минус дробь: чис­ли­тель: r_1 плюс r_2, зна­ме­на­тель: левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k конец дроби мень­ше или равно дробь: чис­ли­тель: 2 левая круг­лая скоб­ка r_1 плюс r_2 пра­вая круг­лая скоб­ка в квад­ра­те , зна­ме­на­тель: левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка в квад­ра­те k в квад­ра­те конец дроби мень­ше или равно \dfrac2k в квад­ра­те .

Сле­до­ва­тель­но, для не­ко­то­ро­го 0 мень­ше или равно \varepsilon мень­ше или равно 1:

 дробь: чис­ли­тель: 1, зна­ме­на­тель: 1 минус \dfracr_1 плюс r_2 левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k конец дроби =1 плюс дробь: чис­ли­тель: r_1 плюс r_2, зна­ме­на­тель: левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k конец дроби плюс дробь: чис­ли­тель: 2 \varepsilon, зна­ме­на­тель: k в квад­ра­те конец дроби \text .

Под­ста­вим это ра­вен­ство в вы­ра­же­ние для B:

B= левая круг­лая скоб­ка k плюс r_1. плюс r_2 плюс дробь: чис­ли­тель: r_1 r_2, зна­ме­на­тель: k конец дроби пра­вая круг­лая скоб­ка левая круг­лая скоб­ка 1 плюс дробь: чис­ли­тель: r_1 плюс r_2, зна­ме­на­тель: левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k конец дроби плюс дробь: чис­ли­тель: 2 \varepsilon, зна­ме­на­тель: k в квад­ра­те конец дроби пра­вая круг­лая скоб­ка =k плюс r_1 плюс r_2 плюс дробь: чис­ли­тель: r_1 плюс r_2, зна­ме­на­тель: 2 n минус 1 конец дроби плюс дробь: чис­ли­тель: r_1 r_2, зна­ме­на­тель: k конец дроби плюс дробь: чис­ли­тель: левая круг­лая скоб­ка r_1 плюс r_2 пра­вая круг­лая скоб­ка в квад­ра­те , зна­ме­на­тель: левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k конец дроби плюс

 дробь: чис­ли­тель: 2 \varepsilon, зна­ме­на­тель: k конец дроби плюс дробь: чис­ли­тель: 2 \varepsilon левая круг­лая скоб­ка r_1 плюс r_2 пра­вая круг­лая скоб­ка , зна­ме­на­тель: k в квад­ра­те конец дроби плюс дробь: чис­ли­тель: левая круг­лая скоб­ка r_1 плюс r_2 пра­вая круг­лая скоб­ка r_1 r_2, зна­ме­на­тель: левая круг­лая скоб­ка 2 n минус 1 пра­вая круг­лая скоб­ка k в квад­ра­те конец дроби плюс дробь: чис­ли­тель: 2 \varepsilon левая круг­лая скоб­ка r_1 плюс r_2 пра­вая круг­лая скоб­ка r_1 r_2, зна­ме­на­тель: k в кубе конец дроби .

Рас­смот­рим сла­га­е­мые, на­чи­ная с пя­то­го. Вое их чис­ли­те­ли огра­ни­че­ны по мо­ду­лю, на­при­мер, чис­лом 10 n в кубе , а зна­ме­на­те­ли не мень­ше чем k. По­это­му при k боль­ше 60 n в сте­пе­ни левая круг­лая скоб­ка 5 пра­вая круг­лая скоб­ка их сумма мень­ше  дробь: чис­ли­тель: 1, зна­ме­на­тель: n в квад­ра­те конец дроби .

Это озна­ча­ет, что число

k плюс r_1 плюс r_2 плюс дробь: чис­ли­тель: r_1 плюс r_2, зна­ме­на­тель: 2 n минус 1 конец дроби

от­ли­ча­ет­ся от це­ло­го числа B менее чем на  дробь: чис­ли­тель: 1, зна­ме­на­тель: n в квад­ра­те конец дроби . Но это не­воз­мож­но, по­сколь­ку оно не­це­лое со зна­ме­на­те­лем, не пре­вос­хо­дя­щим 2 n минус 1, и, зна­чит, от­ли­ча­ет­ся от це­ло­го числа не менее чем на  дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 n минус 1 конец дроби .

До­ка­жи­те, что при N=2 n и боль­ших k лишь про­из­ве­де­ние чисел k плюс 1 и k плюс n плюс 1 или про­из­ве­де­ние чисел k плюс n и k плюс 2 n может де­лить­ся на сумму остав­ших­ся.

 

Ответ: для всех чет­ных N боль­ше или равно 4.