Задачки!!!!!!!!!!!!!!!!

Тази тема е специално за задачки (съвсем конкретни), които обаче са повече логически, а не такива, които изискват доста задълбочени знания върху определен дял на математиката, не такива, които се базират върху неравенството на Чебишев напр.

Ето първата: Доста е лесна, ама си струва, особено ако не си се занимавал с комбинаторика.

По колко начина може да се образува комисия от трима души, съставена от представители на 8,9,10,11 клас, като в комисията не бива да влизат двама представители от един и същ клас.

tova go razbiram kato izbor na tri predmeta ot 4. ami tova oznachava, che tryabva da izberem edin chovek izvyn komisiyata. imame 4 varianta.

Boian

Като съм бързал, съм объркал условието. Истинското е:
По колко начина може да се образува комисия от трима души, съставена от представители: по един ученик и една ученичка от 8,9,10,11 клас, като в комисията не бива да влизат двама представители от един и същ клас.
Така, не че е кой знае колко по-трудна, но поне да бъда коректен в условието, пък и иначе си е направо идиотска.

32

Pozna

dai drugi !

Една стара задача, на която ме интересува не просто отговора (всички го знаем), а възможно най-късото решение:
Математик кани двама приятели-математици (A и B) на гости.
Казва им:
- Намислил съм две цели числа и двете по-големи от 1 със сума по-малка от 100.
После казал на математик А сумата, а на математик B произведението и им
предложил да ги познаят.
Математик А казал:
- Ами аз не мога да ги кажа.
Математик B казал:
- Аз знаех, че няма да можеш да ги познаеш.
Математик А казал:
- Само че аз вече знам кои са.
Математик B казал:
- Тогава и аз знам кои са.

Та, кои са числата?

A sign from a Majorcan shop entrance:
Here speeching American.

mnogo trudna be :))) dai Joker

Въпреки че пишеш, че всички знаят отговора, аз не го знам. По-лошо не успях да го намеря. Така че нищо не ми остава освен да твърдя, че така поставена не може да се реши.

Ако от сумата на числата не можем да ги намерим, то те не са (2,2) или (2,3).

Ако от произведението знаем, че сумата на числата не е е достатъчна да ги намерим, то те са (2,2) или (2,3).

Тогава изказването на втория математик не носи допълнителна информация. Тоест задачата както е изказана не може да се реши.

Какво ще кажеш?

Като видях реакцията ви (и се изненадах) погледнах условието и съмненията ми се оправдаха: объркал съм неволно двамата математици (прося за извинение и си удрям главата в земята): приемете, че "А" е онзи, който е чул произведението (и говори пръв), а "Б" е чул сумата.
Хайде да видим сега докъде ще стигнете.

A sign from a Majorcan shop entrance:
Here speeching American.

Аха, така може и да стане.
Щото и аз стигнах до същия извод, като по-горе, че второто изказване не носи никаква информация.
Сега сигурен ли си, че това е условието?
Щото мене ми я бяха казали:
А: "Аз не ги знам"
Б: "И аз не ги знам"
А: "Аз вече ги знам"
Б: "И аз вече ги знам"
Ама човека дето ми я каза тогава и той не беше сигурен - кой е А и кой Б (кой е с произведението и кой със сумата).

Krasiva zadacha. Otne mi 10 min dokato razbera che ima greshka v uslovieto i poveche dokato ia resha s popravenoto.
Neka namislenite chisla sa X i Y
A(koito znae X*Y ) bi mogal da poznae chislata , togava i samo togava kogato X i Y sa prosti.
B moje da tvardi che A ne moje da gi poznae ot parvi pat, samo ako X+Y ne se prdstavia kato suma na dve prosti.
Nedokazana hipoteza(Goldbach 1742), no proverena za vsichki chisla po-malki ot 100( i mnogo poveche), e che ako 2*N>6 to 2*N se predstavia kato suma na dve prosti.
Sledovatelno X+Y e nechetno.
(Zab:Osven tova , X+Y-2 sashto ne triavba da e prosto, zastoto togava X+Y=(X+Y-2)+2 otnove e predstaviane s dve prosti)
Sledovatelno A razbira ot otgovora na B che ednoto ot chislata e chetno , a drugoto nechetno.
Za da moje A da gi poznae v tozi sluchai, te triabva da se e kolebal mejdu (2 i 2P) i (4 i P), kadeto P e prosto.
Sledovatelno negovia otgovor e 4 i P.
B moje da prosledi razsajdeniata na A , i razbira che ednoto ot chislata e 4 .
Sledovatelno reshenia sa 4 i P, kadeto P e prosto i P+2 ne e prosto ( za poslednoto vij zabelejkata)

