:: Игры Разума
Задача для 8-9 класса
rubinov
Автор

Сообщений: 483
Дата регистрации: 07.02.2005
Имеется 99 мешков. В каждом мешке - некоторое количество яблок и некоторое количество апельсинов. Доказать, что можно выбрать 50 мешков, в которых - не менее половины всех яблок и всех апельсинов.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
А мешки могут быть пустыми?


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
rubinov
Автор

Сообщений: 483
Дата регистрации: 07.02.2005
Нет.
"В каждом мешке - некоторое количество яблок и некоторое количество апельсинов".
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Что-то мне подсказывает что это не совсем корректное условие, или задача не для 8-9 классов
Если бы не было РАЗНЫХ объектов, то решение очевидно - берём произвольно 50 мешков, если там "меньше половины", то значит в оставшихся 49 будет "больше половины", и к ним для ровного счёта можно любой мешок перебросить - выходит задача для 3-го класса Но с объектами 2-х видов... Как говорится "нутром чую что литр а доказать не могу"
P.S. Хотя, наверное, разделив задачу на две половинки её и можно решить - если взять 25 мешков с "наибольшим" количеством яблок и 25 с наибольшим апельсин... Не к вечеру соображалка отказывает


------------------
WBR, Igor




Исправлено 1 раз(а). Последнее : Igor Korolyov, 27.09.10 20:00
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
rubinov
Автор

Сообщений: 483
Дата регистрации: 07.02.2005
Да, вопрос к задаче надо поставить: "....не менее половины всех фруктов". И тогда доказательство ведется от противного (что и ожидается).
А вот если с разными объектами, то наверное не для 8-9 класса.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Предположим, что утверждение задачи не верно. Выберем любые 49 мешков. В них обязательно будет одних фруктов больше половины, а других - меньше половины. (Остальные варианты элементарны). Рассмотрим все наборы из 49 мешков, в которых апельсинов меньше половины, и выберем из них тот, в котором апельсинов больше всего. Пусть A - общее количество апельсинов, S - количество апельсинов в выбранном наборе. Обозначим R=A/2-S. Это сколько апельсинов не хватает до половины. Тогда в каждом из оставшихся мешков апельсинов меньше R, иначе, добавив этот мешок к выбранным 49, получим противоречие с предположением. С другой стороны, в любом из оставшихся 50 мешков апельсинов не больше, чем в любом из выбранных 49. Если это не так, мы могли бы поменять мешки и получить набор из 49 мешков, в котором апельсинов больше максимума (но все равно меньше половины). Таким образом, если упорядочить мешки по апельсинам, выбранные 49 мешков будут располагаться в верхней части, а оставшиеся 50 - в нижней. Выберем из оставшихся 50 мешков тот, в котором апельсинов больше всего, и добавим его к выбранным 49. В получившихся 50 мешках яблок, естественно, будет больше половины, а апельсинов, стало быть меньше. Таким образом, 50 мешков с максимальным количеством апельсинов будут содержать меньше апельсинов, чем 49 мешков с минимальным количеством апельсинов. Это противоречие и доказывает, что утверждение задачи справедливо.

P.S. Думаю, эта задача все-таки не для 8-9 классов.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Ы-ы-ы сломал моск
Цитата:
С другой стороны, в любом из оставшихся 50 мешков апельсинов не больше, чем в любом из выбранных 49. Если это не так, мы могли бы поменять мешки и получить набор из 49 мешков, в котором апельсинов больше максимума
А что если при такой замене яблок станет меньше половины? Это уже совсем другой набор, не из "все наборы из 49 мешков, в которых апельсинов меньше половины"... Это вариант "апельсинов больше половины, а яблок меньше половины"... Хотя, тогда можно "вернуть" замененный мешок как 50-й и получить искомый набор.
Короче жуть!


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Igor Korolyov
Ы-ы-ы сломал моск А что если при такой замене яблок станет меньше половины? Это уже совсем другой набор, не из "все наборы из 49 мешков, в которых апельсинов меньше половины"... Это вариант "апельсинов больше половины, а яблок меньше половины"... Хотя, тогда можно "вернуть" замененный мешок как 50-й и получить искомый набор.
Короче жуть!
Не, Игорь, апельсинов точно будет меньше половины, поскольку "Тогда в каждом из оставшихся мешков апельсинов меньше R". А значит, яблок будет больше половины.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
pioner-v

Сообщений: 1656
Дата регистрации: 01.05.2010
rubinov
Имеется 99 мешков. В каждом мешке - некоторое количество яблок и некоторое количество апельсинов. Доказать, что можно выбрать 50 мешков, в которых - не менее половины всех яблок и всех апельсинов.

