2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 15:46 
Продолжаю свою практику с решением олимпиадных задач. Тема принцип Дирихле. В задачах, где нужно что-то доказать, совсем туго. Где есть решение - правильное ли? Где нету - хотелось бы увидеть от вас.

1. В классе 30 учеников. Во время контрольной работы Петя сделал 13 ошибок, а остальные меньше.
Докажите, что найдутся три ученика, сделавшие одинаковое число ошибок.
*Тут нельзя с уверенностью сказать, так как различных вариантов кол-ва ошибок $14$, а $30/14<3$ ?


2. На Земле больше шести миллиардов жителей, людей старше 150 лет не существует. Докажите, что на
Земле есть два человека, родившихся одновременно с точностью до секунды.
*Тут надо 6 миллиардов разделить на $150\cdot366\cdot24\cdot60\cdot60$. Если результат будет $\geqslant2$, то доказано?

3. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15◦.
* ?

4. В ящике лежат носки: 10 чёрных, 10 синих, 10 белых. Какое наименьшее количество носков надо вынуть не глядя, чтобы среди вынутых оказалось два носка а) одного цвета; б) разных цветов; в) чёрного цвета?
*Если отбросить вариант с одного раза, то a) $11$? б) $6$? в)$11$? А как доказывать красиво?

5. На карьере добыли 36 камней. Их веса составляют арифметическую прогрессию: 490 кг, 495 кг, 500 кг, . . . , 665 кг. Можно ли увезти эти камни на семи трёхтонных грузовиках?
*$S_{36}=20790$, $S_{36}<21 тонны$. Можно. Так?

6. Какое наименьшее число карточек спортлото «6 из 49» надо купить, чтобы наверняка хоть на одной
из них был угадан хоть один номер?
*Вообще не понимаю что это.

7. Докажите, что среди любых пяти человек есть двое с одинаковым числом знакомых среди этих пяти человек. (Возможно, эти двое ни с кем не знакомы.)
*А как же вариант, когда один человек имеет двух знакомых среди этих 5, а другой - 0. Или я что-то не понимаю.

8. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100.
*?

9. Квадратная таблица (2n+1)×(2n+1) заполнена числами от 1 до 2n+1 так, что в каждой строке и в каждом столбце представлены все эти числа. Докажите, что если это расположение симметрично относительно диагонали таблицы, то на этой диагонали тоже представлены все эти числа.
*?

10. В классе 25 человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.
*?

11. Комиссия из 60 человек провела 40 заседаний, причём на каждом присутствовало ровно 10 членов комиссии. Докажите, что какие-то два члена комиссии встречались на её заседаниях по крайней мере дважды.
*?

12. Каждая из 9 прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2 : 3. Докажите, что по крайней мере три из этих прямых проходят через одну точку.
*?

13. Первоклассник Петя знает только цифру 1. Докажите, что он может написать число, делящееся на 1989.
*А арифметических знаком он не знает?)

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 16:16 
ZARATUSTRA в сообщении #584418 писал(а):
3. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15◦.
* ?
параллельным переносом (что вроде не меняет угол между прямыми) проведем все прямые через единственную точку. И получицца ... сколько углов?

ZARATUSTRA в сообщении #584418 писал(а):
4. В ящике лежат носки: 10 чёрных, 10 синих, 10 белых. Какое наименьшее количество носков надо вынуть не глядя, чтобы среди вынутых оказалось два носка а) одного цвета; б) разных цветов; в) чёрного цвета?
*Если отбросить вариант с одного раза, то a) $11$? б) $6$? в)$11$? А как доказывать красиво?
Хм, давайте сначала "некрасиво" объясните...

ZARATUSTRA в сообщении #584418 писал(а):
5. На карьере добыли 36 камней. Их веса составляют арифметическую прогрессию: 490 кг, 495 кг, 500 кг, . . . , 665 кг. Можно ли увезти эти камни на семи трёхтонных грузовиках?
*$S_{36}=20790$, $S_{36}<21 тонны$. Можно. Так?
Этого неравенства недостаточно например 9т, 9т и 2т в 7тонный не поместяцца!

ZARATUSTRA в сообщении #584418 писал(а):
6. Какое наименьшее число карточек спортлото «6 из 49» надо купить, чтобы наверняка хоть на одной
из них был угадан хоть один номер?
*Вообще не понимаю что это.
Игрок может зачеркнуть 6 чисел из 49 чисел. Потом какие то 6 чисел (в результате розыгрыша) оказываются "правильными". Вам надо гарантированно зачеркнуть 1 правильный номер на одной из карточек


ZARATUSTRA в сообщении #584418 писал(а):
8. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100.

А сколько там остатков то? А в сумме или разности?


