Задача с ЕГЭ по математике

bak19771

Пусть число S записано в виде суммы положительных чисел, не превосходящих 1.
Рассматривают такие S, любое представление которых допускает некоторое разбиение на 2 группы
причем любое слагаемое из S записано только в одну из двух групп такие, что сумма чисел в каждой группе не превосходит 15.
а) Может ли S=30; б) Может ли S быть больше (29+1/16); в) Чему равно максимальное S.
----------------------------------------
С а) понятно - можно привести представление S=0.9*33 + 0.3. Тогда суммы групп - 14.7 и 15.3.
Что-то не соображу никак, что с остальным ?

iri3955

б. Понятно, почему больше не может быть - делим на 31 равную часть и не можем разбить.
в. Это S и есть максимальное.
Будем использовать жадный алгоритм построения группы. Каждый раз добавляем туда максимальный элемент из оставшихся, оставляя сумму <= 15.
Тогда когда упрёмся мы полуим сумму S1 >= 15 - m, где m - минимальное число разбиения. Если m <= S / 31, то мы победили. Иначе в разбиении было меньше 31 элемента, а значит 30 (29 быть не может). Делим тогда на 2 группы по 15 (они все меньше 1).

mtk79

а) да
б) нет
в) 30+1/16

mtk79

Вам не рекомендуется проходить егэ

Yansloka

б) нет
в) 30+1/16
тут случайно нет противоречия? :o

bak19771

спасибо за б)! :)
По поводу в) - не мог бы объяснить чуть подробней этот момент

Тогда когда упрёмся мы полуим сумму S1 >= 15 - m, где m - минимальное число разбиения. Если m <= S / 31, то мы победили.

правильно ли я понял, что тут рассматриваются все разбиения с числом слагаемых >=31?
Для разбиения в 31 --- S=30*0.96+0.2625, S1=14.6625, S2=14.4, 15-m=14.7375, т.е. S1 >= 15 - m не выполняется (?)

mtk79

S_\max=(15+16)*15/16
а) и б) из него магически следуют

mtk79

тут случайно нет противоречия?
нет

toysert

ЯННП, можно для дурачков пояснить?

mtk79

но только для дурачков и ННП: егэ — предполагается, что это решать должны школьники, и всяк, кто себя причисляет к "окончившим школу с заслуженной пятеркой по математике", по моему скромному разумению, имеет полное право решить сию простую задачу самостоятельно, причем, начав с, собственно, и представляющего задачу случая "в".
"б" здесь вообще является прямой подсказкой

toysert

спасибо, о гуру, но "заслуженная пятерка" - это отнюдь не 100% решение всех задач, к тому же как известно, со временем часть знаний и навыков может быть утеряна, что усложняет решение даже простых задач, так что попрошу все-таки объяснения ответов.

mtk79

объяснение простое: аналогия с банками варенья, которые нужно расставить на полку, зазоры, вроде, есть — но их не удается собрать вместе, чтобы втиснуть еще одну банку.
Ну, или шары в миску.
наименее благодатный случай начинается тогда, когда шары по возможности большие и одинаковые, и начиная с некоторого следующий уже не влезает в миску, размер которой =15. Это происходит тогда, когда 15 шаров влезли, а 16-й уже никак. Что происходит при среднем размере шара >15/16.
О средних можно говорить, т.к. в неблагодатном случае достаточно привести один пример разбиения, не запихивающегося в обе миски.
Т.о. при при среднем размере шара=15/16 можно заполнить одну миску 16 шарами, вторую — 15-ю,
что дает число 31*15/16. Теперь остается доказать:
а) при S> 31*15/16 существует разбиение, не укладывающееся в обе миски (например, с 31 равными шарами)
б) S< 31*15/16 любое разбиение подходит. Здесь, наверное, предлагается поварьировать по паре x+y=сonst, x<1, y<1, и показать, что наименьшие шансы запихаться в миску — у равных шаров. Поэтому если шары проходят в среднем (т.е. все одинаковые) — а они проходят — то для любого отклонения от среднего шары зазиповываются и подавно.
Т.е. задачу с условным экстремумом в 31-мерном единичном кубе, наверное, решать не предполагается

