За момичетата и математиката

Не знам дали се усещате, но да се напреварвате да решавате задача по математика за _ученици_, след като вие сте завършили _университет_ е.. ъъ.. доволно комплексарска история. Също, безкрайно убеден съм, че в подготовката на учениците за математически състезания влиза елементарна дискретна математика, включая теория на графите и на множествата. По мое време (преди 20 години) дори състезателите от 7ми клас боравеха съвсем спокойно с тях, така че няма как сега да са по-зле.

Първо нека кажа браво на момичетата - пожелавам им още много успехи ! Дано имаме още повече такива деца. straws извинявай ама пишеш глупости. Крайния брой приятели е много важен и не е за заблуда на противника. Тук не се изпозват никакви графи, ами само подмножества и проста индукция. Ето кратко решение на А : Нека предположим че има популярен човек х който не е най-добър приятел на никой друг популярен човек. Приятелите на х са в краен брой. Тези на които х е най-добър приятел са подмножество на приятелите му, значи и те са в краен брой. х е популярен, значи е n-най-добър приятел за всяко n : следователно съществува поне един у на който х е най-добър приятел и такъв че у е n-най-добър приятел за безкраен брой числа n. С индукция се доказва много лесно че ако някой е (n+1)-най-добър приятел на друг, то той е n-най-добър приятел на трети. С още една индукция доказваме че ако m>n, то m-най-добрите приятели са подмножество на n-най-добрите приятели. Според първоначалното предположение у не е популярен : нека тогава j бъде такова число че у да не е j-най-добър приятел на никого. у е n-най-добър приятел за безкраен брой числа n, следователно съществува i>j такова че у да е i-най-добър приятел, което е в явно противоречие с доказаното - i-най-добрите приятели трябва да са подмножество на j-най-добрите приятели. И ето че стигнахме до търсеното противоречие. Току що доказахме каквото се искаше по метода ad absurdum. За Б елементарно може да се построи нужния пример използвайки естествените числа за хората в социалната мрежа. Надявам се че съм успял да напиша нещата ясно и в език разбираем за повечето хора. Задачката е доста лесна, когато човек вече си е изписал условието на математически език - просто така записана изглежда по-сложно отколкото е. Но свалям шапка на гимназистките които са я решили на тяхната възраст.

"...straws извинявай ама пишеш глупости. Крайния брой приятели е много важен и не е за заблуда на противника..." ----------- Шаман, върни се още на първия ми пост и прочети, че твърдението ми за "заблудата" се отнася за подточка Б, където условието е точно обратното - че приятелите могат да са безкраен брой. Това нещо не съм го използвал в Б (и в интерес на истината наистина съм се объркал, че е за заблуда, защото видях решение на подточка А, което важи и за безкраен брой приятели, тоест по подразбиране това условие не ми беше необходимо). Наистина не разписах решението на А по прост и достъпен начин, както си го направил ти, но не зная дали забелязваш, че идеята ми е същата като твоята, с тази разлика, че използвам не множества и подмножества, които се учат в училище, а изображения на множества. По този начин съм нахвърлял решение на по-общ случай, както казах, когато има безкраен брой приятели. Така че това за "глупостите" го приемам само по един начин - не си разбрал това, което съм написал. Наистина ми е трудно да се изказвам ясно и просто, но и ти самият не си перфектен - в доказателството си въвеждаш едно число м, което не ползваш никъде; този ти цитат: "...С индукция се доказва много лесно че ако някой е (n+1)-най-добър приятел на друг, то той е n-най-добър приятел на трети...", е всъщност преповтаряне на дефиницията от условието; а накрая просто изби рибата с това "...За Б елементарно може да се построи нужния пример използвайки естествените числа за хората в социалната мрежа...". Затова карай малко по-въздържано към съфорумците. Първоначално изпитвах удоволстие да помисля малко над задачката и да споделя идеята си за решение, но сега направо съжалявам. Ти взе да се изживяваш като ментор, който не е разбрал смисъла на написаното (дори за коя подточка се отнася), но го квалифицира като "глупост" (между другото, да не си учител?). Деоуина пък взе да говори за някакви комплексари, при положение, че самият той не пропуска случай да напомни, че работи на Уолстрийт, колко математика бил учил, колко бил добър и какви пари вземал. Щеше да бъде смешно, ако не беше тъжно. С удоволствие приемам да участвам в дискусии за решението на занимателни задачки, но да се наддумвам с деоуини - тц.

