Да се намери най-голямото n...

[rashi101]

Да се намери най-голямото [tex]n[/tex], за което съществува множество {[tex]a_1,a_2,...,a_n[/tex]} от естествени числа със следните свойства:
1) числата [tex]a_i[/tex] са съставни
2) всеки две от тези числа са взаимно прости
3) [tex]1< a_i \le (3n+1)^2[/tex] за [tex]i=1,2,...,n[/tex].

Имам някакви подозрения, че n=12 е решението, но не мога да докажа.

[mkmarinov]

Ясно е защо "добрият" случай е да вземем редицата да е съставена от квадратите на простите числа (доказателство - по индукция). Максималният елемент тогава е [tex]p_n^2[/tex] (където [tex]p_n[/tex] е n-тото просто число) - искаме [tex]p_n^2 \le (3n+1)^2 <=> p_n \le 3n+1[/tex]. И търсим най-голямото число което удовлетворява неравенството - на мен ми изглежда, че е 14 .
Относно доказателството, че това е максималното число - едва ли има красиво и кратко доказателство, което е елементарно.

[rashi101]

Да, проверих само до 13 :)

Просто идея. Тъй като [tex]3n+1[/tex] нараства с 3 с всякo следващо n, по-късно може да се получи по-голямо [tex]a_n=p_n^2[/tex], което да удовлетворява условието, само ако имаме достатъчно много случаи на [tex]p_k=p_{k-1}+2[/tex], [tex]k<n[/tex]. Това не би трябвало да се случва, защото ако [tex]p_k[/tex] и [tex]p_k+2[/tex] са прости, то [tex]p_k+1[/tex] се дели на три, [tex]p_k+4[/tex] също, [tex]p_k+5[/tex] е четно, значи следващото просто би могло да бъде не по-малко от [tex]p_k+6[/tex]. Значи каквото "предимство" сме спечелили, непременно ще го загубим. И тъй като по-късно разликата между [tex]p_n[/tex] и [tex]3n+3[/tex] става по-голяма от 2, тя никога не може да бъде преодоляна. Никаква представа си нямам как бих могла да запиша това обаче!

[mkmarinov]

Да, с елементарна математика ще е нещо подобно.

Нека разгледаме 20 поредни числа, за удобство по-големи от 40:
10 от тях са четни.
2 от тях се делят на 5 и са нечетни
6 се делят на 3. Половината от тях са нечетни. От тази половина най-много едно число се дели на 5, т.е. имаме 2 числа, които се делят на и не спадат в горните 2 групи.

Получихме, че от произволни 20 поредни числа, най-много 6 са прости.
Разглеждаме редиците [tex]p_n[/tex] и [tex]b_n=3n+1[/tex].
За всяко n>14: [tex]p_{n+6} \ge p_n+20[/tex], а [tex]b_{n+6}=b_n+18[/tex]
От това, че [tex]p_n > b_n (15 \le n \le 21)[/tex] и горните неравенства следва, че [tex]p_n > b_n \forall n \ge 15[/tex], което решава задачата.

[rashi101]

Страхотно :) Благодаря.