Задача от Канадска МО

[drago]

На масата са нахвърляни [tex]15[/tex] списания, които я покриват изцяло. Докажете, че можем да махнем [tex]7[/tex] от тях, така че останалите да покриват поне [tex]\frac{8}{15}[/tex] части от повърхността на масата.

[inveidar]

Вярно ли е условието на задачата, ако списанията са с различни размери? Не би ли трябвало да се каже, че са еднакви?

[drago]

Списанията са най различни и формата им не е съществена.

[inveidar]

Да предположим първо, че всяко списание има допирна площ с масата. Тогава можем да смятаме, че масата е разделена на 15 или по-малко части. Това са общите части между списанията и масата, като ако две или повече списания се припокриват в някаква част, то общата им част минава към по-голямото по площ списание. Остава да махнем седемте най-малки по площ части(всъщност седемте им съответстващи списания!), оставащите със сигурност ще покриват част от масата, която е по-голяма или равна на осем петнадесети.
Ако някое списание няма обща допирна площ с масата, то спокойно го махаме и така докато махнем всички такива. Ако е само едно, то масата е разделена на 14 части и остава да махнем 6-те най-малки. Останалите са повече от осем четиринадесети, а значи и от осем петнадесети. Ако са две списания за махане, то остават 13 и махаме петте най-малки части и т.н.

[drago]

Като идея е нещо такова, но не ме удовлетворява строгостта на обяснението. Ето това:
"...можем да смятаме, че масата е разделена на 15 или по-малко части. Това са общите части между списанията и масата, като ако две или повече списания се припокриват в някаква част, то общата им част минава към по-голямото по площ списание..."
Нека множествата, които покриват списанията са [tex]A_1, A_2,\ldots , A_{15}[/tex], а масата [tex]T[/tex]. Как точно конструираш тези "15 или по-малко части" ? Обясни го формално!

[inveidar]

Не смятам, че е необходимо, но за да удовлетворя желанието ти ето така:
Означавам с [tex]S _ {i}[/tex] i-тото списание, разгледано като множество. Нека [tex]S _ {i} \cap S _ {j} =S_{ij}[/tex] и [tex]S _ {i}\le S _ {j}[/tex]. Тогава [tex]A _ {i}= S _ {i}-S_{ij}[/tex], а [tex]A _ {j}= S _ {j}[/tex]. Минусът означава "без". Мислиш ли, че така става по-ясно? Предпочитам да го обясня на учениците с картинки.

[inveidar]

Обясни го формално!

Не разбрах и за какво е удивителната?

[pal702004]

Не виждам какво му е олимпиадното на тази задача. В края на краищата се свежда до тривиалното: Ако сумата на 15 неотрицателни числа е 1, то сумата на най-малките 7 от тях е не по-голяма от [tex]\frac{7}{15}[/tex]
Числата са "полезната" площ на всяко списание, може и да е 0.
Може да е утешителна задача, а може и да не сме разбрали правилно условието.

[drago]

Не виждам какво му е олимпиадното на тази задача. В края на краищата се свежда до тривиалното: Ако сумата на 15 неотрицателни числа е 1, то сумата на най-малките 7 от тях е не по-голяма от [tex]\frac{7}{15}[/tex]
Числата са "полезната" площ на всяко списание, може и да е 0.

Точно до това се свежда, но кои са тези 15 неотрицателни числа? И какво означава "полезната" площ?

Означавам с [tex]S _ {i}[/tex] i-тото списание, разгледано като множество. Нека [tex]S _ {i} \cap S _ {j} =S_{ij}[/tex] и [tex]S _ {i}\le S _ {j}[/tex]. Тогава [tex]A _ {i}= S _ {i}-S_{ij}[/tex], а [tex]A _ {j}= S _ {j}[/tex].

Добре, нека следваме твоята дефиниция. Нека [tex]S_1<S_2<S_3[/tex]. Ако разгледаме [tex]S_1,S_2[/tex] според теб трябва [tex]A_2[/tex] да е равно на [tex]S_2[/tex]. Ако сега разгледаме [tex]S_2,S_3[/tex] според теб трябва [tex]A_2[/tex] да е [tex]S_2-S_{23}[/tex]. И така въпросът е: кое точно е [tex]A_2[/tex]? Иначе хубаво е да се обясни с картинки, но да е правилно!

Също смятам, че задачата не е трудна. Обаче е поучителна как да обличаме интуицията си в правилни формални разсъждения.

[pal702004]

И какво означава "полезната" площ

"Полезната" площ означава площта от масата, покрита именно от това списание. Ако по ти харесва, площта от списанието в пряк допир с масата. Очевидно е какво се има предвид, Драго. Търсиш под вола теле.

[inveidar]

