[Архив!] Чистая математика, физика, химия и т.п.: задачки для тренировки мозгов, никак не связанные с торговлей - страница 460

Новый комментарий
 

MetaDriver: (пост от 16.01.2011 04:14)

2011.01.16 03:41:44 MetaSage (EURUSD,H1) Тест =>..... и т.д. Все остальные варианты false, ибо чётные.
2011.01.16 03:41:40 MetaSage (EURUSD,H1) Тест => 2+888=890 false
2011.01.16 03:40:02 MetaSage (EURUSD,H1) Тест => 111+16=127 true
2011.01.16 03:39:23 MetaSage (EURUSD,H1) Тест => 3+592=595 false
2011.01.16 03:38:08 MetaSage (EURUSD,H1) Тест => 37+48=85 false
2011.01.16 03:38:08 MetaSage (EURUSD,H1) S=127; P=1776; a=16; b=111

S=127, P=1776 (числа - 16 и 111) не может быть решением.

А: (1776=16*3*37.) Не знаю.

Б: (127 = 2+нечетное_составное.) Я и без тебя знал.

А: (Значит, сумма - это 2+нечетное_составное. 1776 = 16*111 = 48*37 = 592*3. Суммы - 127, 85, 595. Подходит только выделенная с раложением 16*111.) Знаю числа.

Б: (Здесь укажу только два варианта полного перебора, которых достаточно:

127=2+125. П(=2*5*5*5) = 2*125 = 10*25 = 50*5. Суммы - 127, 35, 55. Допустима только одна - выделенная. Сумма 35 недопустима, т.к. 35=4+31=16+19=32+3 (неоднозначное представление суммой степени двойки и простого). Кандидат (числа - 2 и 125).

127=16+111. П(=16*3*37) = 16*111 = 48*37 = 592*3. Суммы - 127, 85, 595. Аналогично. Кандидат (числа - 16 и 111). ) Не знаю.

___________________________________

Утешение для тебя - непредставимость 127 в виде суммы степени двойки и простого. Таких чисел не очень много, но они не слишком редкие.


Проверяем S=373; P=19776; a=64; b=309. Это второй вариант твоего решения с составным нечетным числом, в котором я сомневался.

Первые две реплики проходят. Третья:

А: (19776(=64*3*103) = 64*309 = 192*103 = 6592*3. Суммы - 373, 295, 6595. Подходит только выделенная. Последняя сумма, кстати, не входит в допустимые даже при снятии ограничений на суммы. Итак, 64 и 309.) Знаю числа.

Дальше пока не сообразил. Но, переходя к последним выкладкам Б, мы уже знаем, что одно разбиение суммы 373=64+309 мы уже проверили и имеем первого кандидата.

P.S. Попробуем угадать (достаточно найти один другой пример с единственной подходящей суммой):

Б: 373 = 32+341. П(=32*11*31) = 32*341 = 352*31 = 992*11. Суммы - 373, 383, 1003. Подходит только выделенная. Обе другие - нет, но по более тонкой причине: каждая из них неоднозначно раскладывается на сумму степени двойки и простого. Об этом дополнительном фильтре я уже писал тут. Итак, у нас еще один кандидат на пару задуманных чисел - 32 и 341. Следовательно, мудрец Б не сможет вычислить пару загаданных.

 

MD, судя по листингу, ты проверяешь только одно произведение на возможные разложения. Т.е. выполняешь работу мудреца А.

А как же работа Б перед его последней репликой? Напоминаю, в чем заключаются его рассуждения. Пусть это вариант S=373; P=19776; a=64; b=309.

У мудреца Б есть только сумма, которую ему дали, - 373. И есть информация о том, что А, воспользовавшись предыдущей наводкой Б, убедился, что произведение 19776=64*3*103 среди всех вариантов разложения на 2 множителя имеет единственную допустимую сумму. Мудрецу А почти не пришлось работать, т.к. ему было достаточно проверить всего три варианта. Что теперь делает Б?

Ему надо перебрать все разбиения 373 на 2 слагаемых. Это 2+371, 3+370, 4+369, ... 186+187. Всего-то 185 вариантов.

Для каждого варианта он должен перемножить слагаемые, а далее сделать то, что делал А ранее. Вот, например, вариант 134+239.

1. Вычисляем произведение (P=2*67*239).

2. Перебираем варианты группировки - 2*16013, 67*478, 134*239.

3. Вычисляем соответствующие суммы - 16015, 545, 373.

4. Допустимы 2 суммы - 545, 373. Следовательно, вариант "134+239" отбрасываиццо.

Это был только один вариант. Далее ему надо перебирать следующие по списку.

