по следам avva

[stas]

Задачка:

Есть два числа: X и Y больших 1, но меньших 100 и два человека: "А" и "Б". "А" сообщают произведение X и Y, а "Б" - сумму X и Y. Самих чисел оба, естественно, не знают. Между ними состоялся такой диалог:

"А": Я не могу сказать, чему равны X и Y.
"Б": Я знал, что ты не можешь этого сказать.
"А": Теперь я знаю, чему они равны.
"Б": Теперь и я знаю, чему они равны.

Вопрос: Чему равны X и Y?

Задачка не моя, списана с одного форума (я даже в ответе своем не на 100% уверен :). Но показалась интересной.

Comments

[avva.livejournal.com]

Åñòü ìíîãî çàäà÷åê òàêîãî ðîäà, õîðîøèé âîîáùå âèä çàäà÷. Ýòîé ðàíüøå íå âñòðå÷àë, ïûòàþñü äóìàòü âñëóõ.

Èç ïåðâîãî çàÿâëåíèÿ çíàåì, ÷òî ïðîèçâåäåíèå x*y íå óíèêàëüíî ñðåäè òàêèõ ïðîèçâåäåíèé ïàð ÷èñåë èç [2..99]. Âñå âîçìîæíûå ïðîèçâåäåíèÿ ðàçîáúåì íà äâà êëàññà: óíèêàëüíûå è íåóíèêàëüíûå (âîçíèêàþùèå èç äâóõ ïàð êàê ìèíèìóì).
Èç âòîðîãî çàÿâëåíèÿ çíàåì, ÷òî ñóììà ÷èñåë x+y òàêîâà, ÷òî *âñå* âîçìîæíûå ðàçáèåíèÿ x+y = a+b ïðèâîäÿò ê îäíîé èç íå-óíèêàëüíûõ ïàð - èíà÷å Á íå ìîã áûòü óâåðåí, ÷òî À íå áóäåò çíàòü ÷èñëà.
Ýòî çíà÷èò, âî-ïåðâûõ, ÷òî x+y != ñóììå äâóõ ïðîñòûõ ÷èñåë áîëüøå 1. Áîëåå òîãî, x+y íå ìîæåò áûòü ðàçáèòî êàê p+b, ãäå p ïðîñòîå áîëüøå 50. Ïîýòîìó x+y<=54. Êàêèå ÷èñëà áîëüøå 4 è ìåíüøå 55 íåïðåäñòàâèìû êàê ïðîñòîå + ïðîñòîå? Îáîéä¸ìñÿ äàæå áåç ãèïîòåçû Ãîëüäáàõà, ïðîñòûì ïåðåáîðîì: 2+x âû÷¸ðêèâàåò
4,5,7,9,13,15,19,21,25,31,33,39,43,45,49
3+x âû÷¸ðêèâàåò
5,6,8,10,14,16,20,22,26,32,34,40,44,46,50
5+x âû÷¸ðêèâàåò
7,8,10,12,16,18,22,24,28,34,36,42,46,48,52
7+x âû÷¸ðêèâàåò
9,10,12,14,18,20,24,26,30,36,38,44,48,50,54

Îñòàþòñÿ ïîêà: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53.

Èç òðåòüåãî çàÿâëåíèÿ çíàåì, ÷òî ïðîèçâåäåíèå x*y ó A áûëî òàêèì, ÷òî âñå âîçìîæíûå ðàçáèåíèÿ x*y=a*b äàâàëè òîëüêî îäèí âàðèàíò a+b èç âûøåâûïèñàííûõ ÷èñåë. Èç ÷åòâ¸ðòîãî çàÿâëåíèÿ çíàåì, ÷òî òîëüêî îäíà ñóììà x+y èç âûøåâûïèñàííûõ äà¸ò ïðè *âñåõ* âàðèàíòàõ x è y òîëüêî îäèí ñïîñîá ðàñïèñàòü x*y=a*b òàê, ÷òî a+b ïîïàäàåò â ñïèñîê (ò.å. òîëüêî îäíà ñóììà x+y ïîçâîëÿåò À ñêàçàòü òî, ÷òî îí ñêàçàë â òðåòüåé ôðàçå). Âñå îñòàëüíûå ñóììû x+y äîëæíû äàâàòü õîòÿ áû îäíó ïàðó x è y ñ íåîäíîçíà÷íûì ïðîèçâåäåíèåì; íàéä¸ì ýòè ñóììû ìåòîäîì ïðîñòîãî ïåðåáîðà:

11 = 5+6; 5*6=15*2; 15+2 = 17, âûâîä - 11 íå ïîäõîäèò
ïî òîé æå ïðè÷èíå (ñèììåòðèÿ) íå ïîäõîäèò 17

23 = 11+12 11*12 = 44*3 44+3=47, âûâîä 23 è 47 íå ïîäõîäÿò.

27 = 15+12 15*12 = 5*36 5+36 = 41 óáèðàåì 27 è 41
29 = 5+24 5*24 = 15*8 15+8 = 23 óáèðàåì 29
35 = 7+28 7*28 = 49*4 49+4 = 53 óáèðàåì 35, 53
37 = 3+34 3*34 = 51*2 51+2 = 53 óáèðàåì 37