Теперь, Вы, конечно, интересуетесь ответами а-в:
а) очевидно, секретарша при наборе ткнула не в ту кнопу ответа. Ей уже поставлено на вид, со строгим выговором
б) очевидно, секретарша при наборе ткнула не в ту кнопу ответа. Ей уже поставлено на вид, с понижением оклада
в) очевидно, досадная опечатка секретарши. Ее уже поставили на вид, с понижением головной и грудной частей тела

Thanhsoa

б) S< 31*15/16 любое разбиение подходит. Здесь, наверное, предлагается поварьировать по паре x+y=сonst, x<1, y<1, и показать, что наименьшие шансы запихаться в миску — у равных шаров. Поэтому если шары проходят в среднем (т.е. все одинаковые) — а они проходят — то для любого отклонения от среднего шары зазиповываются и подавно.
Ну вот это не решение же. Т.е. если бы такой текст был в работе на олимпиаде, то был бы чистый минус. Решение - это взять алгоритм и выписать аккуратно оценочки.

bak19771

а) при S> 31*15/16
б) S< 31*15/16

И из этого должно следовать что? Где максимум? Достаточно в б) рассмотреть один случай при равенстве и доказать.
В этом-то и прикол задачи - чтобы показать, что что-то не подходит, достаточно привести один пример. Это легко. А вот доказать, что подходит - нужен способ учета всех вариантов. Я поэтому б) не решал - решение пунка в) решает всю задачу.
егэ — предполагается...

Какая разница егэ не егэ? В мое время егэ не проводилось, так что интерес предствляет просто сравнить с тем, что было у нас. А так, это такая же задачка, как любая другая. Какой-то бред, что пытающийся её решить должен ассоциировать себя со школьником или бывшим отличником по математике:crazy:
зы Лично я подобных задач в школе не решал, но со вступительными никогда больших проблем не испытывал, хотя и не олимпиадник. Просто любопытно. Тут нужно только идейку правильную подкинуть, дальше любой сам сделает. Не пойму, честно говоря, почему такой ступор :( :D
В задачах С6 действительно составители часто уже указывают ответ - 29.0625, в данном случае. Типо нужно только доказать. Но че-то непонятно пока.. :) Это ж на школьников рассчитано) Пока только сделал конкретную попытку доказать, но то ли ошибся, то ли я чето не понял.
наверное, предлагается поварьировать по паре x+y=сonst, x<1, y<1, и показать, что наименьшие шансы запихаться в миску — у равных шаров

это пока лишь гипотеза. собсна и у меня такая мысль мелькала, но.. хочется увидеть строгое док-во

mtk79

Берите алгоритм и выписывайте оценочки. Ставьте себе чистый плюс. Никто не против. Нас потом просветите, что получилось.
Алгоритм и т.д. действует, когда разбиение уже есть. Для S<S_{\max} нужно доказать, что для любого разбиения...
Давайте, для предметности, возьмите S=29+1/32 и выпишите оценочки. Без привлечения всяких штук из высшей школы
ПС. При выводе я исходил из наибольшего зазора, могущегося образоваться при заполнении одной миски. И получил ответ б). (А не наоборот!). Т.е. к ответу привела некоторая аргументация.
 Поэтому и считаю сие решением, что такой подход (если его доказать, что проще, чем связываться с двумя мисками) дает inf{недостижимости}, взяв дополнение к которому получится sup{достижимости}

bak19771

 
Для S<S_{\max} нужно доказать, что для любого разбиения

Во второй раз пишу. Для чего рассматривать меньше? В пункте б) задачи легко доказывается, что при S>29.0625 не получается - с помощью разбиения, про которое сказал. Дальше нужно только показать, что при S=29.0625 все выполнятся => будет следовать, что это максимум. Для чего рассматривать случаи меньше 29.0625?... ;)
Алгоритм и т.д. действует, когда разбиение уже есть.

