|
>> "маса с произволна /недефинирана/ форма и площ."
ок, приемам забележката :) да се чете
>> "маса с произволна /недефинирана/ форма на плота и крайна площ на същия."
Това, че площта на масата е крайна, не значи, че и диаметърът е краен. Съответно е възможно играта да се продължава до безкрайност. Написал съм го, и ще го повторя:
Необходимо условие за съществуване на стратегия, гарантираща винаги печалба на първия играч, е масата да е с краен диаметър.
Аз разсъждавам така. За да бъде решена е нужно да се състави математичен модел на задачата. И нека в този модел направим някои учочнения. Първото - за крайия диаметър вече го писах. Второто - понеже се говори за "маса", а не за много маси (то иначе би било цял ресторант ), нека приемем, че повърхността на масата представлява равнинна област, която е свързана. Под "свързана" разбирам следното. За всеки две точки от областта да е възможно да се намери крива начупена линия (поне една такава), съставена от отсечки (краен или безкраен брой), така че всяка точка от тази линия да лежи върху областта. Ако областта не е свързана, то в зависимост от това каква точно е тя, е възможно в някои случаи да се намери стратегия, при която вторият ще печели със сигурност. Ако например броят на компонентите на свързаност е четен и всеки от тях е такъв, че върху него може да се постави не повече от една монета и е достатъчно отдалечен от останалите компоненти на свързаност (така че монета, поставена върху един компонент да не "захапва" част от друг компонент), то вторият играч винаги ще печели.
С цел да упростя задачата изключвам възможността монета да бъде поставена върху ръба си и считам, че всички монети ще бъдат поставяни с основата си върху масата. Нужно е също така точно да се дефинира какво значи монета да бъде "поставена" на масата. Беше писано, че монета се счита за поставена, ако центърът и лежи на масата, включително и ако е върху ръба на масата.
Ланс Линк-тайният агент написа:
"Ако на масата няма място за нито една монета, то първия губи със сигурност."
Ако повърхността на масата е празно множество от точки - така е. Но, за да не губи първият със сигурност, изрично уточнявам, че повърхността на масата има поне една точка. Повърхност тук е условно казано, защото е възможно тази т.нар. "повърхост" да има площ нула - ако представлява или отделна точка, или отсечка, или дъга от крива линия, или множество от отсечки и/или дъги. Примерно, ако повърхността е само една точка, то първият поставя монетата с центъра точно върху точката и печели. Разбира се, физически е възможно монета да бъде поставена (при някои форми на масата) и така, че да стои, макар че центърът и няма да е върху масата (примерно върху кръгла дупка с диаметър по-малък от диаметъра на монетата), но за да не си усложнявам излишно живота, приемам горната дефиниция за "поставяне".
Без да се ограничава общността на разсъжденията може да се приеме, че диаметърът на монетите е единица.
И така, разглеждам следния математичен модел на задачата. В равнината е дадена свързана област с краен диаметър. Контурът, обграждащ областта, и принадлежи. Двама играчи се редуват да поставят върху областта кръгове с диаметър единица като два такива кръга не могат да имат повече от една обща точка. Кръг се счита за поставен върху областта ако центърът му е точка от областта. Да се намери стратегия, следването на която гарантира печалба на играча, поставил пръв монета.
Равнината може да се покрие с мрежа от равностранни триъгълници (да я наречем "триъгълна мрежа"), всеки от които имащ обща страна със свой съсед. Нека дължината на страната на един такъв равностранен триъгълник наречем константа на мрежата., а върховете на тези триъгълници - възли на мрежата.
Ланс Линк-тайният агент написа:
Тук отново имаме решавана задача (трудна, олимпийска, но решавана) - да се намери максималния брой монети който може да се сложи в една фигура.
Тази задача е същата като да се намери най-голямото цяло положително число, за което е възможно да се намери такова взаимно разположение на дадената фигура и триъгълна мрежа с константа единица, така че броят на възлите на мрежата, които фигурата покрива да е равен на това число. Това, разбира се е само при условие, че под "да се сложи във фигура" се разбира същото като "да се постави вурху масата". Ако под "да се сложи във фигура" се разбира кръгът (демек монетата) да не излиза извън очертанията на фигурата, тогава задачата е малко по-различна.
Ланс, пич, дай ако обичаш някакъв линк, където тази задача е била разглеждана/решавана.
Дали е вярно следното твърдение:
"Ако за дадена фигура (област от равнината) с краен диаметър и за дадена триъгълна мрежа е възможно да се намери такова тяхно взаимно разположение, че фигурата (областта) да покрива n на брой възли на мрежата, то или е възможно да се намери такова взаимно разположение, че броят на покритите възли да е (n-1), или е възможно да се намери такова взаимно разположение, че броят на покритите възли да е (n+1)."
В случая се има предвид включващо "или", тоест допуска се и двете неща да са възможни. Как мислите - вярно ли е това твърдение, или е невярно?
Ланс Линк-тайният агент написа:
...и ще сведем задачата до тази с клечките.
Коя задача с клечки имаш предвид?Редактирано от Пporpaмиcт-дъpвo на 12.11.08 00:34.
|
Re: Забавление [re: mlee]