ZARATUSTRA в сообщении #584418 писал(а):
13. Первоклассник Петя знает только цифру 1. Докажите, что он может написать число, делящееся на 1989.
*А арифметических знаком он не знает?)
Имеется в виду что он пишет стопицотзначное число из единичек. Арифм знаков не знает

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 16:18 
Аватара пользователя
11. $40 \cdot \frac {10 \cdot 9} 2 > \frac {60 \cdot 59} 2.$
13. Арифметические знаки ему и не нужны. Взять эту единицу и поделить столбиком на $1989$. Рано или поздно остатки начнут повторяться, причём первым повторится остаток $1$ на $n$-м шаге. Взять число, составленное из $n$ единиц. Оно будет гарантированно делиться на $\frac {1989} 9$. Если не делится на $9$, то написать это число $9$ раз подряд. Для примера можно заменить $1989$ на $7$ - $111111$ делится на $7$.

(Оффтоп)

Тему логичнее было озаглавить не "Пару простых задач на принцип Дирихле", а "Чёртова дюжина простых задач на принцип Дирихле". :-)

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 16:20 
VoloCh в сообщении #584424 писал(а):
ZARATUSTRA в сообщении #584418 писал(а):
3. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15◦.
* ?
параллельным переносом (что вроде не меняет угол между прямыми) проведем все прямые через единственную точку. И получицца ... сколько углов?

ZARATUSTRA в сообщении #584418 писал(а):
4. В ящике лежат носки: 10 чёрных, 10 синих, 10 белых. Какое наименьшее количество носков надо вынуть не глядя, чтобы среди вынутых оказалось два носка а) одного цвета; б) разных цветов; в) чёрного цвета?
*Если отбросить вариант с одного раза, то a) $11$? б) $6$? в)$11$? А как доказывать красиво?
Хм, давайте сначала "некрасиво" объясните...

ZARATUSTRA в сообщении #584418 писал(а):
5. На карьере добыли 36 камней. Их веса составляют арифметическую прогрессию: 490 кг, 495 кг, 500 кг, . . . , 665 кг. Можно ли увезти эти камни на семи трёхтонных грузовиках?
*$S_{36}=20790$, $S_{36}<21 тонны$. Можно. Так?
Этого неравенства недостаточно например 9т, 9т и 2т в 7тонный не поместяцца!

ZARATUSTRA в сообщении #584418 писал(а):
6. Какое наименьшее число карточек спортлото «6 из 49» надо купить, чтобы наверняка хоть на одной
из них был угадан хоть один номер?
*Вообще не понимаю что это.
Игрок может зачеркнуть 6 чисел из 49 чисел. Потом какие то 6 чисел (в результате розыгрыша) оказываются "правильными". Вам надо гарантированно зачеркнуть 1 правильный номер на одной из карточек


ZARATUSTRA в сообщении #584418 писал(а):
8. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100.

А сколько там остатков то? А в сумме или разности?


ZARATUSTRA в сообщении #584418 писал(а):
13. Первоклассник Петя знает только цифру 1. Докажите, что он может написать число, делящееся на 1989.
*А арифметических знаком он не знает?)
Имеется в виду что он пишет стопицотзначное число из единичек. Арифм знаков не знает

К вечеру напишу, что получилось. Спасибо.

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 16:42 
ZARATUSTRA в сообщении #584418 писал(а):
1. В классе 30 учеников. Во время контрольной работы Петя сделал 13 ошибок, а остальные меньше.
Докажите, что найдутся три ученика, сделавшие одинаковое число ошибок.
*Тут нельзя с уверенностью сказать, так как различных вариантов кол-ва ошибок $14$, а $30/14<3$ ?
Можно сказать с уверенностью. Во-первых, не 30, а 29; во-вторых, не 14, а 13; в-третьих, не $< 3$, а $> 2$.

ZARATUSTRA в сообщении #584418 писал(а):
2. На Земле больше шести миллиардов жителей, людей старше 150 лет не существует. Докажите, что на
Земле есть два человека, родившихся одновременно с точностью до секунды.
*Тут надо 6 миллиардов разделить на $150\cdot366\cdot24\cdot60\cdot60$. Если результат будет $\geqslant2$, то доказано?
Да, доказано. Причем с очень большим запасом. Но Вам так доказать не удастся, ибо результат будет меньше 2. На самом деле, достаточно доказать, что частное $> 1$.

