52 в математических заковыках.

Previous Entry Поделиться Next Entry
5 октября, 22:11
e_kaspersky
Совершенно случайно непосредственно перед своим днём рождения мне попалась очень заковыристая математическая задачка. Что характерно, в ней самым непосредственным образом участвует число "52". Задачка звучит следующим образом:

Однажды тёмной осенней ночью один злой русский хакер (ЗРХ) загадал два различных целых числа, оба больше единицы и меньше 100. Потом ЗРХ наугад выбрал двух честных программистов. Одному (программисту-П) он сказал результат произведения этих двух чисел, а второму (программисту-С) сообщил их сумму. То есть, чтобы не было разночтений: программист-П знает только произведение этих чисел, а программист-С знает их сумму и друг к другу они не подглядывают. Программисты призадумались... Через некоторое время программист-П сказал своему коллеге по несчастью:

-- Я не могу определить что загадал ЗРХ, мне не хватает данных.
-- А я сразу знал, что тебе не хватит данных! - порадовал его знаток суммы чисел программист-С.
-- Ага, ну тогда я знаю что за числа загадал русский хакер! - сказал программист-П.
-- Ну, раз так... то и я знаю! - сказал второй, и они вместе пошли пить пиво.

Вопрос: прежде чем мы к ним присоединимся - а при чём здесь 52? Обоснуйте.

Уверяю - задача имеет решение. Но это очень интересная задачка - я над ней помучился дней несколько... Но чур в интернеты не подглядывать!

M75A6975

P.S. Термины "русский хакер" и "программисты" можно менять на "блоггер, хипстер, гопник, блондинка, штирлиц - терминатор - мёрфиус, квят - феттель - хэмилтон, ...." что еще?.. - и прочие термины из новостных заголовков.

Замена "ЗРХ" и "Программист" на другие мемы может увеселить формулировку задачи и усмешить её решение. Решайте алгебраическое зубодробительное улыбаясь! = звучит как реклама таблеток для ума.

Чего и всем тоже обязательно желаю!
Метки:
Previous Entry Поделиться Next Entry

Записи из этого журнала по тегу «chtogdekogda»


Обоснуйте 4 и 13, исходя из условий задачи.
(только не надо копи-пастить интернеты или если уже знаете решение).

http://www.zerohedge.com/news/2017-10-05/putin-strikes-again-russian-hackers-stole-nsa-data-cyber-defense - тут опять как Вы у NSA данные сперли )) - может в суд на этих "фантазеов" подадите ??!


Опять корпоратив в тамошнем дурдоме... Но американские законы забавны - подать на газету в суд практически невозможно. Они же не сами на нас клевещут, там у них типа есть какие-то источники, которые они транслируют. Всё. Вы там тоже можете любую херню опубликовать под соусом "ехал в лифте и услышал вот что: ....."

Ну-ка, щас покумекаем.

> -- Я не могу определить что загадал ЗРХ, мне не хватает данных.

Значит, хотя бы одно из двух чисел — не простое. И если есть одно простое число, то оно меньше 50, а точнее меньше 100 / наименьший множитель второго числа. Потому что иначе из-за ограничения на каждое число (меньше 100) вариант будет все равно только один.

> -- А я сразу знал, что тебе не хватит данных! - порадовал его знаток суммы чисел программист-С.

Это довольно сильное заявление, означает, что как сумму ни разложить, то оба числа будут удовлетворять условию выше, эдакое отрицание гипотезы Гольдбаха. То есть сумма не может быть четной, ясное дело. А раз сумма нечетная, то одно из двух чисел четное (2..98), а второе нечетное (3..99, или 3..49 для простого числа).

> -- Ага, ну тогда я знаю что за числа загадал русский хакер! - сказал программист-П.

То есть до того у него было несколько вариантов, но только один из них с нечетной суммой, а остальные с четной. То есть если взять все простые множители обоих чисел, в них должно быть больше одной двойки, и еще ровно одно простое число (меньше 50), потому что иначе вариантов с нечетной суммой будет больше одного. Значит, имеем варианты:
x = 4, 8, 16, 32, 64
y = 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Ну, программист-П поделил произведение на 2 до упора, и уже знает числа.

> -- Ну, раз так... то и я знаю! - сказал второй, и они вместе пошли пить пиво.