И только тогда, когда среди всех этих 185 вариантов у него будет только один с единственной допустимой суммой, он может говорить свою реплику. (Примечание: проверив вариант "32+341" и увидев, что там единственная допустимая сумма, он не может остановиться и заявить, что знает числа. Ему придется идти до конца и проверять, возможно, все остальные: а вдруг найдутся еще варианты с одной допустимой?)

До сих пор я нашел в сети только одно более-менее строгое рассуждение. Автор - Константин Кноп. Оно тут. Рассуждения немного сложнее, чем у меня, но для ограничения "сумма менее 100" он строго доводит его до конца. Однако для сумм с большими ограничениями у него только несколько гипотез. И тоже апелляция к компутеру...

 
Mathemat:

MD, судя по листингу, ты проверяешь только одно произведение на возможные разложения. Т.е. выполняешь работу мудреца А.

А как же работа Б перед его последней репликой? Напоминаю, в чем заключаются его рассуждения. Пусть это вариант S=373; P=19776; a=64; b=309.

У мудреца Б есть только сумма, которую ему дали, - 373. И есть информация о том, что А, воспользовавшись предыдущей наводкой Б, убедился, что произведение 19776=64*3*103 среди всех вариантов разложения на 2 множителя имеет единственную допустимую сумму. Мудрецу А почти не пришлось работать, т.к. ему было достаточно проверить всего три варианта. Что теперь делает Б?

Ему надо перебрать все разбиения 373 на 2 слагаемых. Это 2+371, 3+370, 4+369, ... 186+187. Всего-то 185 вариантов. // см. золотистый комментарий

Для каждого варианта он должен перемножить слагаемые, а далее сделать то, что делал А ранее. Вот, например, вариант 134+239.

1. Вычисляем произведение (P=2*67*239).

2. Перебираем варианты группировки - 2*16013, 67*478, 134*239.

3. Вычисляем соответствующие суммы - 16015, 545, 373.

4. Допустимы 2 суммы - 545, 373. Следовательно, вариант "134+239" отбрасываиццо.

Это был только один вариант. Далее ему надо перебирать следующие по списку.

И только тогда, когда среди всех этих 185 вариантов у него будет только один с единственной допустимой суммой, он может говорить свою реплику. (Примечание: проверив вариант "32+341" и увидев, что там единственная допустимая сумма, он не может остановиться и заявить, что знает числа. Ему придется идти до конца и проверять, возможно, все остальные: а вдруг найдутся еще варианты с одной допустимой?)

До сих пор я нашел в сети только одно более-менее строгое рассуждение. Автор - Константин Кноп. Оно тут. Рассуждения немного сложнее, чем у меня, но для ограничения "сумма менее 100" он строго доводит его до конца. Однако для сумм с большими ограничениями у него только несколько гипотез. И тоже апелляция к компутеру...

Вапчета не так. Вот основная процедура проверки (см. ниже). Она отрабатывает сразу справедливость третьей (А) и четвёртой (В) реплики.

Внешний цикл проверяет справедливость реплики 4 (если переменная Count в конце большого цикла == 1)

Внутренний цикл проверяет справедливость реплики 3 (если переменная сount в конце внутреннего цикла == 1)

См. зелёные комментарии в тексте ниже.

   uint GetCountValidSum(uint n,uint &P,uint &a,uint &b)
     {
      uint Count=0;
      //       for(uint i=2;i<=sqrt(n);i++)  // ОШИБКА!! 
      for(uint i=2;i<n/2;i++) // Правильно так.                  // Внешний цикл
                                                         // проверяет все разбиения суммы на 2 слагаемых. 
         {
         uint count=0;
         sMX J;
         J.Join(MX[i],MX[n-i]); // объединяем множители слагаемых // 1. Вычисляем произведение (P=2*67*239). 
         for(uint j=1; j<=J.GetCountAllSums(); j++)              // Внутренний цикл
                                                      // 2. Перебираем варианты группировки - 2*16013, 67*478, 134*239. 
            count+=IsValidSum(J,j); // j - номер суммы      // 3. Вычисляем соответствующие суммы - 16015, 545, 373. 
         if(count==1)  // это условие истинно только если для конкретного набора множителей существует только одна валидная сумма
           {           // т.е. если это так - мудрец А сможет однозначно определить числа
            Count++;
            P=J.Value();
            a=i;
            b=n-i;
           }
        }
      return Count;  // А вот если таких произведений, для которых мудрец А способен найти решение после второй реплики только одно
     }               // т.е. Count==1  тогда и мудрец В сможет однозначно найти решение

Как то так. :)

Красненьким скопировал твои выкладки в виде комментария в текст процедуры, дабы привязать к местности.


 
Mathemat:

S=127, P=1776 (числа - 16 и 111) не может быть решением.

А: (1776=16*3*37.) Не знаю.

Б: (127 = 2+нечетное_составное.) Я и без тебя знал.

