палиндромы

[Capella]

Здравстуйте!

Вроде такая задача ещё не предлагалась.

Есть такии числа, которые если читать их справо налево равны cами себе (например 363, 97179 или просто 3).
Допустим число

$$P(N)$$

задаёт общее количесто таких палиндромов до какого-то числа

$$N$$

(например, до числа 11 можно найти 10 палиндромов).
Попытайтесь вывести общую формулу

$$P(N)$$

для любого

$$N$$

и докажите, что всегда верно неравенство

$$P(N) > 2 \sqrt{N} -3$$

[Genrih]

Остается считать.
для $n=10^k$ , $k$-натурально ,
$P(n)=2*10^{\frac k 2}-2$ при четном k
$P(n)=11*10^{\frac {k-1}{2}}-2$ при нечетном k , что легко доказать по индукции.

дальше думаем ...

[maxal]

Пусть $10^{2k-1}\leq N < 10^{2k+1}.$ Тогда

$$P(N) \geq \left\lfloor\frac{N}{10^k}\right\rfloor - 10^{k-1} + P(10^{2k-1}) = \left\lfloor\frac{N}{10^k}\right\rfloor + 10^{k} - 2 > \frac{N}{10^k} + 10^{k} - 3.$$

Пользуясь неравенством о средних, имеем

$$P(N) > 2\sqrt{N} - 3.$$

[Capella]

Я пока не буду давать полный ответ и лишь наведу на несколько мыслей. Во первых, надо различать между числами

$$N$$

, которые имеют чётное и нечётное количество цифр в себе.
с чётными всё понятно:

$$10^k - 1$$

Далее для палиндромов с чётным количеством цифр Вы приводите очень хорошу формулу

$$ \left\lfloor\frac{N}{10^k}\right\rfloor $$

(только здесь тоже надо отнять 1). Но здесь есть один фокус! Возьмём два числа: $1507$ и $1577$. $k=2$ и для обоих чисел мы получаем $15$, но это не совсем верно. Суть в том, что в первом множестве будет отсутствовать палиндром $1551$, а во втором (у $1577$) он присутствует. Поэтому надо изобрести некоторый остаточный член $R$, который бы выдавал например $1$ для второго случая и $0$ для первого.
Далее лучше сделать общую степень для нечётных и чётных палиндромов. Например, это можно достигнуть тем-же округлением

$$ n = 2k, n= 2k +1 \to \left\lfloor\frac{n}{2}\right\rfloor = k$$

.
А теперь надо только расписать оба случая. Можно предcтавить как сумму всех случаев.

$$P(N) = 10^{ \left\lfloor\frac{n}{2}\right\rfloor} + \left\lfloor\frac{N}{10^{\left\lfloor\frac{n}{2}\right\rfloor} }\right\rfloor - 2 + R$$

Добавлено спустя 1 час 7 минут 28 секунд:

Вот, а теперь имея готовую формулу осталось разрулить с неравенством

[maxal]

Зачем огород городить?
Неравенство $P(N) \geq 2\sqrt{N} - 3$ я доказал, причем непосредственно из доказательства следует, что равенство может достигаться, только если $\frac{N}{10^k}=10^k,$ то есть $N=10^{2k}.$ Но как Genrih справедливо заметил, $P(10^{2k})=2\cdot 10^{k} - 2>2\sqrt{10^{2k}} - 3.$ Поэтому для всех $N$ имеем $P(N)>2\sqrt{N} - 3.$

[Capella]

maxal

Да, но неравенство будет строгим, а у Вас оно выходит не строгое. Если хотите, я могу выложить и решение неравенства тоже... Или лучше Вам расписать Ваш вариант со всеми промежуточными шагами.

[maxal]

Перечитайте еще раз мое предыдущее сообщение. Там показано как из нестрого неравенства следует строгое.

Добавлено спустя 8 минут 41 секунду:

Точная формула для $P(N)$ получается из неравенства:

$$\left\lfloor\frac{N}{10^k}\right\rfloor - 10^{k-1} + P(10^{2k-1}) \leq P(N) \leq \left\lfloor\frac{N}{10^k}\right\rfloor - 10^{k-1} + P(10^{2k-1}) + 1.$$

Причем верхняя грань достигается, только $k$ последних цифр числа $N$ образуют число не меньшее числа, образованного первыми $k$ цифрами в обратном порядке; в остальных случаях $P(N)$ равна нижней грани.

Добавлено спустя 19 минут 7 секунд:

Я исправил исходное доказательство. Теперь неравенство $P(N)>2\sqrt{N}-3$ получается сразу.

[Genrih]

Capella, я только сейчас понял что значит "общая формула" -- объединить мою писанину для четного и нечетного... неинтересно
Задача чисто вычислительная и скорее интересна олимпиадникам - программистам (я одному показал формулку -- он вскрикнул от радости)

[Capella]

Genrih писал(а):

Capella, я только сейчас понял что значит "общая формула" -- объединить мою писанину для четного и нечетного... неинтересно
Задача чисто вычислительная и скорее интересна олимпиадникам - программистам (я одному показал формулку -- он вскрикнул от радости)

Так это-же ясно, что их надо объединять! Дело в том, что например для числа $1500$ - рассматриваем все палиндромы, но поэтому разбиваме их на "классы":
Классы будут различаться по количеству цифр в числах- кандидатах. Вот пример:
для чисел с 1 цифрой (нечётные палиндромы):

$$1,2,3,4,5,...,9$$

2 (чётные):

$$11,22,....,99$$

3 (нечётные):

$$101,111,...,353,...797,...,989,999$$

4 (чётные):

$$1001,...,1441$$

Как видите, в общем случае мы должны рассматривать сумму чётных с нечётными. Поэтому и надо рассматривать сумму для неравенства, а не брать чётные и нечётные по отдельности.