Возьмите для примера 3 кролика и две клетки.

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 17:40 
Это пару задачек?)
1. Выкиньте Петю - он единственный у кого 13 ошибок. У остальных будет от 0 до 12 ошибок, а человек будет 29.
2. Нет, вы неправы - необходимо, чтобы было хотя бы больше единицы.
3. Вот уже сказали - параллельным переносом сдвиньте все прямые, чтобы они проходили все через одну точку. Посчитаете кол-во углов и примените принцип Дирихле
4. Нет, причём везде неправильно. Рассмотрите худший случай... и допишите в задаче очень важное слово "гарантированно"
5. Нет, нельзя! Докажите, что какая-то трёхтонка повезёт по крайней мере 6 камней и попробуйте положить в неё самые лёгкие камни.

Прежде чем объяснять другие задачи, хочу вас спросить: вы хотите просто узнать решения задач, или хотите научится использовать методы решения?

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 17:58 
Tanechka в сообщении #584452 писал(а):
Это пару задачек?)
1. Выкиньте Петю - он единственный у кого 13 ошибок. У остальных будет от 0 до 12 ошибок, а человек будет 29.
2. Нет, вы неправы - необходимо, чтобы было хотя бы больше единицы.
3. Вот уже сказали - параллельным переносом сдвиньте все прямые, чтобы они проходили все через одну точку. Посчитаете кол-во углов и примените принцип Дирихле
4. Нет, причём везде неправильно. Рассмотрите худший случай... и допишите в задаче очень важное слово "гарантированно"
5. Нет, нельзя! Докажите, что какая-то трёхтонка повезёт по крайней мере 6 камней и попробуйте положить в неё самые лёгкие камни.

Прежде чем объяснять другие задачи, хочу вас спросить: вы хотите просто узнать решения задач, или хотите научится использовать методы решения?

Хочу за лето выйти на уровень городской олимпиады. На самом деле у меня не все так плохо, как кажется со стороны. За год по математике - 10. Но олимпиадные задачи значительно отличаются от школьных. Олимпиадные задания, где не нужно ничего доказывать, я решаю достаточно успешно(ясно, что задачи не такие сложные, как вы решаете в соседних темах). А где нужно что-то доказать...Тут самые проблемы, ибо в школе НИКОГДА(!) ничего не доказывали. Вот и учусь.

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 18:49 

(Оффтоп)

ZARATUSTRA, с Беларуси значит... а какой город, какой класс?

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 19:26 
Tanechka в сообщении #584474 писал(а):

(Оффтоп)

ZARATUSTRA, с Беларуси значит... а какой город, какой класс?

(Оффтоп)

Молодечно. Иду в 11.



3. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15◦.
12 прямых образуют 24 угла, которые в сумме равны 360. $360/24=15$. А если уменьшить другие углы в пользу того, чтобы этот угол был больше 15?

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 19:35 
ZARATUSTRA в сообщении #584491 писал(а):
А если уменьшить другие углы в пользу того, чтобы этот угол был больше 15?

Сначала советую почитать теорию, которая написана в книге... особенно где зайцы траву едят.

-- 13.06.2012, 20:07 --

(Оффтоп)

Вообще в 11 классе уже про областной диплом думать надо...

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение13.06.2012, 19:42 
Tanechka в сообщении #584498 писал(а):
ZARATUSTRA в сообщении #584491 писал(а):
А если уменьшить другие углы в пользу того, чтобы этот угол был больше 15?

Сначала советую почитать теорию, которая написана в книге... особенно где зайцы траву едят.

-- 13.06.2012, 20:07 --

(Оффтоп)

Вообще в 11 классе уже про областной диплом думать надо...

И там написано, что:"а если кто-то съел больше среднего то кто-то съел меньше среднего".
Почему в нашем случае нельзя, чтобы угол был больше 15, но зато мы уменьшим другие?

(Оффтоп)

Вы про облостной конкретно мне? Или 11-классникам? Если мне, то я в себе не очень уверен: у меня для подготовки лето+осенью учительница со мной будет заниматься. И то там времени не особо много - репетиторы и факультативы. Эх, начал бы я готовится хотя бы в 10 классе...А то последний раз занимался этим в классе 5-6 - первое место занял.
Эх, а мне бы облостной диплом дал 100 баллов по цт по математике...

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение14.06.2012, 08:56 
ZARATUSTRA в сообщении #584505 писал(а):
Почему в нашем случае нельзя, чтобы угол был больше 15, но зато мы уменьшим другие?

Хе, дык вы тогда выберете те прямые, которые образуют меньше 15 градусов...

 
 
 
 Re: Пару простых задач на принцип Дирихле.
Сообщение14.06.2012, 21:56 
Аватара пользователя
ZARATUSTRA в сообщении #584418 писал(а):
13. Первоклассник Петя знает только цифру 1. Докажите, что он может написать число, делящееся на 1989.
*А арифметических знаком он не знает?)

С помощью этой задачи можно решить другую, более сложную:
topic59966.html

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group