Ами аз скалъпих една програмка дето ми даде 4 и 13 за отговор.
Между другото, ако P е произведението, което знае B, то не е задължително то да не е произведение на прости числа.
Примерно ако P = 49*49. Тогава то то се представя като:
1. 7 * (7*49) (мързи ме да ги сметна точно)
2. 49 * 49
Само че на първата двойка сумата е по-голяма от 100.

Ако програмата ми работи правилно, то отговорът е един - (4, 13).
Само че това не е матматическо решение - просто проверявам дали за дадена двойка числа са възможни дадените твърденията в дадената последователност.

Условието е точно както го казах (в твоя вариант не знам дали може да се реши).

A sign from a Majorcan shop entrance:
Here speeching American.

Да, това е отговорът, но мен ме интересуваше елегантно решение.
Предния постинг върви добре, но спира преди края - не е 4 и P (P+2 не е просто), а точно 4 и 13. 13-цата излиза благодарение на факта, че Б може да реши задачата. Но как...

A sign from a Majorcan shop entrance:
Here speeching American.

Не знам за второто решение, нещо в това, което мказваш, не ми е ясно. Нали 49*49 не е произведение на две прости числа (ти казваш "не е задължително да не е произведение на две прости", т.е. може да е произведение на две прости, само че 49 не е просто, нали? Значи...?
Но ето малко история...
Задачата я знам (изобщо нямам спомен койу ми я каза тогава) може би от 70-те години (нямам представа кой я е предложил пръв и как е била измислена, но това е много любопитно). Тогава бях хлапе и се мъчих бизло седмица (или две). Реших я, но изписах сигурно цяла тетрадка. След това случайно ми попадна в руското списание "Квант" (по-младите от вас може и да не са чували за него... всъщност нямам представа, може още да излиза). Това е единственото място, където съм я виждал решена (не, решението не беше особено елегантно - то съчетаваше известна икономия в разсъжденията с моя донякъде brute froce подход). Години по-късно я видях в една от книгите на М.Гарднър (преведени на български). Гарднър не привеждаше решение, но даваше отговора. Изглежда я беше поставил на страниците на Scientific American, защото имаше и анализи на читатели. Там Гарднър споменаваше, че задачата има единствено решение за суми по-малки от две хиляди и нещо (не знам защо ми е останало в главата 2601 - но това е спомен за нещо, което съм чел преди 20 години, така че може и да се лъжа). Тази граница мисля беше емпирично получена чрез проверка на възможните двойки числа (както ти правиш). Любопитното е, че 49*49 = 2401... малко напомня на спомена ми (2601)... Вярно, не сумата, а произведението, но дали нещо не се заблуждавам?
Елегантна задача все пак. Възможност за конкретно решение при условие, в което няма дори намек за числа. Винаги съм се чудил колко много информация може да има в привидно най-обикновени думи!

A sign from a Majorcan shop entrance:
Here speeching American.

Знам, че решението ми не е елегантно. Аз също съм любопитен да видя някакво математическо решение. Моето е абсолютен brute force - въртя през всички възможности (не аз де - компютъра).
Ама просто бях любопитен за отговора, пък да се напише програмата ми отне 10 минути, така че сравнително бързо видях отговора.

Иначе по-горе имах предвид, че ако Б знае произведението 49*49, то той знае, че числата са (49, 49) (не е казано да са различни, нали?). А някой беше казал, че за да знае Б кои са числата, то те трябва да са прости, т.е. той да знае произведение на прости числа. Горното не е такова, а Б пак може да отгатне числата.
Идеята е, че Б знае произведение p, от които могат да се получат двойки (p1, p2) и ако само за една двойка имаме p1 > 1, p2 > 1, p1 + p2 < 100 то това са числата, т.е. той ги знае. Същото имаме и за 39*39 - Б веднага разбира че те числата са (39, 39) (друга възможност са 3 и 3*39*39, но тогава сумата > 100, т.е. това не е възможно).

Neka MathA znae U*V=(2^N)*(P1^N1)*(P2^N2)*....(Ps^Ns),
N>-1, N1,..Ns>0, s>-1;
MathB znae U+V
Ot parvia otgovor na B se razbira , che U+V ne e se predstavia kato suma na dve prosti,
i sledovatelno U+V e nechetno ( MathA i Math B misliat che Goldbach Conjecture e viarna)
=> boo U e chetno i V e nechetno
=> N>0, s>0
Ako s>1,to A ne bi mogal da poznae otgovora v tozi moment (Osven ako ne izpolzva niakakvo ogranichenie za U+V, v koito sluchai elegnatno reshenie bez pregled na sluchai niama)
=> U*V=(2^N)*P^N1
Po sashtata prichina N1=1
=>U*V=(2^N)*P
I MathA veche moje da zaivai , che znae otgovora, U=2^N, V=P
Razbira se MathB moje da prosledi razsajdeniata na MathA (Neshto kato Arsene Lupin v knigite na Maurice Leblanc) i edinstvenoto koeto mu triabva za da poznae U i V v tozi moment e edinstvenost na predstavianeto na U+V kato suma na stepen na dvoikata i prosto chislo.
Koi chisla imat poseldnoto svoistvo ne moga da opredelia nabarzo, dori mi izglejda kato nereshena zadacha (Takmo si tarsia tema za dipplomna rabota :) )
Vav vseki sluchai 17 e takova i 4 i 13 e reshenie.
Pozdravi!