Наверное, в задаче предполагается, что яблок и апельсинов в каждом мешке "примерно" поровну.
В противном случае, можно предположить, что в каждом из 98 мешков находится по одному яблоку, а в 99-м мешке все остальные яблоки. Тогда вероятен случай, что 50 мешков не включает этот "99" мешок и, следовательно, более половины яблок будет в невыбранной порции.
Исходя из принципа примерного равенства, задача решается следующим образом:
1) Пусть во всех мешках находится М яблок и N апельсинов.
2) Тогда в одном мешке находится в "среднем" (М+N)/99 плодов.
3) В 50 мешках будет K=((M+N)/99)*50 плодов
4) Величина К больше, чем Р=((M+N)/100)*50=(M+N)/2, равной половине всех фруктов.

P.S. И еще. Мне кажется, что в задаче не утверждается, что выбранные 50 мешков должны содержать > 50% яблок и > 50% апельсинов. Скорее утверждается, что в выбранной "порции" будет более 50% от общего количества фруктов.



Исправлено 1 раз(а). Последнее : pioner-v, 28.09.10 16:01
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
Очевидно, что по условия задачи яблоки не отличаются от апельсинов.
Тогда 99 = 50+49. Очевидно, что в 50 мешках яблок и апельсинов будет больше, чем в 49.


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
pioner-v
Наверное, в задаче предполагается, что яблок и апельсинов в каждом мешке "примерно" поровну.
Не предполагается.

Влад Колосов
Очевидно, что по условия задачи яблоки не отличаются от апельсинов.
Не очевидно.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
leonid
Выберем любые 49 мешков. В них обязательно будет одних фруктов больше половины, а других - меньше половины.
Не факт.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
ry
leonid
Выберем любые 49 мешков. В них обязательно будет одних фруктов больше половины, а других - меньше половины.
Не факт.
Ну, мне казалось, что остальные варианты слишком тривиальны, чтобы объяснять. Если в в этих 49 мешках не меньше половины яблок и не меньше половины апельсинов, то добавим к ним еще один любой мешок и получим противоречие с предположением, что утверждение задачи неверно. Если в этих 49 мешках не больше половины яблок и не больше половины апельсинов, то возьмем оставшиеся 50 мешков, и опять получим противоречие.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
Разве нельзя допустить, что в 49 мешках больше апельсинов, чем в 50-ти, а в 50-ти больше яблок, чем в 49?
Вопрос в том, что переставляя мешки с известным количеством яблок и апельсинов можно удовлетворить условию.
Допустим, все яблоки находятся в 50 мешках, а все апельсины в 49. Тогда мы меняем 25 мешков местами и удовлетворяем условию.


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Влад Колосов
Допустим, все яблоки находятся в 50 мешках, а все апельсины в 49.
Задачу надо решить не только в этом случае, но также и во всех остальных. Только тогда она будет решена полностью.
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
ry
leonid
Выберем любые 49 мешков. В них обязательно будет одних фруктов больше половины, а других - меньше половины.
Не факт.
Есть 3 разных варианта. В выбранных 49 мешках:
1) >=50% апельсин И >=50% яблок - добавив любой другой мешок (даже пустой) мы выполняем условие задачи.
2) <=50% апельсин И <=50% яблок - очевидно это значит что в "оставшихся" 50 мешках как раз и находится требуемое по условию "большинство или равенство".
3) <50% апельсин И >=50% яблок - это мы и рассматриваем. Вариант когдя яблок меньше а апельсин больше, СОВЕРШЕННО аналогичен, "переименуй/перекрась" фрукты и решай дальше

Короче, нужно курить много бамбука, чтобы понять логику решения задачи


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
pioner-v

Сообщений: 1656
Дата регистрации: 01.05.2010
leonid
pioner-v
Наверное, в задаче предполагается, что яблок и апельсинов в каждом мешке "примерно" поровну.
Не предполагается.

Хочу уточнить. Я имею ввиду не примерное равенство яблок и апельсинов в одном мешке, а примерное равенство яблок в каждом мешке и примерное равенство апельсинов в каждом мешке...
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Вот объясни, зачем чего-то там "придумывать" чего нету в условии? Давай я "придумаю" что в каждом мешке ровно 1 яблоко и 1 апельсин, и на этом основании "решу" задачу
Условию удовлевторяет и "примерно равное", и "в 98 мешках по 1+1, а в 99-м по 1000 каждого", и обратное "в 98 мешках по 1000 каждого, а в 99-м всего по 1-му", и даже "в 49 мешках по 1 яблоку и 0 апельсинов, а в 50 оставшихся мешках по 1 апельсину и 0 яблок"... Сейчас я даже начал сомневаться имеет ли смысл моё уточнение насчёт пустых мешков, похоже даже для случая когда имеется всего 3 или 5 мешков задача решается точно так-же (главное чтобы их число было нечётным, а число "выбираемых" было на 0.5 больше точной половины).


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Goodwin

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Алъгорiтмъ:

for i=1 to 25
Из кучи берём мешок, где больше всего яблок
Из кучи берём мешок, где больше всего апельсинов
endfor


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive
Re: Задача для 8-9 класса
Goodwin

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Неверный.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 4 (Гостей: 4)

© 2000-2024 Fox Club 
Яндекс.Метрика