Игра с множества или загубени в превода...

[drago]

Дадено е множеството [tex]M[/tex], което се състои от [tex]n[/tex] елемента. [tex]k[/tex] е фиксирано естествено число.
Двама човека, [tex]A[/tex] и [tex]B[/tex], играят на следната игра. На всеки ход [tex]A[/tex] разделя, както пожелае, [tex]M[/tex] на две части, а [tex]B[/tex] избира една от тези части. Няма ограничение в броя на ходовете. [tex]A[/tex] печели, ако успее да накара [tex]B[/tex] в [tex]k[/tex] последователни негови избора да избере множества с непразно сечение.
Да се докаже, че [tex]A[/tex] има печеливша стратегия при:
а) [tex]n=2^k[/tex]
b) [tex]n=2^{k-1} + 1[/tex]

П.П. Под "разделя [tex]M[/tex] на две части" се разбира две непресичащи се части с обединение [tex]M[/tex]. Задачата е давана на някакво състезание в латинска америка и има и друга история, но затова по-късно.

[inveidar]

Подточка А) не е ли елементарна? Разделя N на две групи. В зависимост от избора на В, разделя избраната от него група на половината и слага по една половинка към неизбраната група при първия избор. След това пак така - дели избраната половинка на половина и т.н. На к-тия избор му остава точно по един вече избран елемент, който слага в двете групи?

[drago]

Да, така е. а) е почти елементарна.
Но и б) не е трудна. Ако A вземе един произволен елемент [tex]x_1 \in M[/tex] и предложи на [tex]B[/tex] да избира между [tex]\{x_1\}[/tex] и [tex]M \setminus \{x_1\}[/tex], то какви са вариантите. Ако [tex]B[/tex] избере [tex]M \setminus \{x_1\}[/tex], то нещата нататък стават като подточка a) нали? И B няма да е толкова прост да го направи и ще избере [tex]\{x_1\}[/tex] . Но ако [tex]A[/tex] му предложи отново и отново същия избор, то колко пъти [tex]B[/tex] може да се отклонява ?

[Гост]

Ako A предлага последователно на B да избира между [tex]x_1[/tex] и [tex]M-x_1[/tex] то B не може [tex]k[/tex] последователни пъти да избере [tex]x_1[/tex], защото тогава ще е избрал [tex]k[/tex] последователни множества с непразно сечение. Значи все някога трябва да избере [tex]M-x_1[/tex] и тогава на следващия ход A започва като в т.А).

[drago]

Г-н Стоянов, как мислиш, ако тази задача беше дадена на този ЕМТ дали доста хора щяха да я решат?

[inveidar]

Мисля, че задачата е подходяща и цялата биха я решили не повече от 15-на участника.

[Гост]

A) биха я решили почти всички, мисля, че и Б) доста хора щяха да се сетят.

[inveidar]

За А) - биха я решили не повече от 60% от участниците.За Б) - както казах. Това е нестандартна задача, която не включва обаче някакви нови знания. Въпрос на интелект.
Сега аз да питам. Какво ще кажете за тази задача за 8 клас - viewtopic.php?f=60&t=11134? Колко човека ще я решат и дали е подходяща?

[drago]

Ще ти кажа мнението си за тази задача в темата дето си я постнал, но първо да довърша това.
Значи 15-на човека. Да предположим все пак, че г-н Стоянов е оптимист и я решат да кажем 10-тина.
Значи нац. ни отбор като цяло ще се справи с нея. И аз така мисля.
Сега да продължа от началния пост.
Задачата е давана на някакво състезание в латинска америка. Мястото е Аржентина, състезанието- IMO 2012, задачата е 3-та. Задачата убиец.
Исате ли да анализираме защо тя бе такова фиаско за почти всички участници, като много отбори получиха общо 0т. на нея. България има общо 7т. и то благодарение на само 1 участник- Богдан Станков.
Ключът към тази задача е "превода".

[Гост]

Ще ти кажа мнението си за тази задача в темата дето си я постнал, но първо да довърша това.
Значи 15-на човека. Да предположим все пак, че г-н Стоянов е оптимист и я решат да кажем 10-тина.
Значи нац. ни отбор като цяло ще се справи с нея. И аз така мисля.
Сега да продължа от началния пост.
Задачата е давана на някакво състезание в латинска америка. Мястото е Аржентина, състезанието- IMO 2012, задачата е 3-та. Задачата убиец.
Исате ли да анализираме защо тя бе такова фиаско за почти всички участници, като много отбори получиха общо 0т. на нея. България има общо 7т. и то благодарение на само 1 участник- Богдан Станков.
Ключът към тази задача е "превода".

Явно под "превод" разбираш умението на ученика да си преформулира задачата.
За много трудни задачи преформулирането е ключ и оригиналната формулировка не е лесна за преодоляване. Друг интересен пример е петата задача от МОМ в Казахстан - ако беше формулирана с "да се докаже, че ...", резултатът щеше да е много по-различен. Що се отнася до буквалния превод - на големите състезания журито одобрява текст на английски, всички го превеждат на своите езици и преводите се окачват на табло. Оставя се време от няколко часа, в което всеки има право да преглежда чуждите преводи и да сигнализира за отклонения. След евентуална дискусия по отклоненията (ако има забелязани такива; действителни или не) журито гласува одобряване на преводите.

[drago]

Под "превод" разбирам да се трансформира задачата в друга еквивалентна по същество, така че плявата да се махне и да може да се работи по-лесно.
Тази е такава. Не всички обаче са такива. Тази на IMO 2011 за "мелницата" не е такава. При нея има само една идея или наблюдение, които решават всичко.
Taзи обаче, за лъжеца ми хареса повече. И знаете ли каква и е трудността. Че всеки почва в началото да я решава като логическа задача. Ето това е.Трябва да се разкара от нея всякаква обвивка, която има общо с лъжа/истина и т.н. , за да остане само една игра с множества. След което вече е много по-лесно.
Разбира се това, което съм написал или по-точно т.б) в този пост е "еквивалентна" само на първото подусловие на тази в Аржентина. (което май е носело 3т. като гледам резултатите). За второто трябва още една интерпретация.

[drago]

Koйто му е интересно може да види една по-добра оценка от това, което се искаше на б) подточка на 3-та от IMO Аржентина.
http://www.artofproblemsolving.com/Foru ... 7#p2853477