Задача о числах мудрецов

Программирование - Практика программирования

Решаем головоломку средствами 1С

Однажды мне попалась вот такая задача:

Пусть x и y два целых числа 1<x<y притом x + y≤100. Салли сказали только сумму x + y, а вот Полю произведение xy. Салли и Пол честнейшие ребята, это всем известно, они и друг другу отродясь не врали.
И вот такой вышел у них разговор:
Пол: «Не знаю я, что это за числа.»
Салли: «Тоже новость. Я знаю, что ты не знаешь.»
Пол: «Ну твоя то сумма мне теперь известна.»
Салли: «Да уж и мне теперь твое произведение.»
Каковы числа? 

Идея решения пришла быстро, но отыскать его с помощью бумаги и карандаша оказалось трудно, поэтому пришлось обратиться к 1С.

Сначала определим алгоритм поиска. Хочу поблагодарить Сергея (ildarovich) за сделанное замечание, это позволило исправить первоначальный вариант, который давал правильные решения, но содержал ошибку

На предварительном этапе с помощью функции GetSallySum получим числа из заданного диапазона, которые нельзя представить в виде :

  • суммы двух простых чисел;
  • суммы простого числа и его квадрата;
  • суммы простого числа и его куба.

При выполнении  данной операции используется вспомогательная функция EratosthenesSieve для генерации списка простых чисел с помощью алгоритма "решето Эратосфена" Вот исходный код:

function  EratosthenesSieve(Ulimit)
	
	vt=new array(Ulimit+1);
	for i=2 to  Ulimit do
		if vt[i]=undefined then
			vt[i]=true;
			j=i+i;
			while j<=Ulimit do
				vt[j]=false;	
	
	arr=new array;
	for i=2 to  Ulimit do
		if vt[i]=true then
			arr.Add(i);
		endif;
	enddo;
	
	return arr;
	
endfunction	


function GetSallySum(ULimit)
	
	notsally=new array;
    //в массив parr записываем все простые числа непревосходящие установленную границу
	parr=EratosthenesSieve(Ulimit);
	

	vt=new valuetable;
	vt.Columns.Add("i",new ОписаниеТипов("Число"));
	imax=parr.UBound();
	for  i=0 to imax  do
		for j=i to imax do
			s=parr[i]+parr[j];
			if s<ULimit then
				row=vt.add();
				row.i=s;
			endif;
		enddo;	
		
		s=parr[i]+parr[i]*parr[i];
		if s<ULimit then
			row=vt.add();
			row.i=s;
		endif;
		
		s=parr[i]+parr[i]*parr[i]*parr[i];
		if s<ULimit then
			row=vt.add();
			row.i=s;
		endif;
	enddo;	
	
	vt.GroupBy("i");
	notsally=vt.ВыгрузитьКолонку("i");
	
	
	sally=new array;
	for s=4 to ULimit do
		
		if notsally.Find(s)=undefined then
			 sally.Add(s);
		endif;
    enddo;		
	
	
	return sally;
endfunction	

На следующем шаге мы готовим таблицу с числами кандидатами, среди которых будет искаться решение. Сумма этих чисел равна числу из массива, который возвращает предыдущая функция. Вот фрагмент кода:

 vt=new valuetable;
 vt.columns.Add("i",new ОписаниеТипов("Число"));	
 vt.columns.Add("j",new ОписаниеТипов("Число"));		
 vt.columns.Add("Multij",new ОписаниеТипов("Число"));		
 vt.columns.Add("Sumij",new ОписаниеТипов("Число"));		
 
 arr=GetSallySum(UpLimit);	
 for each sally in arr do
	 for i=2 to (sally-sally%2)/2 do
		 row=vt.Add();
		 row.i=i;
		 row.j=sally-i;
		 row.Sumij=sally;
		 row.Multij=row.i*row.j;
	 enddo;	 
 enddo;	 

Теперь разберем структуру запроса. Временная таблица Candidate содержит исходные пары чисел, с рассчитанными для них значениями  суммы и произведения. В таблице GroupMult мы собираем неповторяющиеся значения произведений. Затем из исходных данных отбираем только те строки, которые содержат уникальное значение произведения. Среди найденных строк находим неповторяющиеся значения для суммы. А затем применяем найденные значения, как фильтр к предыдущей выборке.

