2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 палиндромы
Сообщение12.12.2006, 01:43 
Заслуженный участник
Аватара пользователя


09/10/05
1142
Здравстуйте!

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

Есть такии числа, которые если читать их справо налево равны cами себе (например 363, 97179 или просто 3).
Допустим число $$P(N)$$ задаёт общее количесто таких палиндромов до какого-то числа $$N$$ (например, до числа 11 можно найти 10 палиндромов).
Попытайтесь вывести общую формулу $$P(N)$$ для любого $$N$$ и докажите, что всегда верно неравенство $$P(N) > 2 \sqrt{N} -3$$

 Профиль  
                  
 
 
Сообщение12.12.2006, 02:53 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение13.12.2006, 00:30 
Модератор
Аватара пользователя


11/01/06
5710
Пусть $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.$$

 Профиль  
                  
 
 
Сообщение13.12.2006, 01:39 
Заслуженный участник
Аватара пользователя


09/10/05
1142
Я пока не буду давать полный ответ и лишь наведу на несколько мыслей. Во первых, надо различать между числами $$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 секунд:

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

 Профиль  
                  
 
 
Сообщение13.12.2006, 02:22 
Модератор
Аватара пользователя


11/01/06
5710
Зачем огород городить?
Неравенство $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.$

 Профиль  
                  
 
 
Сообщение13.12.2006, 02:26 
Заслуженный участник
Аватара пользователя


09/10/05
1142
maxal

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

 Профиль  
                  
 
 
Сообщение13.12.2006, 04:53 
Модератор
Аватара пользователя


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

Добавлено спустя 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$ получается сразу.

 Профиль  
                  
 
 
Сообщение14.12.2006, 10:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение14.12.2006, 13:14 
Заслуженный участник
Аватара пользователя


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


Так это-же ясно, что их надо объединять! :wink: Дело в том, что например для числа $1500$ - рассматриваем все палиндромы, но поэтому разбиваме их на "классы":
Классы будут различаться по количеству цифр в числах- кандидатах. Вот пример:
для чисел с 1 цифрой (нечётные палиндромы): $$1,2,3,4,5,...,9$$
2 (чётные): $$11,22,....,99$$
3 (нечётные): $$101,111,...,353,...797,...,989,999$$
4 (чётные): $$1001,...,1441$$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group