Çàêëþ÷àåì, ÷òî åäèíñòâåííàÿ âîçìîæíîñòü - x+y=51 (ìîæíî ïåðåáîðîì òàêæå óäîñòîâåðèòüñÿ, ÷òî âñå a+b=51 ïðè âñåõ a*b=c*d äàþò c+d âíå ñïèñêà åñëè c,d íå ñîâïàäàþò ñ a,b; íî ýòîò øàã èçëèøåí, ò.ê. ìû óâåðåíû â òîì, ÷òî åñòü ðåøåíèå; ÿ ñäåëàë åãî â óìå, ÷òîáû ïðîâåðèòü, íå îøèáñÿ ëè ãäå ðàíüøå; äîñòàòî÷íî ïðîâåðÿòü a+b=51 è a*b=(a*z)(b/z) ïðè a è z íå÷¸òíûõ, èç ñîîáðàæåíèé ñèììåòðèè è òîãî, ÷òî âñå âîçìîæíûå ñóììû íå÷¸òíû).

Òóò ÿ ïîêà çàñòðåâàþ. Íàäî ïîäóìàòü.

Êàçàëîñü áû, ëþáàÿ êîìáèíàöèÿ x+y=51 òåïåðü ïîäõîäèò, ò.ê. ïðè ëþáîé òàêîé êîìáèíàöèè À ìîæåò íà òðåòüåì õîäó äîãàäàòüñÿ, êàêîâû x è y. È íåïîíÿòíî, êàê ëþáàÿ èç íèõ ìîæåò äàòü Á íà ÷åòâ¸ðòîì õîäó ïîíÿòü, êàêîâû x è y. Áóäó äóìàòü åù¸ ;)

[stas]

Ãì. Áðåä íàïèñàëñÿ. 51 íå ïîýòîìó íå ïîäõîäèò, à ïîòîìó, ÷òî åñëè ýòè ÷èñëà áûëè - 34 è 17, òî À ìîã óãàäàòü ñðàçó (ò.ê. 2*17*17 îñîáî äðóãèì ñïîñîáîì íå ðàçëîæèøü, ó÷èòûâàÿ, ÷òî èñõîäíûå ÷èñëà ìåíüøå 100).

[avva.livejournal.com]

Ñîãëàñåí, 51 íå äîëæíî áûòü â ñïèñêå. ß íåäîñòàòî÷íî òùàòåëüíî åãî ñîñòàâèë, ìíå ïîêàçàëîñü, ÷òî äîñòàòî÷íî óáðàòü âñå ñóììû ïðîñòûõ, à ïðî ñèììåòðèþ, ñâÿçàííóþ ñ òåì, ÷òî òðè ïðîñòûõ ìíîæèòåëÿ ìîãóò äàâàòü òå æå ÷èñëà â äðóãîì ïîðÿäêÿ (ò.å. 17-34 è 34-17) êàê åäèíñòâåííûé âàðèàíò, ÿ íå ïîäóìàë. Íî êàæåòñÿ ýòî âåðíî òîëüêî äëÿ 51, à â ìîèõ ïîäñ÷¸òàõ äëÿ 11 è 17 â îêîí÷àòåëüíîì âàðèàíòå îíî íå âñïëûâàåò, òàê ÷òî îòâåò îñòà¸òñÿ âåðíûì ;)

[avva.livejournal.com]

ß ïîíÿë ñâîþ îøèáêó: ÿ íåïðàâèëüíî ïðîàíàëèçèðîâàë ÷åòâ¸ðòîå âûñêàçûâàíèå. Íåâåðíî, ÷òî x+y äîëæíî áûòü òàêèì, ÷òî èç x+y=a+b è a*b=c*d ñëåäóåò, ÷òî c+d âíå ñïèñêà (êàê ÿ ñ÷èòàë). Ýòî èìåííî ÷òî íå äà¸ò Á âîçìîæíîñòè îïðåäåëèòü ÷èñëà. Íàîáîðîò, x+y äîëæíî áûòü òàêèì, ÷òî òîëüêî äëÿ îäíîãî ðàçáèåíèÿ x+y=a+b âûïîëíÿåòñÿ: èç a*b=c*d ñëåäóåò, ÷òî c+d âíå ñïèñêà (ò.å. ÷òî À ìîæåò îïðåäåëèòü a è b íà òðåòüåì øàãå). Äëÿ ñóììû S ñêàæåì, ÷òî ðàçáèåíèå x+y=S õîðîøåå, åñëè x*y=a*b -> a+b âíå ñïèñêà (åñòåñòâåííî, a,b îòëè÷íû îò x,y). Ìû èùåì S, ó êîòîðîãî åñòü òîëüêî îäíî õîðîøåå ðàçáèåíèå.
Ðàçáèðàÿ S îäíî çà äðóãèì:
11=5+6; 5*6=15*2; 15+2=17: ïëîõîå
11=9+2; 9*2=3*6 3+6=9 âíå ñïèñêà: õîðîøåå
11=4+7; 4*7=2*14 2+14=16 âíå ñïèñêà: õîðîøåå

Çíà÷èò, 11 îòïàäàåò.

17=3+14=5+12=7+10=9+8=11+6=13+4=15+2.

Èç íèõ 3+14 ïëîõîå (21+2=23 â ñïèñêå), 5+12 ïëîõîå (20+3=23 â ñïèñêå), 7+10: 35+2=37 ïëîõîå,
9+8: 3+24=27 ïëîõîå, 11+6: 33+2=35 ïëîõîå, 13+4: 26+2=28 âíå ñïèñêà - õîðîøåå, 15+2: 5+6=11 ïëîõîå. Óðà! Òîëüêî îäíî õîðîøåå. Âñå îñòàëüíûå ñóììû óæå ðàññìàòðèâàòü íå íàäî (ïðåäïîëàãàÿ, ÷òî ó çàäà÷è òîëüêî îäèí îòâåò).

Îòâåò: 13 è 4.

Õîðîøàÿ çàäà÷êà ;)