Значит, программист-С попробовал отнять числа из списка x выше, и получил простое число из списка y ровно один раз. Скажем, 11 = 3+8 = 4+7 не проканает. Нужно поскладывать все возможные пары выше, и оставить неповторяющиеся суммы.

Зачем далеко ходить, пара строчек в баше и:
> for x in 4 8 16 32 64; do for y in 3 5 7 11 13 17 19 23 29 31 37 41 43 47; do echo $((x+y)); done; done | sort -n
видим, что есть лишь 27 уникальных сумм:
> 7, 9, 13, 17, 25, 29, 31, 41, 43, 53, 57, 59, 61, 67, 71, 73, 77, 79, 81, 83, 87, 93, 95, 101, 105, 107, 111

Скажем, 17 = 4 + 13, ну а произведение 52. :)

PS. С Днем!

> Скажем, 17 = 4 + 13

А почему не скажем 16+25 или даже 2+51 ?

primes = (2,3,5,7,11, 13,17,19,23,29,31,37, 41,43,47,53,59,61,67, 71,73,79,83,89,97)
s=set(xrange(7,198))
for i in primes:
for j in primes:
if j<>i and i+j in s:
s.remove(i+j)
print s
for i in (2,3,5,7):
for j in primes:
if j<>i and i*i+j in s:
print i*i,'*',j,'=',i*i*j
4 * 7 = 28
4 * 13 = 52
4 * 19 = 76
4 * 23 = 92
4 * 31 = 124
4 * 37 = 148
4 * 43 = 172
4 * 47 = 188
4 * 53 = 212
4 * 61 = 244
4 * 67 = 268
4 * 73 = 292
4 * 79 = 316
4 * 83 = 332
4 * 89 = 356
4 * 97 = 388
9 * 2 = 18
25 * 2 = 50
49 * 2 = 98


Edited at 2017-10-05 23:47 (UTC)

> for i in primes:
> for j in primes:

Зачем так себя ограничивать? Почему нет остальных чисел?

- Я не могу определить что загадал ЗРХ, мне не хватает данных.
-- А я сразу знал, что тебе не хватит данных! - порадовал его знаток суммы чисел программист-С.
-----

Вот именно. Не объединив свои данные, ответа они не найдут.


Ну, и пока ничто в условии задачи не указывает на то, что 52 тут при чем. Может быть, а может и не быть. Для решения нужны значения x*y и x+y.

учительница задаёт задачу
по реке плывут два напильника,один из них курит.высчитайте,сколько мне лет
вовочка - 28
учительница - правильно,расскажи решение
вовочка - мне 14,а папа меня полудурком называет

Решение хочу оставить здесь, чтобы не потерялось. Итак, есть задачка, в которой такие условия:

Условие0. Есть два различных целых числа A и B от 2 до 99.
Условие1. По их произведению A*B невозможно определить значения чисел.
Условие2. По их сумме A+B сразу было известно, что определить их значения невозможно.
Условие3. Зная произведение A*B и факт того, что "Условие2" = эти числа однозначно вычисляются.
Условие4. Зная сумму A+B и факт того, что "Условие3" = эти числа однозначно вычисляются.

Поехали...

Условие0 =>
сумма чисел от 5 до 98+99=197.
произведение от 6 до 98*99=9702.

Условие1 =>
Это не произведение двух простых чисел. Там как минимум три множителя: A*B = a*b*c. Разложение на простые даёт три и более чисел. Максимальное простое число в произведении <50, иначе оно сразу B и оставшийся хвост = A (поскольку если B=b*n, где b>50, то вылезаем за 100).

Условие2 =>
1) Это не сумма двух простых чисел (я даже термин придумал: "не-плюсо-простые", НПП).
2) Сумма A+B не более 55, иначе возможен расклад:
=> A+B=53(простое)+n для A+B от 55 до 152;
=> и A+B=97(простое)+n для оставшихся 153-197.
(то есть, второй не мог заявить "а я сразу знал...")

То есть, ищем пару чисел, сумма которых:
1) нечётная, т.е. представляется как 2+a*b или 2*a+b*c
2) не является суммой простых (здесь перебор от 2 до 53, больше не надо).
3) сразу можно выкинуть двойные попадания 2^n + p (простое), поскольку:
11=4+7 и 11=8+3 - второй не сможет по сумме сказать "а теперь и я знаю".