Приведу код, который я использовал при поиске решения. Сначала текст вспомогательной функции, которая помещает таблицу значений во временную таблицу, чтобы появилась возможность обращаться к ней в запросе. Аргумент МТТ - это ссылка на объект типа МенеджерВременныхТаблиц.

Функция PutToTemporaryTable(vt,name,MTT)
    ТекстЗапроса="ВЫБРАТЬ
                 |    ВходнаяТаблица.*
                 |ПОМЕСТИТЬ ВременнаяТаблица
                 |ИЗ
                 |    &мТЗ КАК ВходнаяТаблица
                 |;";
                    
    запрос=новый Запрос;
    запрос.Параметры.Вставить("мТЗ",vt);
    запрос.текст=СтрЗаменить(ТекстЗапроса,"ВременнаяТаблица",name);
    запрос.TempTablesManager=MTT;
    запрос.Выполнить();

КонецФункции
 

Теперь функция, в которой реализован приведенный выше алгоритм.

function NumberOfSages() export
	
 TTM=new МенеджерВременныхТаблиц;	
	
 vt=new valuetable;
 vt.columns.Add("i",new ОписаниеТипов("Число"));	
 vt.columns.Add("j",new ОписаниеТипов("Число"));		
 vt.columns.Add("Multij",new ОписаниеТипов("Число"));		
 vt.columns.Add("Sumij",new ОписаниеТипов("Число"));		
 
 arr=GetSallySum(UpLimit);	
 for each sally in arr do
	 for i=2 to (sally-sally%2)/2 do
		 row=vt.Add();
		 row.i=i;
		 row.j=sally-i;
		 row.Sumij=sally;
		 row.Multij=row.i*row.j;
	 enddo;	 
 enddo;	 
 PutToTemporaryTable(vt,"Candidate",TTM);
 
 
 query=new query;
 query.МенеджерВременныхТаблиц=TTM;
 
 query.Текст="ВЫБРАТЬ
             |	Candidate.Multij КАК Multij
             |ПОМЕСТИТЬ GroupMult
             |ИЗ
             |	Candidate КАК Candidate
             |
             |СГРУППИРОВАТЬ ПО
             |	Candidate.Multij
             |
             |ИМЕЮЩИЕ
             |	КОЛИЧЕСТВО(*) = 1
             |;
             |
             |////////////////////////////////////////////////////////////////////////////////
             |ВЫБРАТЬ
             |	Candidate.i КАК i,
             |	Candidate.j КАК j,
             |	Candidate.Multij КАК Multij,
             |	Candidate.Sumij КАК Sumij
             |ПОМЕСТИТЬ FilterMult
             |ИЗ
             |	Candidate КАК Candidate
             |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ GroupMult КАК GroupMult
             |		ПО Candidate.Multij = GroupMult.Multij
             |;
             |
             |////////////////////////////////////////////////////////////////////////////////
             |ВЫБРАТЬ
             |	FilterMult.Sumij КАК Sumij
             |ПОМЕСТИТЬ GroupSum
             |ИЗ
             |	FilterMult КАК FilterMult
             |
             |СГРУППИРОВАТЬ ПО
             |	FilterMult.Sumij
             |
             |ИМЕЮЩИЕ
             |	КОЛИЧЕСТВО(*) = 1
             |;
             |
             |////////////////////////////////////////////////////////////////////////////////
             |ВЫБРАТЬ
             |	FilterMult.i КАК i,
             |	FilterMult.j КАК j,
             |	FilterMult.Multij КАК Multij,
             |	FilterMult.Sumij КАК Sumij
             |ИЗ
             |	FilterMult КАК FilterMult
             |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ GroupSum КАК GroupSum
             |		ПО FilterMult.Sumij = GroupSum.Sumij
             |
             |УПОРЯДОЧИТЬ ПО
             |	Sumij,
             |	Multij";
 
 
  query.Parameters.Insert("UpLimit",UpLimit);
 
  vt=query.Execute().UnLoad();
  
  return vt;
  
EndFunction	

Ответ приводить не буду. Приведу результаты своих исследований. В условиях задачи сумма чисел меньше или равна 37. Первое решение появляется, когда верхний предел становится равен 65. Второе решение появляется при верхнем пределе 439.

Послесловие.