@straws : просто пиша каквото мисля А - това че може да се създаде пример с безброй много приятели няма нищо общо с това което се иска да се докаже тук. по-скоро с този пример доказваш че в Б (с безброй много приятели), и двете ситуации са възможни - и явно пак грешиш в нещо основно щом си "успял" да докажеш А за безкраен брой приятели, защото това е в ясно противоречие с исканото в Б... - числото m се използва съвсем накрая за да се получи противоречието : i играе ролята на m, j играе ролята на n - дефиницията на к-най-добър приятел в условието, така както са я написали очевидно навежда на мисълта че съответните подмножества от к-най-добри приятели са така построени че всяко едно съдържа следващото, но това не е дадено условие и не може да си спестим формалното му доказване с кратка индукция която се побира в 3 реда Б ето и елементарния пример (не съм опитал да се правя на Фермат и да казвам че имам "красиво и елементарно решение но мястото на страницата не ми е достатъчно да го запиша" ) Нека х(n) бъдат хората в мрежата, за всяко естествено число n. Връзките от тип приятел не играят важна роля тук, така че нека всеки бъде приятел на всеки друг човек. За всяко n и за всяко к такова че [n(n+1)/2]-10, x(0) бъде (n+1)-най-добър приятел на x((n+1)(n+2)/2-2). Нека това бъдат всички връзки от типа най-добър приятел. Получаваме че x(0) е n-най-добър приятел за всяко n>1, следователно x(0) e популярен. По конструкция никой друг човек не е може да е популярен, тоест x(0) не е най-добър приятел на друг популярен човек. straws, прочети всичко внимателно Опитах се да запиша възможно най-кратко решенията

Стана грешка и ми изряза част от написаното Пиша пак примера за Б Нека х(n) бъдат хората в мрежата, за всяко естествено число n. Връзките от тип приятел не играят важна роля тук, така че нека всеки бъде приятел на всеки друг човек. За всяко n и за всяко к такова че [(n+1)(n+2)/2-1]

има някякъв проблем ето текста като .jpg http://i44.tinypic.com/fw3k1z.jpg

"... и явно пак грешиш в нещо основно щом си "успял" да докажеш А за безкраен брой приятели, защото това е в ясно противоречие с исканото в Б..." ------------ Не бе, човек, наистина не ме разбираш, макар дори сам да си го написал по-долу за Б.: "...Връзките от тип приятел не играят важна роля тук, така че нека всеки бъде приятел на всеки друг човек...". Релацията "приятел" е различна от релацията "най-добър приятел" - ние се опитваме да доказваме разни неща за популярността, която се дефинира чрез "най-добър приятел" и не виждам за какво ни трабва да намесваме "приятел" в моето предложение за доказателство. Можем да работим само с релацията "най-добър приятел" и в двете подточки. За А. предполагам е необходимо за твоето доказателство, но за моето не е, защото пак ти казвам, използвам инекция на множеството на релациите в множеството на потребителите. За общо к на брой потребители в системата (където к е произволно естествено число) има не повечеч от к на брой релации "най-добър приятел" (това го знаем не защото са подмножества едно на друго заради безкрайността, а заради споменатата инекция, която позволява да "сравняваме" безкрайни редици от числа). Следователно винаги можеш да вземеш друго естествено число к+1, за което в дефинираната система няма как да съществува (к+1)-най-добър приятел, защото потребителите са к на брой, следователно няма к+1 на брой релациите, които да направят този човек популярен. Релацията "приятел" не е необходима при това доказателство, а само при твоето, което, пак казвам, очевидно е търсеното, защото е съобразено с възрастта на учениците. Затова те питах дали си учител - явно добре знаеш какво са учили и какво могат да използват. Но иначе продължавам да твърдя, че за да бъде човек популярен, трябва да се получи цикъл в графа (затова, Деоуине, намесих графи, само заради терминологията, за да се разбираме по-лесно, иначе и аз не мисля, че се ползва нещо от теория на графите в доказателствата). Но наистина условието е зададено малко неясно - примерно не е казано при определяне ранг на приятел дали могат да се повтарят потребителите - тоест ако имаме затворен цикъл (А е в релация с В, В със С и С с А), дали това ограничава и тримата да са 3-най-добър приятел или е възможно да започнеш да циклиш безкрайно по релациите и за всеки цикъл да твърдиш, че хората в него са популярни. Ако не е възможно да циклиш, то тогава популярни хора може да има само ако има един единствен цикъл в множеството на потребителите, който включва всички тях, но и тогава малко ми убягва като концепция цялата система... а и подточка Б. би била невъзможна (освен ако няма грешка при превода и всъщност са искали да кажат, че са възможни безкрайно много релации най-добър приятел за всеки потребител?). Както и да е, май спирам спора, защото в началото бях напълно убеден в условието, но ако има грешки при превода, може би спорим напразно. Всеки май си го разбира по негов си начин За Б. за съжаление не мога да отворя картинката, проксито ми го резва

http://picbg.net/img.php?file=73a2a365ac97ae86.jpg http://postimage.org/image/z97khd9lp/ http://www.freeimagehosting.net/djlm2 пробвай тези, ако не стане и с тях, махни/смени или конфигирирай проксито...