Кстати, это может быть. У меня пока с помощью этого алгоритма не получилось. И, собственно, никаких полезных оценок вывести тоже не вышло.
Как я понимаю, тут возможны три подхода решения. Взять годный алгоритм, наподобие жадного и.. может быть получится. Второй - взять разбиение на группы, в котором одна из сумм >15 и с помощью каких-то изначальных предположений показать, что можно свести такое разбиение к годному. Может, комбинация этих двух.. Ну а третий - как-то учесть все разбиения через оценку - по типу того, что среди них есть какой-то класс, для которого если выполняется, то выполняется для всех остальных - наподобие среднеарифметических.. А может разбиение по 15/16 в каком-то смысле оптимально и если оно годно, то и все остальные годны.. Не знаю - я каждый день понемногу обдумываю эту задачу, но пока тока мозг пухнет и ниче больше :grin:

mtk79

ну, это одно и то же. Возьмите тот самый S =S_{\max}
Из того, что написал __ — это прекрасно. Но из этого следует, что в S1 будет не менее 15-m, и в S2 будет не менее 15-m. В сумме будет не менее 30-2m.
То, что m<=S/31 (для разбиения на 31, ибо остальные тривиальны (30 — это очевидно и так. Из этого всего следует, что
макс. S — не более 30*31/29. Но это и так очевидно.

bak19771

Мое удивление связано с тем, что я прорешивал несколько видов C6 2012 года и все они решались на ура. В плане стоит, что на решение С6 у абитура должно уходить 40 мин с оформлением. Именно это я и наблюдал у себя - т.е. это вполне реально, нормальные текстовые задачки - немного логики и решение занимает строчек 6, без учета объяснений. Там в тестах были и посложнее, хотя за них дается меньше баллов. Эта же задача как-то выпадает

bak19771

Но из этого следует, что в S1 будет не менее 15-m, и в S2 будет не менее 15-m

В том-то и дело, я привел выше пример. Если исходить из того, что написал , а именно
Каждый раз добавляем туда максимальный элемент из оставшихся, оставляя сумму <= 15

и m- минимальное число разбиения, то такая оценка неверна (пример привел).
То, что я ссылался на его пост, так это доказательство пунка б).
Кроме того
для разбиения на 31, ибо остальные тривиальны (30)

почему не рассматриваются разбиения 32 или 33, например? Во всяком случае указания\доказательства, что нужно только 30 и 31 никто не привел.

iri3955

Поясню, что я имел ввиду.
S = 29 + 1/16
S1 >= 15-m
m <= S/31 = 15/16
Это значит, что S1 >= 14 + 1/16 (но всё еще меньше 15).
Тогда S2 = S - S1 <= 15

Thanhsoa

m <= S/31
Вот это мне не очевидно. Т.е. у меня в решении рассуждения, отметающие вариант m > S/31, не являются одноходовыми.

iri3955

Если кол-во элементов рабиения >= 31, то минимальный <=31.
Если же кол-во элементов < 31 (то есть =30 то делим на 2 любые группы по 15.

Thanhsoa

Если кол-во элементов рабиения >= 31, то минимальный <=31.
А почему минимальный уже не в S1? Может он был как раз добавлен на предыдущем шаге?

bak19771

Поясню, что я имел ввиду.
S = 29 + 1/16
S1 >= 15-m
m <= S/31 = 15/16
Это значит, что S1 >= 14 + 1/16 (но всё еще меньше 15).
Тогда S2 = S - S1 <= 15

Я понимаю происходящее так. По алгоритму мы заполняем сумму S1, каждый раз кидая туда максимальный и прекращаем, когда очередной делает сумму больше 15. В таком случае про S1 наверняка можно сказать только, что S1>=14. Кроме того, S2 может оказаться больше 15.
Если же на каждом шаге мы кидаем туда максимальный из возможных, то тогда S1>=15-m, но m в этом случае - минимальный из оставшихся неиспользованных. И если мы заменим в неравенстве
это m на минимальный разбиеня вообще, то неравенснство станет неверным, особенно если неравенство строгое (для конкретного разбиения).
Теперь, оценка m <= S/31 = 15/16 — верна в принципе для минимального элемента всех разбиений, количеством элементов 31 и больше.
Связать все это вместе и сделать дальше какой-то вывод не получается..

mtk79

отвечая на все вопросы скопом, я и предлагал свести задачу к НАИБОЛЕЕ неблагоприятному случаю, когда существует наибольший зазор. Это и будет означать, что все, что за пределами — уже благоприятно.
Редуцировать задачу предлагаю к одной миске:
Задача-лемма: даны M штук одномерных шариков, размером от 0 до 1 каждая, их нужно запихать в миску размером N, при этом сумма всех M шаров = N+0 (сколь угодно малое эпсилон). Для данной расфасовки Т шары запихиваются так, чтобы зазор d был минимален.
Каково наибольшее значение зазора d, и какова конфигурация T? (т.е. некоторый принцип максимина)
Ответ очевиден, решение интуитивно
а) d=N / M-0
(минимальный шар m > d, при этом m<среднее q, тогда максимальное d будет когда m как можно ближе к q, т.е. при равном разбиении)
б) M=N+1,
(при увеличении M d ,будет падать. Грубо говоря: чем больше шаров — тем меньше они в среднем, тем проще из расфасовать)
T: все шары одинаковы размера d=m=N/(N+1) +0
для двух шаров можно доказать обычным экстремумом.
далее- может, по индукции
Для двух мисок — то же самое.
Затем устремляем эпсилон к 0 и заключаем, что в пределе можно запихнуть еще один шарик, не нарушая условий задачи. Получается некая конфигурация, соотв. наибольшему зазору в одном миске, кою нужно поисследовать на устойчивость. Теперь предлагается поварьировать в 31-мерном пространстве (на плоскости сумма =константин) — но только в окрестности точки устойчивости. Предполагается, что малому возмущению координат будет соответствовать малое значение |макс. шар - мин. шар|, после чего для любого возмущения можно бОльшие шары переставлять в миску, где есть зазор, ибо зазор конечен, а отклонение от равновесия — мало.
Хотя если при этом неравенства появятся — конечно, выглядеть будет более научно