В начале статьи я благодарю Сергея (ildarovich) за сделанное замечание. Он указал, что два различных числа больше единицы  однозначно определяются по их произведению не только в случае, когда эти числа простые, но и в двух других, когда их произведение является либо кубом либо четвертой степенью простого числа. Во всех найденных мной в Сети решениях задачи о мудрецах говорится только о произведении простых чисел. Впрочем, с таким заявлением я поспешил, в этой статье такие варианты рассматриваются. Проведем поиск решения на конкретном примере . И так у нас есть таблица, которая содержит суммы двух чисел и их произведение. Значения произведений мы можем разбить на две группы, в первую отнесем  повторяющиеся значения, во вторую неповторяющиеся.

Таблица с данными
На приведенном рисунке в левой таблице содержатся неповторяющиеся произведения, в правой повторяющиеся. Данные построены для случая, когда сумма сомножителей меньше или равна 11. Внимательный читатель сразу заметит, что к неповторяющимся отнесено произведение 20, хотя 20 равно 4*5 и 2*10. Точно так же не подходят под критерий неповторяющихся произведения 28 и 30. Все дело в ограничении на сумму.  Для числа 20 сумма множителей 4 и 5 равна 9 и эта пара попадает в исследуемый набор, а сумма множителей 2 и 10 равна 12, что больше верхнего предела. Поэтому эта пара в наборе отсутствует.  Отсюда первый вывод , то куда попадет произведение из исходной последовательности зависит от ограничения на сумму сомножителей.

Разбиение на 2 множества при ограничении на сумму 16

Если мы будем рассматривать набор чисел, для которых сумма множителей меньше 16, то увидим что значения 20,28 и 30 исчезли из левой таблицы. Это подтверждают данные на приведенном рисунке. Следующий шаг заключается в поиске таких значений из колонки Сумма, которые не встречаются в левой таблице, но присутствуют в правой. В последнем примере таким числом является 11. И обнаружить мы это можем только начиная с суммы множителей равной 16.  Вот и второе наблюдение, список чисел, которые не выражаются в виде суммы сомножителей, чье произведение не повторяется в рассматриваемом наборе, зависит от размера этого набора. Ниже приведен список таких чисел. В колонке Предел проставлено значения верхнего предела суммы множителей, при котором появляется данное значение. Такие суммы назовем числами Салли.

Таблица сумм

Решения нашей задачи нам нужно искать среди таких пар, у которых значение суммы содержится в приведенном выше наборе. Найденные пары опять разобьем на две группу. В первую занесем те значения, которые не содержат повторяющиеся значения из колонки Произведение, во вторую отнесем пары с повторяющимися значениями произведения. Ниже приводятся таблицы для случая, когда сумма множителей меньше 64.

Сумма меньше 64

Левая таблица показана не полностью. Обратим внимание на две пары из левой таблицы - (17;52) и (17;70). Увеличим верхнюю границу до 65. Согласно нашим данным при этом ограничении появляется число Салли равное 37.

Решение для верхней границы 65

37 можно представить в виде суммы двух чисел 2 и 35. Их произведение равно 70. Значит произведение со значением 70 стало повторяющимся, появилось две пары (17;70) и (37;70). Поэтому пара (17;70) из левой таблицы уйдет. И в левой таблице появится пара (17;52) , у которой значение из колонки Сумма уникальное. И эта пара будет первым решением  задачи о числах мудрецов.

В изложенном подходе мы обрабатывали исключительно набор данных образованных парами, составленными из значений суммы и произведения двух множителей. В этом случае состав множества чисел, которые мы назвали числа Салли, определяется верхней границей для суммы сомножителей. В тоже время, существует альтернативный подход для построения чисел Салли. На первом шаге мы можем сгенерировать ряд простых чисел. На следующем  составить множество из попарной суммы простых чисел и сумм вида (p+p*p), а также (p+p*p*p), где p - это простое число. А затем найти числа, которые не вошли в указанный набор, но больше его нижней границы и меньше верхней. Именно такой подход я использовал. Результаты, которые дает запрос Сергея (ildarovich) и подход с использованием генерации чисел Салли совпадают. Отличие заключается в значении суммы множителей, при которых эти решения появляются. Ниже приводится ряд образованный значениями ограничений на сумму, при которых появляются новые решения задачи, если использовать генератор чисел Салли - 37,439,757,991,1267,1925,2023,2227,2323.  Запрос Сергея дает первое решение при верхней границе - 65 (это показано в разобранном примере) , второе при верхней границе 1685.