А: (Значит, сумма - это 2+нечетное_составное. 1776 = 16*111 = 48*37 = 592*3. Суммы - 127, 85, 595. Подходит только выделенная с раложением 16*111.) Знаю числа.

Б: (Здесь укажу только два варианта полного перебора, которых достаточно:

127=2+125. П(=2*5*5*5) = 2*125 = 10*25 = 50*5. Суммы - 127, 35, 55. Допустима только одна - выделенная. Сумма 35 недопустима, т.к. 35=4+31=16+19=32+3 (неоднозначное представление суммой степени двойки и простого). Кандидат (числа - 2 и 125).

127=16+111. П(=16*3*37) = 16*111 = 48*37 = 592*3. Суммы - 127, 85, 595. Аналогично. Кандидат (числа - 16 и 111). ) Не знаю.

___________________________________

Утешение для тебя - непредставимость 127 в виде суммы степени двойки и простого. Таких чисел не очень много, но они не слишком редкие.


Проверяем S=373; P=19776; a=64; b=309. Это второй вариант твоего решения с составным нечетным числом, в котором я сомневался.

Первые две реплики проходят. Третья:

А: (19776(=64*3*103) = 64*309 = 192*103 = 6592*3. Суммы - 373, 295, 6595. Подходит только выделенная. Последняя сумма, кстати, не входит в допустимые даже при снятии ограничений на суммы. Итак, 64 и 309.) Знаю числа.

Дальше пока не сообразил. Но, переходя к последним выкладкам Б, мы уже знаем, что одно разбиение суммы 373=64+309 мы уже проверили и имеем первого кандидата.

P.S. Попробуем угадать (достаточно найти один другой пример с единственной подходящей суммой):

Б: 373 = 32+341. П(=32*11*31) = 32*341 = 352*31 = 992*11. Суммы - 373, 383, 1003. Подходит только выделенная. Обе другие - нет, но по более тонкой причине: каждая из них неоднозначно раскладывается на сумму степени двойки и простого. Об этом дополнительном фильтре я уже писал тут. Итак, у нас еще один кандидат на пару задуманных чисел - 32 и 341. Следовательно, мудрец Б не сможет вычислить пару загаданных.

Лёша, твой (а также Кноповский) критерий об однозначности разложения на сумму степени двойки и простого является недоказанной гипотезой.

То, что это часто справедливо - не является доказательством. Так что - либо доказательство в студию, либо тест полным перебором на компе. Второе предпочтительнее ибо не нуждается в доказательствах по факту предъявления. У меня оно тест не проходит.

Кстати, программа отлажена - сервисдеск нашёл таки ошибку. Оказалась моей (в процедуре проверки нужно было обнулить память перед сортировкой), я её поправил.

Прога в прицепе.

Файлы:
metasage_6.mq5  6 kb
 
MetaDriver:

Лёша, твой (а также Кноповский) критерий об однозначности разложения на сумму степени двойки и простого является недоказанной гипотезой.

Он не мой, я его у тебя подсмотрел :) Кратко формулируется так: если разложение неоднозначно (есть несколько способов), то сумма невалидна. Ты готов опровергнуть? Давай, жду пример.

Я уже разместил свой способ использования разложения на сумму степени двойки и простого. Там почти доказательства-то и нету, но есть практический способ использования наблюдения, обоснованный на все 100. Смотри выделенное зелененьким.

Копирую его сюда, чтобы щелкать по ссылкам не пришлось:

На самом деле есть более общее наблюдение (оно видно из распринтовки MD): вероятно, все разумные варианты ограничиваются парами чисел 2^n и p (простое). Я его не доказал, просто предполагаю.

Теперь, опираясь на это предположение, сделаем нечто реальное. Самое сложное в диалоге мудрецов - это последняя реплика. Именно она пока требует расматривать много вариантов. Давайте предположим, что три реплики у нас уже состоялись, и осталась только последняя. А много ли сумм из МДС могут быть представлены в виде 2^n + простое?

Почему именно такое разложение? Да просто потому, что Б в последней реплике, расматривая возможные разложения сумм (см. мой предыдущий пост) и соответствующие произведения, встретив произведение 2*...*2*простое, уже заранее знает, что из сумм для него только одна и может быть допустимой, т.к. только одна нечетна - если числа равны степени двойки и нечетному простому. Это сразу дает реального кандидата.

Итак, поехали.

11 = 2^2+7 = 2^3+3. Кандидатов - два. Облом сразу.

17 = 2^2+13. Больше таких представлений нет. Хороший кандидат.

23 = 2^2+19 = 2^4+7. Облом.

27 = 2^2+23 = 2^3+19 = 2^4+11. Тем более облом.

29 = 2^4+13. Представление единственно. Еще один кандидат.

35 = 2^2+31 = 2^4+19 = 2^5+3. Облом.