Мерси, сега го отворих. Обаче, признавам си, не мога да осмисля доказателството ти на Б. "...Получаваме, че х(0) е най-добър приятел за всяко н по-голямо от 2, следователно х(0) е популярен..." - да но нали за н = 1 и н = 2 не знаем дали е най-добър приятел, следователно няма да е популярен? Също така, ме притеснява и това "... по конструкция никой друг човек не може да бъде популярен..." - това откъде идва, каква е тази "конструкция"? Не смея да отхвърля решението ти, защото явно имаме проблем с комуникацията и не се разбираме добре взаимно (то затова и трябва да се ползва стриктно математически език, без съкращения), но ми се струва, че нещо ти куца в доказателството на Б. Опасявам се, че и аз звуча като теб, когато казваш, че нещо не е наред в моята идея за решение, но наистина не мога да разбера на какво основание твърдиш горните 2 неща? Красимир, балгодаря за оригинала, наистина изглежда вярно преведена задачата. Грешката явно е в нас Но аз продължавам да питам как може релациите да са безкрайно много без да има цикъл? Винаги броят на релациите ще е по-малък или равен на броя на потребителите, който е естествено число и следователно няма как да се постигне популярност за така дефининираната система без цикъл.

достатъчно е за n>1 или 2 защото вече съм доказал че ако m>n и си m-най-добър приятел, то също со n-най-добър приятел нарисувай си какво става за n=0,1,2 и ще видиш правя последователно наредени групички от елементи като увеличавам дължината с 1 целта е всяка от тези поредици да ми даде 1-най-добър приятел, после 2-най-добър приятел и тн..., после всеки от тези елементи избират х0 за най-добър приятел правейки го така 2-най-добър приятел, 3-най-добър приятел итн... също така внимавам да ограничавам всеки от елементите в групичките така че да е най-много едиси-какъв-най-добър приятел, и така гарантирам че х0 е единственият популярен

Оф, естествено, че си прав за индекси 1 и 2, разсеян съм. И идеята ти за доказателство е интересна, но ми се струва невярна, ако съм те разбрал правилно. Ако навържеш толкова много потребители към х(0), то броят на тези потребители (например от група 1, група 2, група 3 за 3-най-добър приятел) ще бъде винаги по-голям от максимални ранг (най-голямото число, за което е най-добър приятел) на този човек - от моя пример са 6 човека, а х(0) е от трети ранг най-добър приятел (защото това е най-голямата група досега). Ако добавим и верига с 4 потребителя, ще станат 10 на брой, а рангът ще е 4. Винаги ще можам да вземам естествено число, по-голямо от броя потребители, което е по-голямо от ранга на човека. Разбираш ли, убягва ти идеята за изображение на едно множество в друго. Точно това се опитвам да ти обясня и твоят пример е много хубава илюстрация - множеството на релациите се изобразява инективно в множеството на потребителите дори за безкраен брой (грубо казано, по-"малко" е, подмножество) и следователно винаги за всяка дефинирана система, ако вземем число н, равно на броя потребители, то ще бъде по-голямо от ранга. Освен ако няма цикъл и включените в него винаги ще могат да направят безкрайно много завъртания по цикъла за да достигнат до произволно естествено число, по-голямо от броя потребители. Разбираш ли? Не ми отговори на втория въпрос - защо "... по конструкция никой друг човек не може да бъде популярен..."? Откъде идва това? На противното мнение съм - има поне още един популярен в системата, заради цикъла, без който няма как да има популярни въобще. Според мен, трябва да изясним първо А., че после да мислим Б.

всеки елемент (освен х0) е най-добър приятел на най много един друг елемент и правя само крайни цикли всеки от който свъшва в х0 ето защо по конструкция няма друг популярен няма грешка в това което съм писал 100% гаранция давам

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

Ей, много съм тъп - сетих се още един много очевиден аргумент против системата ти само от един популярен човечец. Нали в първото подусловие доказваме противното - че всеки популярен е най-добър приятел на друг популярен - следователно не може да има само един брой в подточка А. В Б. само добавяме възможността да имат по безкрайно много приятели, но това няма връзка със систематат ти, защото ти не ползваш релацията "приятелство" в доказателството си (и аз не виждам как се ползва изобщо). Разбираш ли, дори самото твърдение за доказване, че всеки популярен е най-добър приятел на друг популярен ни насочва към мисълта за цикъл.

straws, ми сори, ама точно като комплексари звучите с тия силни надпреварвания един с друг за решаване на задачка за гимназисти с университетски знания. Ако те кефи да се занимаваш, сядаш и си разписваш задачката за лично удоволствие. В такъв случай, обаче, обясни ми защо е нужно писането по форумите. А между другото, никога не съм споменавал колко пари взимам, просто защото никога не е било релевантно. Точно както съвсем не е релевантно дали аз съм комплексар за това дали вие сте такива.