Ну и наконец, заключительная таблица с числами мудрецов.

       число А              число В           Сумма      Произведение
4 13 17 52
4 61 65 244
16 73 89 168
16 111 127 1 776
64 73 137 4 672
32 131 163 4 192
4 229 233 916
32 311 343 9 952
64 309 373 19 776

См. также

Комментарии
1. Александр Гремячкин (itvdonsk) 06.02.15 05:34 Сейчас в теме
И всего-то в задаче не указано что числа простые. Кажется автор телепат 80 уровня.
PheelSAV; GreenDragon; mrmasson; Dmirily; +4 Ответить
5. Валерий (scientes) 122 06.02.15 10:32 Сейчас в теме
(1) itvdonsk, Я прочитал замечание о простых числах и внес изменение в текст статьи, чтобы этот момент сразу стал понятен.
2. Алексей Роза (DoctorRoza) 06.02.15 08:37 Сейчас в теме
Решать головоломки с помощью 1С - мое нутро отвергает это напрочь! Только хардкор, только С++/Java! :)
3. Антон Антонов (monkbest) 28 06.02.15 10:02 Сейчас в теме
Не очень понятно, почему это обязательно простые числа?
4. Игорь Пашутин (Alien_job) 128 06.02.15 10:25 Сейчас в теме
конечно не простые, автор об этом пишет в первом же абзаце
6. Игорь Пашутин (Alien_job) 128 06.02.15 10:59 Сейчас в теме
7. Валерий (scientes) 122 06.02.15 11:28 Сейчас в теме
(6) Alien_job, если будет желание поэкспериментируйте со значением ограничения на сумму. Первое решение появится только тогда, когда верхняя граница равна 37, хотя сумма чисел решения будет меньше этого значения. 4 и 61 тоже самое, я сначала думал, что это ошибка в моей программе. Но нет, так и должно быть.
11. Игорь Пашутин (Alien_job) 128 06.02.15 11:35 Сейчас в теме
(7) scientes, да, экспериментирую. Но не представляю причину отсутствия решения при ограничении на сумму ммм меньше 37
12. Игорь Пашутин (Alien_job) 128 06.02.15 11:44 Сейчас в теме
(7) scientes, "Среди строк таблицы есть такие, которые содержат уникальные значения в колонке сумма или произведение, например, произведение простых чисел будет уникальным. Такие данные нам надо удалить." Почему вы удаляете уникальные произведения?
13. Валерий (scientes) 122 06.02.15 11:59 Сейчас в теме
(12) Alien_job, ни Пол, ни Салли не знают решение. Значит известные им значения суммы и произведения не позволяют назвать числа. Поэтому варианты с уникальными значениями мы и удаляем. Скажем, если бы Полу назвали произведение 143, он разложил его на множители 11 и 13. Это разложение единственное, он сразу называет ответ.
8. Валерий Дяченко (davealone) 06.02.15 11:31 Сейчас в теме
Допустим мы отсеяли все простые, но дальше если сумма и произведение известны, почему не решить головоломку как систему уравнений? Есть:
X + Y = SUM -> Y = SUM - X
X * Y = PROD - > SUM*X - X^2 = PROD -> X^2 - SUM*X + PROD = 0
Получим обычное квадратное уравнение, у которого меньший корень єто X, а больший Y
9. Игорь Пашутин (Alien_job) 128 06.02.15 11:33 Сейчас в теме
(8) davealone, мы не знаем суммы и произведения
10. Игорь Пашутин (Alien_job) 128 06.02.15 11:33 Сейчас в теме
(8) davealone, мы не знаем суммы и произведения(7) scientes,
14. Михаил Гусев (Идальго) 64 06.02.15 17:24 Сейчас в теме
Если числа непростые, то рассмотрим давайте пару (4, 15). Так, Салли сказали сумму = 19, ну и Полу = 60. Понятно, что Пол не знает из каких двух множетелей получается сложное число 60, веть это может быть пара (2, 30) или (3, 20) или (4, 15) или (5, 12) или (6, 10). От того, знает/не знает Салли, что Пол не знает пару этих чисел - ничего не меняется. Да и сам Салли на самом деле не знает из каких слагаемых образовалась сумма = 19. Поэтому, я думаю чего-то не хватает в условии. Хотя может и ошибаюсь?
15. Сергей (ildarovich) 5300 06.02.15 23:45 Сейчас в теме
Не знаю, где я ошибся, но вот решение, которое никак не хочет второй вариант на 439 показывать. Это всего один запрос и более короткий, чем у автора. Работает в консоли.
ВЫБРАТЬ
	0 КАК Х