37 = 2^3+29 = 2^5+5 . Облом.

41 = 2^2 +37. Представление единственно. Кандидат.

47 = 2^2+43 = 2^4+31. Облом.

51 = 2^2+47 = 2^3+43 . Облом.

53 = 2^4+37. Представление единственно. Кандидат.

Итак, из всех МДС у нас остались только 4 допустимые суммы - 17, 29, 41, 53.

 
Я запутался. Бездумное применение разных фильтров может привести к глупостям.
 
Mathemat:
Я запутался. Бездумное применение разных фильтров может привести к глупостям.

Ну типа да. Я согласен, что если есть несколько валидных способов разложения, то вариант невалиден.

Но это относится только к валидным критериям, например S="2+составное нечётное". Для этого критерия строго и корректно доказана соответствующая лемма.

Критерий "степнь двойки + простое" в условиях задачи не фигурирует и не является доказанной леммой. Это просто свойство большинства решений. Но не всех, как выяснилось.

 
MetaDriver: Но это относится только к валидным критериям, например S="2+составное нечётное". Для этого критерия строго и корректно доказана соответствующая лемма.

Ну спасибо, хоть это посмотрел...

Критерий "степнь двойки + простое" в условиях задачи не фигурирует и не является доказанной леммой. Это просто свойство большинства решений. Но не всех, как выяснилось.

А вот тут ты не посмотрел. У меня это антикритерий - доказанный строго и корректно. Попробуй сам, если не хочешь смотреть мое доказательство (оно в посте чуть выше, зелененьким):

Если сумма представима в виде суммы степени двойки и простого несколькими способами, то эта сумма невалидна после третьей реплики.

Заметь, я не говорю о суммах, представимых таким образом единственным способом...

P.S. Еще раз пересмотрел свое опровержение твоего "решения" 16, 111. Пока не вижу там ошибок. Копирую сюда:

S=127, P=1776 (числа - 16 и 111) не может быть решением.

А: (1776=16*3*37.) Не знаю.

Б: (127 = 2+нечетное_составное.) Я и без тебя знал [, что не знаешь].

А: (Значит, сумма - это 2+нечетное_составное. 1776 = 16*111 = 48*37 = 592*3. Суммы - 127, 85, 595. Подходит только выделенная с разложением 16*111, т.к. 85-2 и 595-2 - простые.) Знаю числа.

Б: (Здесь укажу только два варианта полного перебора, которых достаточно:

127=2+125. П(=2*5*5*5) = 2*125 = 10*25 = 50*5. Суммы - 127, 35, 55. Допустима только одна - выделенная. Сумма 35 после третьей реплики недопустима, т.к. 35=4+31=16+19=32+3 (неоднозначное представление суммой степени двойки и простого). Кандидат (числа - 2 и 125).

127=16+111. П(=16*3*37) = 16*111 = 48*37 = 592*3. Суммы - 127, 85, 595. Аналогично. Кандидат (числа - 16 и 111). ) Не знаю.
Ты это признаёшь как корректное опровержение, MD?
 

Mathemat:

Ты это признаёшь как корректное опровержение, MD?

Да вроде как нет.


S=127, P=1776 (числа - 16 и 111) не может быть решением.

А: (1776=16*3*37.) Не знаю.

Б: (127 = 2+нечетное_составное.) Я и без тебя знал [, что не знаешь].

А: (Значит, сумма - это 2+нечетное_составное. 1776 = 16*111 = 48*37 = 592*3. Суммы - 127, 85, 595. Подходит только выделенная с разложением 16*111, т.к. 85-2 и 595-2 - простые.) Знаю числа.

Б: (Здесь укажу только два варианта полного перебора, которых достаточно:

127=2+125. П(=2*5*5*5) = 2*125 = 10*25 = 50*5. Суммы - 127, 35, 55. Допустима только одна - выделенная. Сумма 35 после третьей реплики недопустима, т.к. 35=4+31=16+19=32+3 (неоднозначное представление суммой степени двойки и простого). Кандидат (числа - 2 и 125).

127=16+111. П(=16*3*37) = 16*111 = 48*37 = 592*3. Суммы - 127, 85, 595. Аналогично. Кандидат (числа - 16 и 111). ) Не знаю.

Здесь логическая ошибка.

Сумма 35 вполне допустима на этом витке рассуждений, ибо при своей третьей реплике у мудреца А есть только один критерий - сумма известная Б = 2+нечётное-составное.

35=2+33=2+3*11, следовательно разложение 2+125 невалидно ибо и 127 и 35 являются допустимыми. Остаётся 16 и 111.

 
Беру паузу. Чую, что наворотил что-то непотребное, но пока не могу понять, что это :)
1...453454455456457458459460461462463464465466467...628
Новый комментарий