mtk79

Тогда S2 = S - S1 <= 15
здесь предполагается, что все шарики уже поместились в S2. Хотя S2 ничуть не хуже S1

iri3955

Да, чот этот момент я упустил.
Тогда рассмотрим момент, когда S1 перевалила за 14 (то есть стала 14 + a, считаем, что a < 1/16).
До этого мы туда пихали всегда максимальнй элемент.
Далее, мы туда бросим сколько-то элементов по тому же принципу, в том числе и минимальный.
S1 в этом случае будет меньше 14 + 1/16 (иначе всё хорошо, решение получено).
Тогда все оставшиеся элементы > 1 - a > 15/16 (иначе бы в S1 пошли они, а они не влезли).
Объелиним все маленькие числа (добавленные после достижения 14 + a) в одно. Оно меньше 1/16,
все остальные > 15/16, тогда чисел ровно 31 (если их больше, то сумма будет больше S тогда делим большие числа на две кучки по 15,
а оставшееся кидаем в меньшую.
Наверное, можно проще этот случай доказать

iri3955

Здесь ничего не предполагается. Я просто упустил случай, про который написали выше.

Thanhsoa

Ага, я рассуждал так:
Пусть m > S/31 = 15/16. Заметим, что в S1 содержится как минимум первые 15 максимальных элементов из разбиения S (т.к. каждый из них <=1). Далее, заметим, что в S2 = S\S1 остается как минимум 16 элементов (если их там меньше, то сумма по S2 <= суммы по S1 <= 15 и построение успешно). Теперь, имеем как минимум 16 элементов в S2, каждый из которых не меньше m и как минимум 15 элементов в S1, каждый из которых не меньше любого из S2, а значит не меньше m. Тогда сумма по S1 и S2 не меньше 31*m > S, что противоречит построению.

ruslan80

ЕГЭшную задачку обсуждают уже две страницы. Куда скатился МГУ :(

lenmas

ЕГЭшную задачку обсуждают уже две страницы. Куда скатился МГУ :(
Тут скорее скатился, что вообще обсуждает тупое егэ :)
Оставить комментарий
Имя или ник:
Комментарий: