Дана последовательность длины 100, состоящая из нулей и единиц. Несколько цифр, стоящих подряд (возможно, одна), образуют подпалиндром, если последовательность этих цифр одинаково читается от начала к концу и от конца к началу. Какое наименьшее количество подпалиндромов может быть в последовательности?

их вроде лазером выжигают. говорят болезненная процедура.

(0) один :)

(2) ну сотка-то по-любому будет)

Дык... один наверное :)

(4) каждая цифра сама себе подпалиндром, так что их точно больше чем 1;)

(5) Вопрос заключается в том, какое НАИМЕНЬШЕЕ количество.

(0) Вопрос не совсем ясен. Мне кажется один.
Например, последовательность из 100 единиц. Или из 100 нулей.

(7) +1 И нужно ли считать подпалиндромы внутри других подпалиндромо, или могут ли пересекаться подпалиндромы.

(7) В последовательности из 100 одинаковых символов 100 подпалиндромов, начиная от 1, 11 , 111 и т.д.

(0) Надо считать каждый подпалиндром или только уникальные?

(10) Каждый

(11)+ таким образом в (9) описаны 100 однобуквенных+ 99двубуквенных+...+1 стобуквенный подпалиндром = 5500штук.
очевидно, что это и есть максимум 5500/из 5500 возможных.
а в задаче спрашивается, каков минимум (?)/из 5500

Кому не слабо написать регулярку для поиска подпалиндромов?:)

(13) регулярки с палиндромами ЗаранееНеИзвестноКакойДлины вроде не дружат)

имхо, 198, но пока доказать не могу

Если в комнате загорелась бумага в корзинке и имеется ведро песка:
- химик засыплет огонь песком
- физик осыплет очаг вокруг и станет наблюдать за процессом
- лишь математик сразу понимает что задача имеет решение и теряет к ней интерес...

(15) Задача именно на доказательство. Предсказать - это прогноз погоды))

(15) отгадал) осталась оценка и пример)

(18)100111000011111.....  такой ряд?

(19) таких рядов может быть много, если не лень, напиши программку-проверяйку)

+19 ошибочка. для такого ряда 575 получается.

(20) А математически не решается задача?

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
    string s="1001110000111110000001111111000000001111111110000000001111111111000000000001111111111110000000000000";
//1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";    
    int a[100][100];
    int n = s.length();
    cout<<n<<endl;
        for(int i = 0; i < n; i++)
            a[i][i] = true;
        int res = n;

        
        for(int l = 2; l <= n; l++)
        for(int i = 0; i + l - 1 < n; i++)
        {    
            if((s[i] == s[i+l-1]) && ((l == 2) || (a[i+1][i+l-2])))
            {
                a[i][i+l-1] = true;    
                res ++;
            }
        }
        cout << res<<endl;
   return 0;
}

если нет компилятора запускаем тут

http://www.tutorialspoint.com/compile_cpp_online.php

(22) ну она же в секции математика, а не одинэсинг, значит решается)

Процедура КнопкаВыполнитьНажатие(Кнопка)  
    Мин = 1000000;
    ГСЧ = Новый ГенераторСлучайныхЧисел;
    
    Пока Истина Цикл
        Стр = "1";
        Для Сч = 1 По 99 Цикл
            Если ГСЧ.СлучайноеЧисло(0, 1) = 0 Тогда
                Стр = Стр + "0";
            Иначе
                Стр = Стр + "1";
            КонецЕсли;     
        КонецЦикла;
        Пал = ЧислоПалиндромов(Стр);
        
        Если Пал < Мин Тогда
            Мин = Пал;
            Стр2 = ТабличноеПоле1.Добавить();
            Стр2.Число = Стр;
            Стр2.Полиндромы = Пал;
            Сообщить(Стр+"___"+Пал);
        КонецЕсли;
        
        ОбработкаПрерыванияПользователя();
    КонецЦикла;
КонецПроцедуры


Функция ЧислоПалиндромов(Знач Строка)
    Кол = СтрДлина(Строка);
    
    Длина = СтрДлина(Строка);    
    Для Сч = 2 По Длина Цикл
        Для Сч2 = 1 По Длина - Сч + 1  Цикл
            Если ЭтоПалиндром(Сред(Строка, Сч2, Сч)) Тогда
                Кол = Кол + 1;    
            КонецЕсли;     
        КонецЦикла;     
    КонецЦикла;    
    Возврат Кол;