Означавам с [tex]S _ {i}[/tex] i-тото списание, разгледано като множество. Нека [tex]S _ {i} \cap S _ {j} =S_{ij}[/tex] и [tex]S _ {i}\le S _ {j}[/tex]. Тогава [tex]A _ {i}= S _ {i}-S_{ij}[/tex], а [tex]A _ {j}= S _ {j}[/tex].

Добре, нека следваме твоята дефиниция. Нека [tex]S_1<S_2<S_3[/tex]. Ако разгледаме [tex]S_1,S_2[/tex] според теб трябва [tex]A_2[/tex] да е равно на [tex]S_2[/tex]. Ако сега разгледаме [tex]S_2,S_3[/tex] според теб трябва [tex]A_2[/tex] да е [tex]S_2-S_{23}[/tex]. И така въпросът е: кое точно е [tex]A_2[/tex]?

Добре де. Ще го мислим допълнително.
Нека първо всяко списание има допирна площ с масата. Нека още списанията [tex]S_{i}, S_{j}, S_{k}[/tex] имат обща площ и [tex]S_{i}< S_{j}<S_{k}[/tex]. Тогава [tex]A_{k}=S_{k}, A_{j}=S_{j}-(S_{j}\cap A_{k}) , A_{i}= S_{i}-(S_{i}\cap A_{k}) -(S_{i}\cap A_{j})[/tex]. Така по-добре ли е?

ddd.png (12.37 KiB) Прегледано 692 пъти

[kmitov]

И аз имам едно предложение. Само не ме псувайте, че ми омръзна.


Ако номерираме списанията с номера от 1 до 15 и означим с [tex]M_i[/tex] множеството от точки на масата, които са покрити само от списанието с номер i, (тук за да не възникват спекулации 'покрити' от списание с номер i означава точно това, което се има в предвид под 'покрити' в условието на задачата).

Тези множества са непресичащи се и поради това, че са налице 15 правоъгълника, множествата [tex]M_i[/tex] са многоъгълници или празни множества, но във всеки случай са измерими (имат лице).

Ако [tex]S_i[/tex]=лицето на [tex]M_i[/tex], то числата [tex]S_i \ge 0[/tex] и можем да ги наредим по големина в нарастващ ред така [tex]S_{(1)} \le S_{(2)} \le \ldots \le S_{(15)}[/tex].

Освен това [tex]S_0=\sum_{i=1}^{15} S_{(i)} \le S[/tex], където [tex]S[/tex] е лицето масата.

Да махнем онези списания, които съответстват на първите 7 числа във вариационния ред (най-малките). Тогава ще се открие частта от масата [tex]M_{(1)} \cup M_{(2)} \ldots \cup M_{(7)}[/tex], чието лице е [tex]\sum_{i=1}^7 S_{(i)} \le \frac{7}{15}S_0 \le \frac{7}{15}S[/tex].

[drago]

Предлагам да не се използват думичките "пряк допир", "допирна площ" и др. био-зоо-... речников фонд, щото много издишат.
Имаме някакви множества примерно [tex]S_1,S_2,\ldots, S_{15}[/tex]. Имаме и друго[tex]T[/tex]. Известно е:[tex]T\subset \bigcup_{i=1}^{15} S_i[/tex].
Нататък трябва да се направи някаква конструкция, (напр. да се изберат исканите 7 множества по някакъв алгоритъм) така че да ме убедите в твърдението.
Това, което казва Митов: [tex]M_i[/tex] да е множеството от точки покрити само от [tex]S_i[/tex]. Ами тогава може всички [tex]M_i[/tex] да са празни!!
И да ви кажа не се заяждам, това не са лапсуси или леко неправилно изразяване. Всичко това отгоре са просто неточни (разбирай неправилни) "решения", на които може да се даде 2т. за нещо като правилна идея.

P.S. Всъщност може би разбирам, какво има предвид Митов, но напиши го с горната терминология, за да не се налага обяснения от сорта: "...тук за да не възникват спекулации 'покрити' от списание с номер i означава точно това, което се има в предвид под 'покрити' в условието на задачата..."

[kmitov]

И какъв е проблема, ако всичките са празни?

[kmitov]

И защо в решението на задачата да не се ползва същата :терминология, като е условието?

[inveidar]

Предлагам да не се използват думичките "пряк допир", "допирна площ" и др. био-зоо-... речников фонд, щото много издишат.

Е, не си прав, Драго! Това е задача от олимпиада. Както каза Митов(и аз да се съглася един път с него!), не е проблем да се използва терминологията от условието. Даже е желателно, когато задачата се обяснява на ученици да става точно по този начин. Ти по-добре кажи къде ни е грешката, ако имаме такава? Аз не виждам проблем в обяснението ми с картинката.

[kmitov]

Благодаря!

[drago]

Нещо леко започнах да отегчавам от това преливане от пусто в празно.
Нямам против кой както иска да го обяснява, стига да няма двусмислици.

И какъв е проблема, ако всичките са празни?

@Митов: Мислех че нещо си зацепил, но след този въпрос виждам, че съм сбъркал.
@Инвейдър: В обяснението с картинката всичко е ОК, но има един малък проблем. Конструкцията е за ТРИ множества/списания/. А за 15 как ще процидираме? По тройки ли ще прилагаш това? Така ще стане същата боза, като по двойки. Ако имаш правиш нещо друго- какво е то? И не ми обяснявай как трябва да се обяснява на ученици, щото ми писна от тази педагогика, дето пробутваш. Защото преди всичко трябва да им се обяснява вярно.
Имам чувство, че не говоря с хора, които имат математически тертип на мислене. Толкова ли е трудно да се направи тази конструкция както трябва?!

[kmitov]

Благодаря за зацепването. Ще чакам истинското решение. Да сте живи и здрави.

[inveidar]

Ами по същия начин, както с три, бе, Драго. Аз съм дал примерно 3. С четири е същото, с пет пак така. Кажи къде е грешката а недей да се нервиш, защото си си втълпил в главата, че трябва да ни научиш как да обличаме разсъжденията си формално. И на мен ми писна вече от твоя менторски тон. Пробутвам ти педагогика, айде бе. От къде накъде ще знам аз педагогика? И ще си обяснявам каквото си искам и на който си искам. Кой си ти всъщност, че да ми забраняваш? Не се ли увличаш малко? Ако не ти изнася, не се включвай, твой проблем.
За да мирясаш ще ти пусна едно решение без припокриващи се списания.
Първо, ако списание стърчи извън масата, го изрязваме с ножичка! Така върху масата с лице S остават 15 "списания"(кавичките слагам, защото някои от тях са изрязани по краищата!), които покриват точно площ S. Ще докажем, че можем да махнем едно списание и оставащите 14 да покрият площ по-голяма или равна от [tex]\frac{14}{15 }S[/tex]. Ако допуснем, че което и списание от 15-те да махнем, то оставащите покриват площ по-малка от [tex]\frac{14}{15 }S[/tex], то това означава, че всяко едно от петнадесетте списания има площ по-голяма от [tex]\frac{1}{15 }S[/tex], а всичките заедно - по-голяма от [tex]15.\frac{1}{15 }S[/tex]=[tex]S[/tex], което е невъзможно след изрязването, нали? И така, можем да махнем едно списание и останалите 14 покриват площ, по-голяма или равна на [tex]\frac{14}{15 }S[/tex]. Аналогични разсъждения ни водят до факта, че от останалите 14 мога да махна още едно така, че останалите 13 да покрият площ по-голяма или равна на [tex]\frac{13}{14 }S_{1}[/tex], където с [tex]S_{1}[/tex] означаваме площа покрита от останалите от първото махане 14. При това площа, която покриват 13-те е по-голяма или равна на [tex]\frac{13}{14 }S_{1}[/tex][tex]\ge[/tex] [tex]\frac{13}{14 }.\frac{14}{15 } S=\frac{13}{15 }S[/tex]. Този процес продължаваме още пет пъти и готово.
Ако обичаш, преди да кажеш нещо за това решение, да помислиш малко. Става ли?

[inveidar]

Имам чувство, че не говоря с хора, които имат математически тертип на мислене. Толкова ли е трудно да се направи тази конструкция както трябва?!

Да, трудно и излишно за задача, която може да се реши и от седмокласник. И е време да разбереш, че не всички сме гений като теб и в това няма нищо лошо.

[kmitov]

Сетих се за следния частен случай и реших да го кажа. Ако масата е 1х1 м. и всички списания са 1х1 м и са наредени едно върху друго на масата така, че никое не стърчи отвън, какви ще са множествата М_i, (според мен празни), какви ще са техните лица (според мен всичките ще са 0) и каква част от масата ще остане покрита ако махнем 7 от тях (според мен цялата, което е повече от 8/15)?

[inveidar]

Сетих се за следния частен случай и реших да го кажа. Ако масата е 1х1 м. и всички списания са 1х1 м и са наредени едно върху друго на масата така, че никое не стърчи отвън, какви ще са множествата М_i, (според мен празни), какви ще са техните лица (според мен всичките ще са 0) и каква част от масата ще остане покрита ако махнем 7 от тях (според мен цялата, което е повече от 8/15)?

Митов, зарежи тия множества и виж другото решение!

[inveidar]

Нещо все ме дърпа към покривките! От всички припокривания на масата, които са краен брой, защото списанията са 15, има едно с най-много пласта един върху друг. Почвам от него с познатата от картинката процедура, но не за три, а за колкото са пластовете. Оправяме го това припокриване и там вече има само един пласт списания. Минаваме на следващото припокриване с най-голям брой пласта и оправяме и него. Така ги оправяме всичките и след това е ясно. Как е сега, става ли така?

[inveidar]

http://www.artofproblemsolving.com/Foru ... 1#p3484231
Това е решението на Драго.