Остаются суммы:
17, 29, 41, 53

Далее число представляется как:
1) сумма 2*a+b*c = разложение на простые => варианты сумм a+b*c, a*b+c, a*c+b.
2) в двойных скобках (()) искомое число,
3) а просто в скобках () второй вариант числа, у которого нет разложения на сумму простых (удовлетворяет условию2).

Два или более чисел в скобках = нарушение условия3. Два однозначных набора без нарушения условия3 = нарушение условия4. То есть, надо найти число, у которого единственный вариант без двух (или более) чисел в скобках.

17 ->

2+15 = 2,3,5 => ((17)), (11), 13 = два числа в скобках, т.е. неоднозначное, поскольку два набора возможных сумм A+B, выкидывается по условию3.
4+13 = однозначное ((17)).
8+9 = 8,3,3 = ((17)), (27) два числа в скобках, выкидывается по условию3.
10+7 = 2,5,7 => (37), ((17)), 19 тоже самое.
12+5 = 4,3,5 => 19, ((17)), (23) тоже самое.
14+3 = 2,3,7 => (23), 13, ((17)) оно же.
Всё! ====> {4,13} удовлетворяет условию задачи.

Теперь надо доказать единственность решения. Перебираем дальше.

29 ->

2+27 = 2,3,3,3 => ((29)), 15, 21 однозначность номер1.
4+25 = 4,5,5 => ((29)), 25 = однозначность номер2, дубль, нарушение условия4.

41 ->

4+37 = 4,37 => ((41)) однозначность.
16+25 = 16,5,5 => ((41)), 85 => еще одна однозначность, нарушение услови4.

53 ->

16+37 => однозначность.
40+13 = 8,5,13 => 73, ((53)), 109. <---- вторая однозначность, поскольку при данном разложении на простые 109=104+5, 104 больше 100 и противоречит условию задачи.

Всё.

Единственное решение A,B = {4,13}.
A+B = 17,
A*B = 52 <======= а вот оно и и искомое "пятьдесят два". Это число, которое злой русский хакер сообщил программисту-П.

Edited at 2017-10-07 12:25 (UTC)

Я не слишком вникал, но интуиция подсказывает, что вы делаете слишком строгие предположения о получаемой программистами информации, и поэтому пространство решений резко сокращается.

Скажем, контрпример: пара (16,13).

> -- Я не могу определить что загадал ЗРХ, мне не хватает данных.

П видит 4 варианта: 2*104 = 4*52 = 8*26 = 16*13.
Действительно, не хватает.

> -- А я сразу знал, что тебе не хватит данных! - порадовал его знаток суммы чисел программист-С.

С видит 13 вариантов: 2+27 = 4+25 = 6+23 = 8+21 = 10+19 = 12+17 = 14+15 = 16+13 = 18+11 = 20+9 = 22+7 = 24+5 = 26+3.
Действительно, для каждой пары есть больше одного варианта перемножения.

> -- Ага, ну тогда я знаю что за числа загадал русский хакер! - сказал программист-П.

П понимает, что сумма обязательно нечетная, и остается с одним вариантом: 16*13.
Может, он делает и более строгий вывод, но у него все равно остался только один вариант.

> -- Ну, раз так... то и я знаю! - сказал второй, и они вместе пошли пить пиво.

С понимает, что раз чет-нечет у П был ровно один, то одно из чисел — степень двойки >1, а второе число — простое.

К примеру, в случае (4,25), П не мог бы различить между (4,25) и (20,5), хотя С точно так же заранее знал, что П не хватит данных: 2+27, 4+25, 6+23, ... — везде более одного варианта разложения на множители.

Поэтому С знает, что (16,13) подходит, а (4,25) — нет.

Ну и почему сумма не больше 55, тоже не вижу причин.

А перебором честно решать?

Часа полтора всего на решение ))

 var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
 function factor(n) {
	 var res = [];
	 for(var i = 0; n > 1 && i < primes.length; i++) {
		 var p = primes[i];
		 for(var j = 0; n % p == 0; j++, n /= p)
			 ;
		 if(j > 0)
			 res.push([p,j]);
	 }
	 return res;
 }

function enumPairs(fact) {
	if(fact.length == 0)
		return [[1,1]];
	var p = fact[0][0];
	var j = fact[0][1];
	var subPairs = enumPairs(fact.slice(1));
	var res = [];
	for(var i = 0; i <= j; i ++) {
		var m = Math.pow(p,i);
		var n = Math.pow(p,j-i);
		for(var k = 0; k < subPairs.length; k ++) {
			var pair = [subPairs[k][0]*m,subPairs[k][1]*n];
				res.push(pair);
		}
	}
	return res;
}


var simplePairs = [];
var simpleSums = {};
var nonSimpleSums = {};
for(var n1 = 2; n1 < 100; n1++)
	for(var n2 = 2; n2 < n1; n2++) {
		var multFact = factor(n1*n2);
		var pairs = enumPairs(multFact)
			.filter(p => p[0] < p[1] && p[0] > 1 && p[0] < 100 && p[1] > 1 && p[1] < 100);
		if(pairs.length == 1) {
			simplePairs.push([n1,n2]);
			simpleSums[n1+n2] = true;
		}
		else
			nonSimpleSums[n1+n2] = true;
	}

var exclusivelySimple = {};
var nonExclusivelySimple = {};
for(var n in simpleSums)
	if(n in nonSimpleSums)
		nonExclusivelySimple[n] = true;
	else
		exclusivelySimple[n] = true;

var exclusivelyNonSimple = {};
for(var n in nonSimpleSums)
	if(!(n in simpleSums))
		exclusivelyNonSimple[n] = true;

function getArrayFromNumKeys(obj) { return Object.keys(obj).map(n => Number(n)).sort((a,b) => a-b);}

console.log("simpleSums", getArrayFromNumKeys(simpleSums).length);
console.log("nonSimpleSums", getArrayFromNumKeys(nonSimpleSums).length);
console.log("nonExclusivelySimple", getArrayFromNumKeys(nonExclusivelySimple).length);
console.log("exclusivelySimple", getArrayFromNumKeys(exclusivelySimple).length);
console.log("exclusivelyNonSimple", getArrayFromNumKeys(exclusivelyNonSimple));

// -- Я не могу определить что загадал ЗРХ, мне не хватает данных. 
// not a simple pair
// -- А я сразу знал, что тебе не хватит данных! - порадовал его знаток суммы чисел программист-С.
// sum in exclusivelyNonSimple

var pairsWithExclusivelyNonSimpleSum = [];
var simplePairs2 = [];
var sipmleSums2 = {};
for(var n1 = 2; n1 < 100; n1++)
	for(var n2 = 2; n2 < n1; n2++)
		if((n1+n2) in exclusivelyNonSimple) {
			pairsWithExclusivelyNonSimpleSum.push([n1,n2]);
		
			var multFact = factor(n1*n2);
			var pairs = enumPairs(multFact)
				.filter(p => p[0] < p[1] && p[0] > 1 && p[0] < 100 && p[1] > 1 && p[1] < 100 && ((p[0]+p[1]) in exclusivelyNonSimple));
			if(pairs.length == 1) {
				simplePairs2.push([n1,n2]);
				sipmleSums2[n1+n2] = (sipmleSums2[n1+n2] || 0) + 1;
			}
		}

console.log("pairsWithExclusivelyNonSimpleSum", pairsWithExclusivelyNonSimpleSum.length);
console.log("simplePairs2", simplePairs2.length);

// -- Ага, ну тогда я знаю что за числа загадал русский хакер! - сказал программист-П.
// in simplePairs2
// -- Ну, раз так... то и я знаю! - сказал второй, и они вместе пошли пить пиво.
// only one pair with this sum in simplePairs2

var givenPairs = [];
for(var i = 0; i < simplePairs2.length; i++)
	if(sipmleSums2[simplePairs2[i][0]+simplePairs2[i][1]] == 1)
			givenPairs.push(simplePairs2[i]);

console.log(givenPairs);
if(givenPairs.length != 1)
	throw "givenPairs.length";

100 кстати можно смело заменить на 1000 (протестировал) - результат тот же, только одна пара.

Можно ли вообще не ограничивать?

?

Log in

No account? Create an account