Но 49*49 не може да е решение, защото ако А знае 2401, а Б знае 98, то А започва краткия диалог с "Аз знам кои са числата" (2401 = 49*49 = 7*343 и само двойката 49*49 дава сума по-малка от 100, а това ограничение е известно на А). Така че ако числата са били (49,49), то диалогът (по условие) между двамата математици е неиздържан.

A sign from a Majorcan shop entrance:
Here speeching American.

Всъщност, твоята идея сигурно е да се илюстрира, че А може да каже числата и без те да са прости. Да, ако използва и ограничението за сумата. ПО ПРИНЦИП е така, но задачата залага не на решение по принцип, а на конкретна двойка (т.е. фактът, че А не ги е казал, означава, че не са 49 и 49).
Разбирам примера ти като контратеза на твърдението "А може да познае числата само, ако произведението е било от две прости числа" (може и ако са, примерно, 49*49 и още други). Но в случая (и това е, което има пряко отношение към задачата) се твърди друго: "А не може да познае числата от първи път само ако е чул произвдение на две непрости числа" (анализираме възможните изводи от първата фраза на А, а тя не е "Аз мога да ги кажа", в който случай може да се твърди, че числата овсен прости ммогат да са и такива, че сред всички разложения на произведението на двойки има само една комбинация със сума по-малка от 100).
С две думи, твоят пример (произведение на две числа, поне едното от които е съставно с "достатъчно" голям прост делител) е пример за критерий за отхвърляне на възможни комбинации от най-първата таблица на решенията.
Един възможен (и определено неелегантен) подход за решаване би бил следният:
1) Правим таблица от рода:
02 03 04...... 49 50 ......... 95 96 97
03 04...... 49 50 ......... 95 96
...............
49 50
Двойките решения (в реда "малко-голямо") се формират като вземем първото число от кой да е ред и кое да е друго число от същия ред (така се удовлетворява искането сумата да е < 100) - имаме 96+94+..+2 = 2304 двойки
2) Втората фаза е да елиминираме простите числа от всеки ред, започващ с просто число (така удовлетворяваме на първи етап изискването числата да не могат да се познават от първи път). Простите до 100 са: 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 - общо 25 на брой.
Така от съответните (започващи с прости числа) редове, елиминираме:
02 - 25 (всички прости)
03 - 23 (2, но и 97)
05 - 22
07 - 21
11 - 19
13 - 18
17 - 16
19 - 15
23 - 13
29 - 10
31 - 9
37 - 7
41 - 4
43 - 3
47 - 1
-----------
общо: 206 комбинации "просто-просто" (и със сума по-малка от 100, защото таблицата е такава), т.е. остават "само" 2098 възможни комбинации.
3) Знаейки, че сумата трябва да е нечетна (това произтича от първата фраза на Б), задраскваме във всеки ред числата с еднаква четност. След тази фаза, таблицата става доста рехава, напр. (съвсем произволно, но и защото е по-кратък) за ред "41": 42, 44, 42, 48, 50, 52, 54, 56, 58
4) Четвъртата фаза на елиминиране може да е тази, която произтича от формулирания от теб критерий (разглеждане на всички произведения и елиминиране на онези, при които едното от числата е с достатъно голям прост делител, така че само една от сумите на възможните множители да е по-малка от 100). Например, пак за същия ред "41" може да се разсъждава по следния начин:
(41,42) -> 41*2*3*7, които се групират по следния начин: (41, 2*3*7), (41*2, 3*7), (41*3, 2*7), (41*7, 2*3), (41*2*3, 7), (41*2*7, 3), (41*3*7,2) и веднага се вижда, че тук има една комбинация, за която сумата от двете числа е < 100, т.е. (41,42) отпада, понеже ако е чул 1722 (=41*42), а "веднага" ще съобрази, че от всики разложения на двойки множители има само една комбинация със сума по-малка от 100, следователно първите му думи че бъдат "Знам числата", а не "Не мога да ги кажа". Подобни "бабешки" разсъждения могат да се направят за всяка двойка от всеки ред. Всъщност използваме, че при фиксирано произведение X*Y минимална сума се получава при максимално близки множители (хм... аз всъщност съм по-уверен в другото: при фиксирана сума, максимално произведение се получава при равни множители), ние можем да разглеждаме само тези разложения, при които двойката множители се различават минимално. Едва когато направимм това отсяване на възможностите (трудоемка задача при този подход) ще изчерпим цялата информация, съдържаща се в първите две фрази на А и Б.
Само ще отбележа, че "погледнато на око" по този начин можем направо да задраскаме редовете над 40 например, защото ако имаме 40*Х (където Х е в интервала 40 - 59), то ако Х = 2*Y, имаме суми 40*2 + Z, където Z e най-малко 20, а тогава сумата става по-голяма от 100. А ако X = 3*Y, то още при първото групиране по различен начин 40*3 + Y имаме сума по-голяма от 100. Дори Х да е просто, тогава (понеже то е > 40) имаме 2*Х + 20 (вземаме двойката като минимален множител на 40) и пак имаме суми > 100 за всички комбинации. Т.е. може да се каже, че не може да има решение, в което и двете числа да са по-големи от 40, СЛЕДОВАТЕЛНО сумата е по-малка от 80, което налага нови изводи. Следващият извод е да задраскаме всички комбинации, в които има просто число по-голямо от 50 (защото при тях има само една комбинация от множители, при които сумата е по-малка от 100, понеже всяка друга комбинация трябва да съдържа n*X, където X е простото > 50, a n е най-малкия делител на второто число, т.е. поне 2). Таблицата вече доста проредя!
Аз ще спря тук, защото постингът ми стана много дълъг, но ще отбележа, че подходът на Genki спестява голяма част от този труд.

A sign from a Majorcan shop entrance:
Here speeching American.