ПОМЕСТИТЬ Бит

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Бит0.Х + 2 * (Бит1.Х + 2 * (Бит2.Х + 2 * (Бит3.Х + 2 * (Бит4.Х + 2 * (Бит5.Х + 2 * (Бит6.Х + 2 * (Бит7.Х + 2 * (Бит8.Х + 2 * Бит9.Х)))))))) КАК Х
ПОМЕСТИТЬ Ряд
ИЗ
	Бит КАК Бит9,
	Бит КАК Бит8,
	Бит КАК Бит7,
	Бит КАК Бит6,
	Бит КАК Бит5,
	Бит КАК Бит4,
	Бит КАК Бит3,
	Бит КАК Бит2,
	Бит КАК Бит1,
	Бит КАК Бит0
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Ряд1.Х КАК Х,
	Ряд2.Х КАК У,
	Ряд1.Х + Ряд2.Х КАК Сумма,
	Ряд1.Х * Ряд2.Х КАК ХУ
ПОМЕСТИТЬ Пробы
ИЗ
	Ряд КАК Ряд1,
	Ряд КАК Ряд2
ГДЕ
	Ряд1.Х < &Предел / 2
	И Ряд2.Х < &Предел - 1
	И 1 < Ряд1.Х
	И Ряд1.Х < Ряд2.Х
	И Ряд1.Х + Ряд2.Х <= &Предел
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Пробы.Сумма
ПОМЕСТИТЬ ТабуСумм
ИЗ
	Пробы КАК Пробы
ГДЕ
	Пробы.ХУ В
			(ВЫБРАТЬ
				Пробы.ХУ
			ИЗ
				Пробы КАК Пробы
			СГРУППИРОВАТЬ ПО
						Пробы.ХУ
			ИМЕЮЩИЕ
				КОЛИЧЕСТВО(*) = 1)
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	ЧислаСалли.ХУ
ПОМЕСТИТЬ ЧислаПоля
ИЗ
	Пробы КАК ЧислаСалли
ГДЕ
	НЕ ЧислаСалли.Сумма В
				(ВЫБРАТЬ
					ТабуСумм.Сумма
				ИЗ
					ТабуСумм)

СГРУППИРОВАТЬ ПО
	ЧислаСалли.ХУ

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ЧислаСалли.Сумма) = 1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	ЧислаСалли.Сумма,
	МАКСИМУМ(ЧислаПоля.ХУ) КАК Произведение,
	МАКСИМУМ(ЧислаСалли.Х) КАК Х,
	МАКСИМУМ(ЧислаСалли.У) КАК У
ИЗ
	Пробы КАК ЧислаСалли
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ЧислаПоля КАК ЧислаПоля
		ПО ЧислаСалли.ХУ = ЧислаПоля.ХУ
ГДЕ
	НЕ ЧислаСалли.Сумма В
				(ВЫБРАТЬ
					ТабуСумм.Сумма
				ИЗ
					ТабуСумм)

СГРУППИРОВАТЬ ПО
	ЧислаСалли.Сумма

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ЧислаПоля.ХУ) = 1
Показать
А возможно, ошибки и нет, а ошибка в исходной статье? Дело в том, что предположение про простые числа - не совсем верное. Вот, например 8 разлагается на сомножители однозначно, но не является произведением двух простых чисел.
16. Serg (Sykoku) 92 11.02.15 11:36 Сейчас в теме
Я думал, что решали ЛОГИЧЕСКУЮ задачу про мудрецов в колпаках (http://eruditor.ru/z/?2). А тут...

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

Решать арифметические задачи методом подбора - это еще додуматься надо...
17. Валерий (scientes) 122 11.02.15 11:54 Сейчас в теме
(16) Sykoku, Я полагаю, что это не арифметическая задача. Ответ получается в результате выполнения запроса. В Послесловии разобрано как этот запрос работает. Все методы решения, которые я видел, в той или иной форме реализуют этот алгоритм.
Оставьте свое сообщение