Вопрос пользователя:
Помогите хотябы какой нибудь сделать.
1. Коридор длины l покрыт конечным числом дорожек. Докажите, что можно убрать часть из них так, чтобы оставшиеся дорожки по-прежнему покрывали коридор и суммарная их длина не превышала бы 2l .
2. Клетки таблицы n x n заполнены числами 1.2…n так, что каждое число встречается ровно n раз. Докажите, что в некоторой строчке или в некотором столбце встречается не менее корень n различных чисел.
3. Камни, сложенные в n куч, собрали и разложили в n+k куч. Докажите, что не менее k+1 камня оказались в кучках меньших, чем те, в которых они лежали.
4. В 100-элементном множестве выбрано 101 трёхэлементное подмножество. Докажите, что найдутся два подмножества, пересекающиеся ровно по одному элементу.
5. Рёбра графа покрашены в d больше1 цветов так, что в любом пути из трёх различных рёбер (возможно, замкнутом) первое и последнее ребро окрашены в разные цвета. Докажите, что вершины графа можно правильным образом раскрасить в цветов
6. Дана бесконечная в обе стороны клетчатая полоска. Двое играют в “крестики-нолики”. Первый каждым ходом ставит три крестика, а второй два нолика. Сможет ли первый игрок поставить 100 крестиков подряд?
Илюха отвечает:
1. Ничего не понимаю. Может. есть еще условия? Или картинка?
Ведь конечным количеством может быть и одна – и в этом случае убрать сколько-нибудь так, чтобы оставшиеся покрывали коридор, очевидно, невозможно…
2. это уже было, решал
3. насчет куч и камней:
по идее, внутри этой задачи можно поднять не менее серьезную задачу о минимальном количестве камней в куче.
Ведь один камень – это же в строгом смысле не куча! И два камня – не куча.
Тут определить хорошо бы свойства кучи надо и потом, подкладывая по одному камню, наблюдать, при каком количестве камней эти свойства появляются…
но плюнем на этот важный вопрос и положим покамест, что минимум камней в куче – один. (очевидно ведь, что если где-либо камней нет вовсе – то о количестве куч на этой территории тем более речь вести невозможно)
Итак, минимум камней в куче – один.
Значит, для создания К куч необходимо минимум К камней. Они, естественно,
до того, как куч стало N+К,
лежали в тех N кучах.
Уже сейчас ясно, что эти К камней (из которых созданы К куч) оказались в кучах меньших, чем они лежали раньше. Ведь каждый из этих К камней раньше лежал в куче, содержавшей более одного камня (иначе при их извлечении те кучи исчезли бы).
Итак, К камней оказались в кучках меньших, чем те, в которых они лежали.
Но вот еще что: кучи, из которых взяты эти К камней тоже стали меньше, чем были вначале. Для того, чтобы использовать эти К камней, нужно извлечь их как минимум из одной кучи, которая при этом не исчеззла (в ней, значит, было более К камней.) Даже если в ней находился еще только один камень, – он так же после этого оказался в кучке меньшей, чем та, в которых он лежал ранее.
Вот и все: минимум камней, который после проведенной неутомимым составителем задач процедуры оказались в кучках меньших, чем те, в которых они лежали ранее = К+1. Это минимум по одному камню, лежещих ныне в каждой из К куч и минимум один камень в куче, откуда эти К камней “родом”
В чем и хотел убедиться экзаменатор!))
4. Сча подумаю
5. условия недописано – количество цветов для вершин не названо
6. непонятен… и ширина полоски неизветсна…
В чем проблема-то?
Пусть дети договорятся, что один ребенок ставит кресты в ряд в одну сторону, а другой нули выстраивает в другую. Тогда после 34 ходов у первого получится ряд из 102 крестов, который, несомненно, содержит цепочку из 100 крестов подряд…
Может, есть в моем понимании условий ошибка?