КонецФункции

Функция ЭтоПалиндром(Знач Строка)
    Длина = СтрДлина(Строка);    
    Для Сч = 1 По Цел(Длина/2) Цикл
        Если Сред(Строка, Сч, 1) <> Сред(Строка, Длина+1-Сч, 1) Тогда
            Возврат Ложь;    
        КонецЕсли;     
    КонецЦикла;     
    Возврат Истина;
КонецФункции

Пока нашёл 248)
Для строки 1011001000101110101111000101101011001011001000110101000011000101011001010001100101011011001111011110

пример нашелся, периодическая последовательность с периодом:
010011
очевидно, если есть подпалиндром длины N, то есть и длины N-2, но перебором видно, что ни длины 5, ни длины 6 подпалиндромов нет
Для каждого элемента есть единственный подпалиндром длины больше 1, начинающийся с этого элемента, за исключением 98-го и 100-го

осталось доказать, что меньше нельзя

(27) для 0100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100
получается 210 подпалиндромов

(28) выведи на экран подпалиндромы, врет твоя программа

(29) Вроде "0", "1", "00", "11", "101", "010", "1001" и "0110"

(30) не только
вот это оно посчитало палиндромом "010011010"

(31) Ну я же сам искал, а не через ПО ;-)

(32) ну и сколько нашел?

(33) Для 0100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100
"0" - 51
"1" - 49
"00" - 17
"11" - 16
"010" - 17
"101" - 16
"0110" - 16
"1001" - 16
Итого: 198

Для слова длины N имеется не менее 2*(N-1) подпалиндромов

Доказательство

Для любого элемента "достаточно далекого от конца" верно одно из двух:
1. Есть подпалиндром длины от 2 до 4, начинающийся с этого элемента
2. Этот элемент является началом слова "0111"/"1000"
(но в этом случае количество подпалиндромов длины более 1, начинающихся с первых трехсимволов есть три). Выгоды нет

Понятно, что это неверно для последнего элемента

Перебором устанавливается, что это может быть неверно для ТОЛЬКО ОДНОГО из 2,3,4 по счету с конца элемента

Как-то так

Четко, что сказать)
Ждём ТС с его решением)

Все проще.
Элемент является началом подпалиндрома длины больше 1 тогда и только тогда, когда правее него есть равный ему элемент.
Для слова длины N таких элементов N-2
Значит всего подпалиндромов N+N-2

(37) точнее не меньше

А если в слове три символа встречаются: 0,1,2?

(39) тогда можно сделать только одинарные:
012012012...

авторское решение
Ответ. 2n–2. Решение. Оценка. Индукция по числу символов. При n = 2 палиндромов хотя бы два – каждый из символов. При n = 3 – хотя бы четыре: три символа и одна из конфигураций aa или aba. Пусть уже доказано, что при n = k (k ? 3) палиндромов не меньше, чем 2k–2. Добавим справа символ a. Он сам по себе палиндром, и если в последовательности, к которой мы его дописали, есть хотя бы одна буква a, то добавился ещё палиндром вида ab…ba; в противном случае та последовательность состояла из k букв b, и в ней было не менее, чем k+(k–1)+…+1 = k(k+1)/2 ? 2k палиндромов. Как видим, в обоих случаях палиндромов будет не меньше, чем 2(k+1)–2 = 2k. Пример. Рассмотрим последовательность 100110100110… (период 6). Примером для любого k служит её начальный отрезок длины k. В самом деле, в отрезке 10 два палиндрома, в отрезке 100 – четыре палиндрома, а далее перебором шести случаев нетрудно убедиться, что добавление каждого следующего знака увеличивает количество палиндромов ровно на два.

(41) В доказательстве по индукции строится новая последовательность длиной k+1 с минимальным количеством подполиндромов, путем добавления символа к последовательности длиной k с минимальным количестаом подполиндромов.
Однако я не нахожу очевидным это, что последовательность длиной k+1 содержит в себе последовательность длиной k.

(42) ЛЮБОЕ слово длины k содержит не менее 2*(k-1) палиндрома, это предположение индукции
Добавление к любому слову длины k еще одного символа увеличивает число палиндромов не менее чем на 2, это шаг индукции