Решение комбинаторных и логических задач
элективный курс (5 класс) на тему

. ПЕРЕСТАНОВКИ

     1) Пусть требуется рассадить четырех человек по четырем креслам. Сколькими способами это можно сделать?  

     2) Помощь. Обозначим людей буквами A, B, C, D и занумеруем кресла: 1, 2, 3, 4. Пусть сначала A сел в кресло с номером 1. Сколькими способами можно рассадить остальных людей?

     Повторите рассуждения, когда A занял кресло с другим номером.

     3) С помощью аналогичных рассуждений покажите, что 5 человек можно рассадить по пяти креслам 54321 способами.

     Сколькими способами можно переставить местами 6 элементов (людей, животных, предметов, знаков)? А 7 элементов?

     Чему равно , если  элементов можно переставить местами 40320 способами?

     4) Что означает запись ? Как называют такую запись?

     Чему равны , , , , , ?

     Решая предыдущие задачи, вы находили число перестановок из  элементов. Это число обозначают . Покажите, что .

     5) Решите следующие задачи, записав их решение, если это возможно,  с помощью знака факториала:

     а) Шестеро спортсменов должны разместиться по шести одноместным байдаркам. Сколькими способами это можно сделать?

     б) Семеро артистов разыгрывают по жребию порядок выступления. Сколько существует результатов жеребьевки?

     в) Сколькими способами можно подключить 9 различных принтеров к девяти компьютерам?

     6) Придумайте задачу, решение которой можно записать с помощью знака факториала.

2. ПЕРЕСТАНОВКИ БЕЗ ПОВТОРЕНИЙ И С ПОВТОРЕНИЯМИ

     1) Прочитайте задачу:

     Сколько можно составить пятизначных чисел, используя по одному разу каждую из следующих цифр:

а) 1, 2, 3, 4, 5;   б) 1, 2, 2, 3, 4;   в) 1, 2, 4, 4, 4;   г) 1, 1, 1, 1, 5?

     Как вы считаете, в каком из случаев - «а», «б», «в», «г» - можно составить больше всего чисел? В каком случае чисел будет меньше всего? Почему?

     Попробуйте ответить на вопросы пунктов «а», «б», «в», «г».

     2) Помощь. Рассмотрим случай «в» и предположим на время, что все цифры 4 «окрасились» в разные цвета и, следовательно, стали различимыми между собой. Сколько чисел можно составить из пяти различных цифр? А теперь предположим, что все цифры 4 «потеряли» свой цвет и вновь стали неразличимыми. Покажите, что при этом искомое количество чисел уменьшится в  раз и станет равно 20.

     3) Покажите, что если использовать каждую цифру по одному разу, то из цифр 9, 9, 9, 8, 7, 6 можно составить 120 шестизначных чисел.

     Сколько семизначных чисел можно составить из цифр 5, 5, 5, 6, 6, 6, 6, используя каждую по одному разу?

     Сколько восьмизначных чисел можно составить из цифр 2, 2, 2, 3, 3, 3, 4, 4, используя каждую по одному разу?

     4) Сколько десятизначных чисел можно составить, используя по одному разу каждую из следующих цифр:  а) 1, 1, 1, 2, 2, 2, 2, 3, 4, 5;   б) 3, 3, 3, 3, 4, 4, 4, 4, 4, 5?   в) 9, 9, 8, 8, 7, 7, 6, 6, 5, 5?

     5) Решите задачу:

     Машинисту нужно прицепить к тепловозу 3 пустые (неразличимые между собой) цистерны и 4 пустые (неразличимые между собой) платформы. Машинист думает, в каком порядке ему прицепить к тепловозу цистерны и платформы. Сколькими способами он может составить поезд?

     Как измениться ответ, если одну из цистерн заполнили нефтью, другую бензином, а третью мазутом и они стали между собой различимыми?

     6) Запишите 8 цифр (возможно повторяющихся), если известно, что используя каждую из них по одному разу, можно составить:

     а)  восьмизначных чисел;        в) 336 восьмизначных чисел;

     б)  восьмизначных чисел;    г) 2520 восьмизначных чисел.

3. СОЧЕТАНИЯ

     1) Представьте себе, что передается некоторый набор сообщений, каждое из которых закодировано с помощью трех единиц и пяти нулей, например, 01001100;  10001001;  00001110. Будем называть такие записи двоичными последовательностями. Сколько существует двоичных последовательностей, состоящих из пяти нулей и трех единиц?

     2) Помощь. Предположите на время, что все единицы и все нули стали «разноцветными» и, следовательно, различимыми между собой. Сколько сообщений можно передать в этом случае?

     Как изменится количество сообщений, если нули и единицы «потеряют» свой цвет и снова станут неразличимыми?

     3) Пусть из девяти человек нужно выбрать троих. Подумайте, как можно «закодировать» такой выбор с помощью двоичных последовательностей, а затем покажите, что такой выбор можно осуществить 84 способами.

     4) Сколькими способами можно выбрать: а) 4 книги из восьми?  б) 6 учеников из десяти?  в) 5 конфет из двенадцати?

     5) Когда вы решали задачи пункта «4», то вы, как принято говорить, находили число сочетаний из восьми по четыре, из десяти по шесть, из двенадцати по пять.

     Для числа сочетаний из  по  существует специальное обозначение . Покажите на примерах, что .

     6) Чему равны: ;  ;  ?

     Рассмотрите и объясните два способа вычисления :

     ...;      

     ...

     7) Найдите , , удобным, на ваш взгляд, способом, а затем придумайте задачи, решение которых можно записать с помощью числа сочетаний из 9 по 5 и из 12 по 6.

4. ПЕРВОЕ СВОЙСТВО СОЧЕТАНИЙ

     1) Сравните задачи:

   Из восьми работников фирмы троих нужно отправить в командировку. Сколькими способами можно выбрать трех человек из восьми?

    Из восьми картин художнику нужно отобрать пять картин для выставки. Сколькими способами можно выбрать пять картин из восьми?

     Как вы думаете, будут ли у обеих задач одинаковые ответы? Почему?

     2) Помощь. Обратите внимание на то, что когда художник отправит 5 картин на выставку, дома у него останутся 3 картины. Сколькими способами он может выбрать те 3 картины, которые он оставит дома?

     Используя формулу числа сочетаний, покажите, что .

     3) Одинаково ли число способов, которыми можно выбрать:

     а) 4 конфеты из 10 и 6 конфет из 10?

     б) семерых мальчиков из пятнадцати и восьмерых девочек из пятнадцати?

     в) 2 предмета из 100 и 98 предметов из 100?

     4) Решая задачи предыдущих пунктов, вы встретились с важным свойством числа сочетаний, которое можно записать в виде формулы      .

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

5. ВТОРОЕ СВОЙСТВО СОЧЕТАНИЙ

     1) Решите задачу:

     В школьной баскетбольной команде 12 человек. В стартовом составе на площадку должны выйти пятеро. Сколькими способами тренер может выбрать пять человек из двенадцати?

     2) Одного из баскетболистов зовут Ваня. Предположим, что тренер решил обязательно включить Ваню в стартовую пятерку. Сколькими способами он может в этом случае выбрать остальных четверых игроков?

     А теперь предположим, что Ваня точно не войдет в стартовую пятерку. Сколькими способами можно составить стартовую пятерку в этом случае?

     Рассмотрите схему на рисунке 43 и подумайте, чему должна быть равна сумма , учитывая, что Ваня либо играет в стартовой пятерке, либо не играет.

     3) Проверьте равенства ,  , записав выражения для числа сочетаний с помощью факториала.    

     4) Итак, мы установили еще одно важное свойство числа сочетаний, которое можно записать в виде формулы: .

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

6. ТРЕУГОЛЬНИК ПАСКАЛЯ

     1) По какому принципу записаны числа сочетаний?

             ....................................................................................................            

     Такую запись называют треугольником Паскаля (в честь французского ученого XVII века Блёза Паскаля).

     Замените в треугольнике Паскаля все  числами, обратив при этом внимание, что принято считать: .

     2) Проверьте, получилась ли у вас такая запись:

     Какие особенности треугольника Паскаля вы могли бы отметить?

     Как отражены в треугольнике Паскаля два свойства числа сочетаний:  и ?

     3) Продолжите построение треугольника Паскаля с таким расчетом, чтобы в нем было 10-12 строк, используя при этом, если считаете нужным, формулы  и .

     4) Проверьте, есть ли в вашем треугольнике Паскаля числа 210, 66, 924? Если нет, добавьте столько строк, чтобы эти числа появились.

     5) Придумайте и выполните задание, связанное с треугольником Паскаля и его свойствами.

7. ЕЩЕ ОДНО СВОЙСТВО СОЧЕТАНИЙ

     1) Сложите числа, записанные в каждой из строк треугольника Паскаля, то есть, найдите суммы: , ,  и так далее. Какую закономерность вы заметили?

     Запишите найденную закономерность в виде формулы, а затем проверьте себя: .

     2) Поясним найденное равенство на примере. Пусть имеются 4 каких-либо элемента , , , . Если мы выберем  и , то такому выбору можно сопоставить «код» 1010; если же выбрать только , то код будет таким: 0001 и так далее.

     Рассмотрите таблицу и объясните, как она построена:

     А теперь подумайте, сколько всего существует «кодов», то есть, сколько существует двоичных последовательностей длины 4.

     3) Постройте аналогичную таблицу, которая могла бы пояснить равенство .

     4) В коридоре 8 лампочек, каждая из которых может либо гореть, либо не гореть. Сколькими способами можно осветить коридор?

     Сколькими способами можно осветить коридор, если из восьми лампочек нужно включить: а) 4 лампочки?  б) 5 лампочек?

     5) В школьной олимпиаде по математике участвуют 12 пятиклассников, каждый из которых в случае успеха может попасть на городскую олимпиаду. Сколькими способами может быть сформирована команда пятиклассников, участвующих в городской олимпиаде?

     Как изменится ответ, если на городскую олимпиаду могут быть допущены не более четырех человек из 12?

     6) Составьте задачу, при решении которой используется свойство числа сочетаний, рассмотренное в данном параграфе.

8. РАЗМЕЩЕНИЯ БЕЗ ПОВТОРЕНИЙ И С ПОВТОРЕНИЯМИ

     1) Сравните задачи:

   Имеются 5 коробок и 3 разноцветных шара. Сколькими способами можно разместить эти шары по коробкам, если в одной коробке может находиться не более одного шара?

    Имеются 5 коробок и 3 разноцветных шара. Сколькими способами можно разместить эти шары по коробкам, если в коробках может находиться любое количество шаров?

     Как вы думаете, в каком случае искомое число размещений будет больше? Почему? Решите обе задачи.

     2) Помощь. Подумайте, сколькими способами можно разместить первый шар, затем второй, а затем третий, учитывая при этом, что в одном случае шар не может попасть в уже «занятую» коробку, а в другом случае - может.

     3) Решая задачи пункта «1», вы подсчитывали число размещений из пяти элементов по 3. При этом в первой задаче вы подсчитывали число размещений без повторений, а во второй задаче  - число размещений с повторениями.

     Обозначим:  - число размещений без повторений из  элементов по ,  - число размещений с повторениями из  элементов по . Покажите, что ; .

     4) Что изменилось в условии первой задачи пункта «1», если искомое число способов размещения шаров стало равно 120?

     Что изменилось в условии второй задачи пункта «1», если искомое число способов размещения стало равно 625?

     5) В каких из следующих задач нужно найти число размещений без повторений, а в каком случае - с повторениями? Решите все задачи.

     а) Кодовый замок состоит из четырех барабанов, на каждом из которых нужно выбрать одну из десяти цифр. Сколькими способами можно выбрать код, если все его цифры должны быть различными?

     б) В киоске продаются 12 сортов мороженого. К киоску подходят четверо друзей, каждый из которых собирается купить какое-либо мороженое. Сколькими способами они могут сделать покупку?

     в) Из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 нужно выбрать шесть различных цифр и составить из них шестизначное число. Сколькими способами это можно сделать?

9. ОТ РАЗМЕЩЕНИЙ К ПЕРЕСТАНОВКАМ

     1) Используя каждую из цифр 1, 2, 3, 4, 5 по одному разу, требуется записать: а) все трехзначные числа;  б) все четырехзначные числа;  в) все пятизначные числа. Сколько, по-вашему, можно записать чисел в каждом случае? Запишите ответ, используя символ числа размещений .

     Можно ли в одном из случаев записать ответ с помощью символа числа перестановок ? Если можно, то в каком именно случае? Почему?

     2) Используя по одному разу некоторые из букв слова АБРИКОС, нужно составить всевозможные слова (не обязательно имеющие смысл) длины . Чему равно , если всего можно составить: а) 210 слов?  б) 2520 слов? Запишите решение с помощью символа . Можно ли в одном из случаев записать решение с помощью символа ?

     3) Составьте задачу, решение которой можно записать с помощью символа . Измените затем условие задачи так, чтобы ее решение можно было записать с помощью символа .

10. ОТ РАЗМЕЩЕНИЙ К СОЧЕТАНИЯМ

     1) Сравните задачи:

   10 футбольных команд разыгрывают между собой золотые, серебряные и бронзовые медали. Сколькими способами могут распределиться медали между десятью командами?

    10 хоккейных команд разыгрывают три путевки в международный турнир (их получат три лучшие команды). Сколькими способами могут быть разыграны путевки в международный турнир?

     В какой из задач нужно найти число размещений? В какой задаче - число сочетаний? Поясните свой ответ.

     2) Решите обе задачи. Во сколько раз отличаются полученные числа? Как вы это объясните?

     3) Составьте две задачи, в одной из которых нужно найти число сочетаний из 9 по 4, а в другой - число размещений из 9 по 4. Как вы объясните, что полученные числа отличаются в 24 раза?

     4) Пусть  - число размещений из  по , а  - число сочетаний из  по . Покажите, что . Исходя из этого равенства, покажите, что .

     5) Решите задачи:

     а) В некотором классе изучают 10 предметов. В понедельник 6 уроков. Сколькими способами можно выбрать предметы, которые войдут в расписание на понедельник при условии, что все предметы должны быть различными?

     б) Сколько существует шестизначных чисел, записанных в двенадцатеричной системе счисления, если:

     - в записи чисел можно использовать все цифры, кроме нуля?

     - можно использовать все 12 цифр?

11. РАЗБИЕНИЕ ЧИСЛА НА СЛАГАЕМЫЕ

     1) Сколькими способами можно разбить число 6 на два слагаемых, каждое из которых должно быть натуральным числом? (При этом имеет значение, в каком именно порядке записаны слагаемые, то есть, разбиения 6=1+5 и 6=5+1 считаются различными.)

     Сколькими способами можно разбить на два слагаемых (при тех же условиях): а) число 10?  б) число 200?   в) произвольное число ?

     2) Сколькими способами можно разбить число 6 на три натуральных слагаемых, если по-прежнему важен порядок следования слагаемых?

      3)    Сколькими способами можно разбить:

     а) число 7 на четыре слагаемых?

     б) число 10 на три слагаемых?

     в) число 11 на четыре слагаемых?

     4) Обратитесь к треугольнику Паскаля. Как вы объясните, что всех рассмотренных случаях ответы совпадают с одним из чисел этого треугольника?

     Покажите на примерах, что число  можно разбить на  слагаемых  способами.

     5) Сравните число способов разбиения:

     а) числа 12 на четыре слагаемых и числа 11 на пять слагаемых;

     б) числа 16 на восемь слагаемых и числа 16 на девять слагаемых;

     в) числа 1000000 на два слагаемых и числа 1500 на три слагаемых.

     6) Число 17 можно разбить на  слагаемых 560 способами. Чему равно ? (Сколько решений имеет задача?)

     7) Число 13 можно разбить на  слагаемых 924 способами. Чему равно ?

     7) Чему равно , если на четыре слагаемых это число можно разбить 1140 способами? Сколькими способами можно разбить  на 19 слагаемых?

12. «БЛУЖДАНИЯ» ПО ГОРОДУ

     1) Представьте, что вы оказались в городе со строго прямоугольной планировкой (рис. 44). Пусть вам нужно попасть из точки A в точку B. Сколько существует путей, ведущих из A в B? (При этом двигаться можно либо вправо, либо вверх, то есть, выбирать можно только кратчайший путь из A в B).

     2) Сколько существует путей: из K в L, из M в N, из P в Q (рис )?

M

                     а)                                     б)                                               в)

     Обратите внимание, что во всех рассмотренных случаях искомое число путей выражается числом, входящим в треугольник Паскаля. Как бы вы это объяснили?

     3) Начертите план города с прямоугольной планировкой и выберите на его улицах две точки с таким расчетом, чтобы число путей из одной точки к другой равнялось: а) 56;  б) 72;  в) любому наперед заданному числу из треугольника Паскаля.

13. ДРУГОЙ ВАРИАНТ «БЛУЖДАНИЙ»

     1) Предположим, что из точки O в точку A можно попасть, двигаясь по диагоналям квадратов, составляющих сетку (рис.). Сколько существует таких путей из O в A?

     2) Рассмотрим аналогичные «блуждания» по координатной плоскости, взяв в качестве стартовой точки начало координат. Сколько существует путей, ведущих к точкам: а) K(4; 0);  б) L(-6; 0);  в) M(8; 0)?

    Проверьте, входят ли найденные числа в треугольник Паскаля.

     Почему эти числа должны входить в треугольник Паскаля?

     В какой именно части треугольника Паскаля находятся числа, равные числу путей из начала координат к точке с координатами (; 0)?

     3) Чему равны числа  и , если число путей из начала координат к точке K(; 0) равно 252, а число путей из начала координат к точке   L(; 0) равно 924? Сколько существует решений в каждом случае?

     4) Подумайте, как можно закодировать пути, ведущие из начала координат к точкам P(4; -2), Q(6; 4), R(-4; -6). Найдите число путей, ведущих из начала координат к этим точкам.

14. ТРЕУГОЛЬНЫЕ ЧИСЛА

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

     1) Из скольких кружков состоит каждый из «треугольников» на рисунке 49?

     Числа 1, 3, 6, 10, 15 называют треугольными.

     По какому принципу строятся треугольные числа? Обратите внимание на разность между соседними треугольными числами.

     Рассмотрите треугольник Паскаля и найдите в нем треугольные числа. Запишите треугольные числа с помощью символа .

     Запишите все треугольные числа, меньшие ста.

     2) Вычислите суммы:  ;  ;  ;  . Как вы объясните, что их значения равны треугольным числам?

     Обозначим -е по счету треугольное число . Покажите, что это число можно вычислить по формуле:

     3) Решите следующие задачи. В каких из них ответ выражается треугольным числом?

     а) Из шести задач ученик должен решить четыре по своему выбору. Сколькими способами он может выбрать четыре задачи из шести?

     б) В восьмиугольнике провели все диагонали. Сколько всего на чертеже отрезков?

     в) В десятиугольнике провели все диагонали. Сколько всего провели диагоналей?

     г) 12 человек обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

     4) Придумайте задачу, ответом на которую было бы одно из треугольных чисел.

15. РАЗБИЕНИЯ НА ПАРЫ И ТРОЙКИ

     1) Решите задачу:

     Восемь человек хотят покататься в четырех двухместных лодках. Сколькими способами они могут разбиться на пары для размещения по лодкам? (Как двое сядут в лодку - значения не имеет.)

     2) Помощь. Пронумеруйте людей и подумайте, сколькими способами можно «подобрать пару» человеку с номером 1. Повторите рассуждения, подбирая пары остальным.

     3) Что изменилось в условии задачи пункта «1», если искомое число способов оказалось равно: а) 15?  б) 945?

     4) Пусть нужно поставить в пары  детей. Покажите, что это можно сделать  способами.

     5) В международных соревнованиях участвуют 8 теннисистов, среди которых двое российских. С помощью жребия составляют пары спортсменов, которые будут играть между собой. В скольких случаях из 105 двое российских теннисистов не окажутся в одной паре?

     Ответьте на аналогичный вопрос, если среди восьми спортсменов четверо российских.

     6) 12 человек собираются разместиться по четырем трехместным байдаркам. Сколькими способами их можно разбить на 4 тройки?    

16. СКОЛЬКО ДЕЛИТЕЛЕЙ ИМЕЕТ ЧИСЛО?

     1) Сколько всего делителей имеют числа: ; ; ?

     Какое из двух чисел имеет больше делителей:

а)  или ?   б)  или ?   в)  или ?

     2) Пусть  - произвольное простое число,  - натуральное число. Запишите в виде буквенного выражения количество делителей числа .

     Как изменится ответ, если взять другое простое число ?

     Чему равны или могут быть равны  и , если  имеет:  а) 7 делителей?  б) 20 делителей?   в) 2004 делителя?

     3) Найдите количество делителей чисел , , , если ;; .

     Как зависит количество делителей от показателей степени?

     Обратитесь, если нужно к таблице.

     3) Пусть число  раскладывается на простые множители следующим образом: . Покажите, что  имеет  делителей.

     Проиллюстрируйте свой ответ на примерах.

     4) Пусть число  раскладывается на простые множители следующим образом: . Обозначим греческой буквой  (читается «тау») количество делителей числа . Покажите на примерах, что .

     5) Сколько делителей имеют числа , , , , если:  ;  ;  ;  ?

     6) Запишите в виде разложения на простые множители какие-нибудь числа, имеющие: а) 10 делителей;  б) 28 делителей;  в) 36 делителей.

     7) Найдите количество делителей чисел, , , , , , , , , если:

     ;  ;  ;  ;  

     ;   ;  ;  ;  .

20. ПРИНЦИП ДИРИХЛЕ

     1) Решите задачи:

     В классе 13 девочек. Можно ли быть уверенным, что хотя бы две из них справляют свой день рождения в одном и том же месяце?

     У фермера 50 кроликов. Для их содержания фермер приобрел 24 клетки, а затем каким-то образом разместил кроликов в этих клетках (возможно, некоторые клетки остались пустыми). Можно ли быть уверенным в том, что:

     а) найдется клетка, в которой будут находиться более двух кроликов?

     б) найдется клетка, в которой будут находиться более трех кроликов?

     2) Решая задачи пункта «1», вы встретились с известным в математике принципом Дирихле, названным так в честь немецкого математика XIX века Петера Дирихле.

     В общем виде принцип Дирихле формулируется так:

     Если в  коробках распределить каким-то образом более  предметов, то обязательно найдется коробка, содержащая более одного предмета.

     Прочитайте еще раз первую задачу пункта «1». Что в этой задаче играет роль «коробок», а что роль «предметов»?

     3) Пусть теперь в  коробках нужно разместить более  предметов. Как бы вы сформулировали принцип Дирихле в этом случае?

     Прочитайте еще раз вторую задачу пункта «1». Что в ней играет роль «коробок», а что роль «предметов»?

     4) Пусть у фермера по-прежнему 24 клетки. Какое наименьшее количество кроликов он должен приобрести, чтобы после их размещения по клеткам:

     а) обязательно нашлась бы клетка, в которой было бы более трех кроликов?

     б) обязательно нашлась бы клетка, в которой было бы более пяти кроликов?

     5) Используя принцип Дирихле, выясните, верны ли следующие утверждения:

     а) Если в школе 750 учеников, то среди них наверняка найдутся трое таких, которые справляют свой день рождения в один и тот же день.

     б) Если из цифр 1, 3, 5, 7, 9 составить, используя каждую по одному разу, 125 чисел, то среди полученных чисел обязательно найдутся хотя бы два одинаковых.

     в) Если взять наугад 6 натуральных чисел, то среди них найдутся по крайней мере два числа, дающих при делении на 5 одинаковые остатки.

     г) Если взять наугад 11 натуральных чисел, то среди них найдутся два таких, разность которых оканчивается нулем.

21. ПРИНЦИП ДИРИХЛЕ (ПРОДОЛЖЕНИЕ)

     1) Имеются 6 клеток и 14 попугаев. Можно ли рассадить попугаев по клеткам так, чтобы во всех клетках находилось разное количество попугаев? (Считаем, что в пустой клетке находятся 0 попугаев.) Если этого сделать нельзя, то почему?

     2) Изменится ли ответ на вопрос пункта «1», если по шести клеткам рассадить с таким же условием не 14, а 15 попугаев? А если рассадить 16 попугаев? А если попугаев 13?

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

     3) Решая задачи предыдущих пунктов, вы встретились с другой формулировкой принципа Дирихле:

      Если в  коробках разместить каким-то образом менее  предметов, то обязательно найдутся две коробки, содержащие одинаковое количество предметов (возможно, и ни одного).

     Как вы думаете, почему в формулировке принципа Дирихле речь идет именно о  предметах?

     4) Используя принцип Дирихле, ответьте на вопросы:

     а) В роще 20 елей, на каждой из которых не более 200 шишек (может быть, ни одной). Можно ли быть уверенным, что найдутся две ели с одинаковым количеством шишек?

     б) Имеются 400 рублевых монет. Можно ли разложить эти монеты по 30 кошелькам так, чтобы не было пустых кошельков и чтобы во всех кошельках было разное количество рублей?

    Если этого сделать нельзя, то какое наименьшее количество монет нужно взять, чтобы это стало возможным?

     в) В классе  человек, у каждого из них имеется среди одноклассников некоторое количество друзей (возможно, 0 друзей). Верно ли, что в этом классе найдутся двое, у которых будет одинаковое количество друзей среди одноклассников?

22. ФАЛЬШИВЫЕ МОНЕТЫ

     1) Пусть имеются 3 одинаковые на вид монеты, среди которых две настоящие, а одна фальшивая. Все настоящие монеты весят одинаково, а фальшивая монета немного легче настоящей. Имеются также чашечные весы без гирь (рис. 55). Можно ли за одно взвешивание на таких весах определить, какая из трех монет фальшивая? Если можно, то как это сделать?

     2) Пусть теперь имеются не 3, а 4 одинаковые на вид монеты, среди которых одна фальшивая (легче остальных). Можно ли обнаружить фальшивую монету за одно взвешивание на весах, изображенных на рисунке 55? Если можно, то как, если нельзя, то почему?

     3) Пусть среди  монет одна фальшивая (легче остальных). Покажите, как ее можно обнаружить за два взвешивания на таких же весах, если: ;   .

     Покажите, что если , то за два взвешивания обнаружить фальшивую монету невозможно.

     4) Пусть среди  монет одна фальшивая (легче остальных). Покажите, что если , то ее можно обнаружить за три взвешивания.

     5) Сколько потребуется взвешиваний на весах, изображенных на рисунке 55, для того, чтобы обнаружить одну более легкую монету:

     а) среди 60 одинаковых на вид монет?

     б) среди 200 одинаковых на вид монет?

     в) среди 700 одинаковых на вид монет?

     г) среди 750 одинаковых на вид монет?

23. ФАЛЬШИВЫЕ МОНЕТЫ (Продолжение)

     1) Пусть имеются 3 одинаковые на вид монеты, среди которых две настоящие, а одна фальшивая. Известно, что фальшивая монета отличается от настоящих по весу, однако неизвестно, легче она или тяжелее. Можно ли за одно взвешивание на весах, изображенных  на рисунке 55, обнаружить фальшивую монету? Если нельзя, то почему?

     Как обнаружить фальшивую монету за два взвешивания?

     2) Пусть теперь имеются 4 монеты, среди которых три настоящие, а одна фальшивая (неизвестно, легче или тяжелее настоящей). Можно ли ее обнаружить за два взвешивания на таких же весах? Если можно, то как это сделать? Всегда ли удастся при этом узнать, легче или тяжелее фальшивая монета по сравнению с настоящей?

     3) Пусть требуется обнаружить фальшивую монету среди  одинаковых на вид монет (по-прежнему неизвестно, легче ли она или тяжелее). Покажите, как с помощью трех взвешиваний можно найти фальшивую монету при: ;   .

8.24. ФАЛЬШИВЫЕ МОНЕТЫ (Продолжение)

     1) В следующих заданиях необходимо также обнаружить фальшивые монеты, однако сейчас в нашем распоряжении будут не чашечные весы, а электронные (на дисплее высвечивается масса груза).

     Пусть имеются 10 мешков с монетами. В девяти мешках все монеты настоящие весом в 10 г каждая, а в одном мешке - фальшивые весом в 11 г каждая. При взвешивании можно брать из любого мешка любое количество монет. Как за одно взвешивание определить, в каком мешке лежат фальшивые монеты?

     2) Помощь. Предположите, что во всех мешках монеты настоящие. Возьмите из первого мешка одну монету, из второго две, из третьего три и так далее. Сколько будут весить все монеты?

     А теперь предположите, что в одном из мешков монеты фальшивые. На сколько изменится общий вес монет?

     3) 100 мешков заполнены монетами: в 99 мешках они настоящие весом в 1 г, а в одном фальшивые - весом в 0,9 г. Из первого мешка взяли одну монету, из второго две, из третьего три и так далее. Оказалось, что все монеты вместе весят 5 кг 42 г 8 мг. В каком по счету мешке находятся фальшивые монеты?

     Ответьте на вопрос пункта «3», если общий вес монет оказался равен: а) 5,04 кг;  б) 5048,7 г.

     4) В коробке лежат 25 настоящих монет и 10 фальшивых. Вес монет неизвестен; известно только, что он выражается целым числом граммов и что настоящая монета на 1 г тяжелее фальшивой. Из коробки пропала одна монета. Как за одно взвешивание на электронных весах определить, какая монета пропала - настоящая или фальшивая?

ДОПОЛНИТЕЛЬНЫЕ ЗАДАНИЯ

1. 1) С помощью цифр 1, 2, 3 составили всевозможные трехзначные числа без повторения цифр. Чему равна сумма этих чисел?

     2) Чему равна сумма всех четырехзначных чисел, составленных из цифр 1, 2, 3, 4 без повторения цифр?

3. 1) На «шахматную доску» размера 44 (рис. 56) нужно поставить 4 ладьи так, чтобы они не били друг друга. Сколькими способами это можно сделать? (Ладья ходит и бьет по вертикали и по горизонтали.)

     2) Сформулируйте и решите аналогичную задачу, связанную с расположением 8 ладей на обычной шахматной доске размера 88.

4. 1) На книжную полку нужно поставить 5 одинаковых учебников по алгебре и 5 одинаковых учебников по геометрии. Сколькими способами можно расставить эти учебники на полке?

     2) Как изменится ответ, если все учебники по алгебре будут различимыми, а учебники по геометрии по-прежнему неразличимы?

5. Сколько различных ожерелий можно сделать:  а) из 4 красных бусинок и 5 синих?  б) из 3 красных бусинок, 4 синих и 5 белых? в) из 5 желтых бусинок, 4 зеленых, 3 красных и 1 черной? (Все бусинки одного цвета считаются между собой неразличимыми.)

6. 1) Известно, что из  зеленых бусинок и  желтых можно составить 330 различных ожерелий. Чему равны (или могут быть равны) числа  и ?

     2) Чему могут быть равны натуральные числа ,  и , если из  белых бусинок,  красных и  зеленых можно составить 4200 различных ожерелий?

7. 1) На отрезке координатной прямой в точках с координатами 1, 2, ... , 11, 12 требуется отметить 8 красных точек и 4 синих. Сколькими способами это можно сделать?

     2) Ответьте на вопрос пункта «1», если в точках с координатами 1 и 12 должны располагаться:  а) красные точки?  б) синие точки?

8. 1) Сколько существует четырехзначных чисел, записанных с помощью двух различных четных цифр и двух различных нечетных? (Цифра 0 в запись числа не входит.)

     2) Ответьте на вопрос пункта «1», если при тех же условиях число требуется записать в восьмеричной системе счисления.

9. Сколько восьмизначных чисел можно составить из цифр 5, 6, 7, 8, если каждую из них можно использовать не более двух раз?

10. Сколько девятизначных чисел можно составить из цифр 2, 3, 4, если каждую из них можно использовать не более трех раз?

11. Сколько пятизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3, 4, 5, если каждую из них можно использовать:  а) только один раз?    б) любое количество раз?

12. Сколько десятизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3, 4, 5, если каждую из них можно использовать не более двух раз?

13. Сколько шестизначных чисел, кратных четырем, можно составить из цифр 1, 2, 3, 4, 5, 7, если каждую из них можно использовать только один раз?

14. Сколько можно получить новых «слов», переставляя местами буквы в словах:   а) БАРАН?  б) БАНАН?  в) АНАНАС?  г) АНАКОНДА?  д) ПАРАЛЛЕЛОГРАММ? (Слова не обязательно должны иметь смысл.)

15. Сколько можно получить новых «слов», переставляя местами буквы в словах ПАРОМ, САХАР, ПОМИДОР, БАРАБАН при условии, что гласные и согласные звуки должны чередоваться? (Слова не обязательно должны иметь смысл.)

16. 1) На огороде вскопали 12 грядок, на четырех из которых хотят посадить морковь, на четырех - горох, на четырех - свеклу. Сколькими способами можно выбрать грядки для посадки каждого из этих овощей?

     2) На другом огороде также вскопали 12 грядок, но здесь хотят посадить: на трех грядках капусту, на трех репу, на трех грядках огурцы и на трех помидоры. Сколькими способами можно выбрать грядки для овощей на этом огороде?

17. Сколько семизначных чисел можно составить из четырех цифр 3 и трех цифр 2? Сколько среди этих чисел четных? Сколько нечетных?

18. Сколькими способами можно выбрать из всех двузначных чисел два различных числа так, чтобы:  а) их сумма была четным числом? б) их произведение было четным числом?

19. Сколько можно записать десятичных дробей, меньших 1, используя по одному разу каждую из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9?

20. Сколько можно записать десятичных дробей, меньших , используя по одному разу каждую из цифр: а) 0, 2, 4, 6, 8?  б) 0, 1, 3, 5, 7, 9?

21. Сколько можно записать десятичных дробей, меньших , используя по одному разу каждую из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9?

22. 1) Сколько можно записать десятичных дробей, меньших , используя по два раза каждую из цифр 0, 1, 2, 3, 4?

     2) Ответьте на вопрос пункта «1», заменив  на .

23. 1) С помощью цифр 1 и 2 составили всевозможные трехзначные числа, а затем эти числа перемножили. Какой цифрой оканчивается полученное произведение?

     2) Ответьте на вопрос пункта «1», заменив цифры 1 и 2 на 9 и 7.

24. С помощью цифр 1, 2, 3, 4 составили всевозможные четырехзначные числа без повторения цифр, а затем эти числа перемножили. Какой цифрой оканчивается полученное произведение?

25. Используя цифры 1, 3, 5, 7, 9, составили всевозможные пятизначные числа, а затем эти числа перемножили. Какой цифрой оканчивается полученное произведение?

26. 1) Подъезд оборудован замком с десятью кнопками. Для того, чтобы открыть подъезд, нужно одновременно нажать две определенные кнопки. Сколькими способами можно выбрать код замка?

     2) Ответьте на вопрос пункта «1», если дверь открывается при одновременном нажатии трех определенных кнопок.

27. 1) Сколькими способами можно расставить на шахматной доске размера 44 две ладьи так, чтобы они не били друг друга?

     2) Сколькими способами можно расставить на шахматной доске размера 88 три ладьи так, чтобы они не били друг друга?

28. 1) Выпускнику школы нужно сдать экзамены по пяти предметам из десяти по своему выбору. Сколькими способами он может выбрать 5 предметов?

     2) Как изменится ответ, если выпускник решил, что:  а) он обязательно будет сдавать физику?  б) точно не будет сдавать физику?

29. Сколько существует двоичных последовательностей длины 8, содержащих нечетное число единиц?

30. Сколько существует двоичных последовательностей длины 9, содержащих: а) четное число единиц?  б) нечетное число единиц?

31. Сколько существует десятизначных чисел, сумма цифр которых равна:     а) 1;  б) 2;  в) 3?

32*. Сколько десятизначных чисел, кратных трем, можно записать с помощью цифр 0 и 1?

33*. Сколько десятизначных чисел, кратных девяти, можно записать с помощью цифр 2 и 4?

34. Сколькими способами можно заменить буквы двузначными числами в неравенстве ?

35. Сколькими способами можно заменить буквы однозначными натуральными числами в цепочке неравенств ?

36. Сколько существует трехзначных чисел, в которых каждая последующая цифра меньше предыдущей?

37. Сколько существует трехзначных чисел, записанных в шестеричной системе счисления, в которых каждая последующая цифра больше предыдущей?

39. На плоскости отмечены 8 точек. Сколько существует ломаных, состоящих из двух звеньев, концы которых совпадают с этими точками?

40. 1) На каждой из двух параллельных прямых отмечены по 6 точек. Сколько существует треугольников с вершинами в этих точках?

     2) Как изменится ответ, если на одной прямой отмечено 5 точек, а на другой 7?

41. Сколько можно построить треугольников, вершины которых совпадают с вершинами данного куба, если треугольники могут быть расположены только на гранях куба?

42. На окружности отмечено 10 точек. Сколько существует треугольников с вершинами в этих точках?

43. На окружности отмечено 12 точек, среди которых одна «красная». Сколько существует треугольников с вершинами в этих точках, если:

     а) одна из вершин треугольника - «красная» точка?

     б) среди вершин треугольника нет «красной» точки?

44. 1) Имеются ткани 12 цветов. Сколькими способами из этих тканей можно изготовить трехцветный флаг с горизонтальными полосами одинаковой ширины, если цвета всех полос должны быть различными?

     2) Как изменится ответ, если цвета верхней и нижней полос могут совпадать?

45. 1) 20 учеников пишут контрольную работу, за которую каждый из них может получить оценку «2», «3», «4», «5». Сколько может быть результатов контрольной?

     2) Как изменится ответ, если стало известно, что двойки получили трое учеников?

46. 1) Из 11 лыжников тренер должен выбрать четверых для участия в эстафете, а затем распределить их по этапам. Сколькими способами он может это сделать?

     2) Как измениться ответ, если двоих лыжников - Иванова и Петрова - тренер уже выбрал, и ему осталось выбрать еще двоих и распределить всех по этапам?

47. Сколько существует:

     а) десятизначных чисел, записанных в двоичной системе счисления?

     б) шестизначных чисел, записанных в пятеричной системе счисления?

     в) пятизначных чисел, записанных в шестеричной системе счисления?

     г) четырехзначных чисел, записанных в двенадцатеричной системе счисления?

48. Сколько четырехзначных чисел можно записать с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9, если эти числа должны быть:  а) больше 6000?  б) кратны пяти?  в) нечетными? (Цифры в записи чисел могут повторяться.)

49. 1) Сколько натуральных чисел, меньших 500, можно записать с помощью цифр 2, 4, 6?

     2) Сколько натуральных чисел, меньших 9000, можно записать с помощью цифр 1, 5, 8, 9?

     3) Сколько натуральных чисел, меньших 60000, можно записать с помощью цифр 3 и 7? (Во всех случаях цифры в записи чисел могут повторяться.)

50. 1) Сколько существует четырехзначных чисел, в записи которых используется один раз цифра 5?

     2) Сколько существует четырехзначных чисел, в записи которых хотя бы один раз используется цифра 5?

51. Сколько существует пятизначных чисел, записанных в пятеричной системе счисления, в записи которых:  а) хотя бы один раз используется цифра 4?  б) хотя бы один раз используется цифра 0?

52. Сколько существует четырехзначных чисел, в записи которых имеются по крайней мере две одинаковые цифры?

53*. Сколько существует шестизначных чисел, записанных в троичной системе счисления, в записи которых имеются по крайней мере три одинаковые цифры?

54. Сколько слов, состоящих из трех букв, можно составить из букв, входящих в слово БАРСУК, если: а) первая и третья буквы должны быть согласными, а вторая гласной?  б) хотя бы одна из букв должна быть гласной?

55. Сколькими способами, используя буквы A, B, C, D, E, F, G, H, можно обозначить:

     а) равносторонний треугольник (его вершины неразличимы)?

     б) треугольник с разными углами?

     в) четырехугольник с разными углами?

56. Сколькими способами можно разместить 14 неразличимых шаров по четырем различимым коробкам при условии, чтобы не было пустых коробок?

57. Сколькими способами можно раздать 25 одинаковых конфет 10 детям при условии, что ни один из них не останется без конфеты?

58. Сколькими способами можно разбить число 17 на пять натуральных слагаемых при условии, что первое слагаемое должно быть не больше двух?

разложить 16 рублевых монет по двенадцати карманам?

60. 1) Из начала координат нужно попасть в точку A(2; 3), двигаясь только вправо и вверх по линиям, образующим сетку (рис. 58). Сколько существует таких путей из начала координат к точке A(2; 3)? 

     2) Сколько существует аналогичных путей, ведущих из начала координат к точкам B, C, D?

     3) Сколько существует аналогичных путей, ведущих:

     а) из точки L(-2; -1) в точку U(0; 3)?

     б) из точки N(0; -5) в точку V(6; 0)?    в) из точки N(-6; -4) в точку W(4; 6)?

63. 1) На прямой отметили 10 точек. Сколько отрезков с концами в этих точках образовалось на прямой?

     2) Сколько точек отметили на прямой, если при этом образовалось 120 отрезков с концами в этих точках?

64. Каково наибольшее возможное число точек пересечения: а) четырех окружностей?  б) пяти окружностей?  в) шести окружностей?

65. Сколько существует:

     а) правильных дробей со знаменателем меньшим или равным 20?

     б) неправильных дробей с числителем меньшим или равным 30?

     в) правильных дробей со знаменателем большим 50, но меньшим или равным 100?

66. На окружности отмечены 14 точек. Сколько существует хорд с концами в этих точках?

67. На окружности отмечены 14 точек. Сколькими способами можно провести шесть хорд с концами в этих точках так, чтобы каждая точка принадлежала только одной хорде?

68. На окружности отмечены 18 точек. Сколькими способами можно построить шесть треугольников, вершины которых совпадают с этими точками, если каждая из точек может принадлежать только одному треугольнику?

69. Сколькими способами 30 туристов могут разместиться по десяти трехместным лодкам? (Как разместятся туристы в каждой лодке - значения не имеет).

70. Найдите хотя бы одно трехзначное число, имеющее:  а) 24 делителя; б) 28 делителей;  в) 30 делителей.

71. 1) Найдите трехзначное число, имеющее 32 делителя.  

     2) Докажите, что не существует трехзначного числа, имеющего более 32 делителей.

     3) Существует ли трехзначное число, имеющее: а) 26 делителей?  б) 22 делителя?  в) 14 делителей? Если такие числа существуют - назовите их, если не существуют - объясните почему.

72. 1) О числе  известно, что  и что оно имеет 36 делителей. Чему равно ?

     2) О числе  известно, что  и что оно имеет 40 делителей. Чему равно ?

73. 1) Найдите двузначное число, которое имеет 8 делителей, среди которых один делитель простой.

     2) Найдите число, которое имеет 16 делителей, среди которых два простых.

     3) Найдите число, которое имеет 12 делителей, среди которых три простых.

     4) Найдите число, которое меньше 2500 и имеет 32 делителя, среди которых пять простых.

74. Натуральное число имеет один простой делитель. Может ли это число иметь 1000 составных делителей? Поясните свой ответ и, если такое число существует, назовите его.

75. Натуральное число  имеет пять простых делителей. Какое наименьшее число составных делителей может иметь это число? Укажите наименьшее из возможных значений .

76. Натуральное число  имеет шесть простых делителей. Какое наименьшее число составных делителей может иметь это число? Укажите наименьшее из возможных значений .

77. 1) Пусть ;  . Сколько существует чисел , таких, что  и ?

     2) Изменится ли ответ, если ;  ?

78. Докажите следующее утверждение или опровергните его, приведя контрпример:

     В любом графе обязательно найдутся хотя бы две вершины, имеющие одинаковую степень.

     Проиллюстрируйте свое доказательство на примерах.

79. На горнолыжном курорте предполагается построить 5 новых станций (назовем их A, B, C, D, E) и некоторые из них соединить между собой канатной дорогой. Конкретно предполагается:

     - станцию A соединить со всеми четырьмя другими станциями;

     - станцию B соединить с тремя другими станциями;

     - станцию C соединить с двумя другими станциями;

     - станцию D соединить с какой-либо одной другой станцией.

     Станцию E не предполагается соединять с другими станциями.

     Осуществим ли такой проект?

80. Встретились  человек, среди которых некоторые знакомы между собой, некоторые не знакомы. Докажите, что найдутся по крайней мере два человека, у которых число знакомых одинаково.

81. Граф состоит из девяти вершин, причем степени всех вершин одинаковы и равны . При каких значениях  это возможно? Поясните свой ответ и начертите такие графы.

82. Постройте эйлеров граф:  а) с 6 вершинами и 10 ребрами;  б) с 7 вершинами и 14 ребрами;  в) с 8 вершинами и 24 ребрами.

83. При каких значениях  -угольник со всеми диагоналями будет эйлеровым графом?

84. Восемь друзей сыграли между собой несколько партий в шахматы. На вопрос, сколько партий сыграл каждый из них, были даны такие ответы: 4, 3, 5, 2, 1, 4, 6, 0. Возможно ли такое? Если не возможно, то почему?

        K 

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Рис. 60

85. 1) На «шахматной доске» (рис. 60) в клетке K стоит конь. Может ли этот конь, двигаясь по правилам шахматной игры, обойти все клетки по одному разу, а затем вернуться в исходную клетку? (Постарайтесь решить задачу, построив соответствующий граф.)

     2) Сформулируйте и решите аналогичную задачу на доске размера 44.

86. Какие из графов на рисунке 61 являются эйлеровыми? Почему остальные графы не являются эйлеровыми? Удалите у этих графов одно из ребер или добавьте в граф одно ребро так, что полученный граф стал эйлеровым.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

88. Десять зайцев нашли 52 морковки и каким-то образом разделили их между собой, причем ни один из зайцев не остался без морковки. Можно ли быть уверенным, что:

     а) нашелся заяц, которому досталось более пяти морковок?

     б) нашелся заяц, которому досталась точно одна морковка?

     в) нашлись два зайца, которым досталось более пяти морковок?

     г) нашлись два зайца, которым досталось одинаковое количество морковок?

89. В ящике лежат 100 черных шаров, 100 красных и 100 белых, причем на ощупь все шары неотличимы. Какое наименьшее количество шаров нужно достать, не заглядывая в ящик, чтобы в самом неблагоприятном случае среди них наверняка были:  а) два белых шара?  б) пять шаров какого-либо одного цвета?  в) хотя бы по одному шару каждого цвета?

90. В коробке лежат 50 пар черных перчаток и 50 пар коричневых, причем на ощупь можно отличить только правую перчатку от левой. Какое наименьшее количество перчаток нужно достать не заглядывая в коробку, чтобы в самом неблагоприятном случае иметь:  а) пару перчаток одного цвета? б) пару перчаток черного цвета?

91. Имеются 10 замков и 10 ключей, причем каждый из ключей подходит к какому-нибудь одному замку. Какое количество проб необходимо совершить в самом неблагоприятном случае, чтобы определить, какой ключ подходит к каждому из замков?

92. Имеются 8 замков и 12 ключей, среди которых 8 подходят к одному из замков, остальные 4 - нет. Какое количество проб необходимо совершить в самом неблагоприятном случае, чтобы подобрать к каждому из замков подходящий ключ?

93*. Докажите, что среди  натуральных чисел всегда найдутся два таких, разность которых делится на . Поясните свое доказательство на примерах.

94. Докажите или опровергните: если взять любые 12 двузначных чисел, то среди них найдутся два таких, разность которых записывается одинаковыми цифрами.

95. Докажите или опровергните: если взять любые 5 чисел, записанных в двоичной системе счисления, то среди них найдутся два таких, разность которых оканчивается двумя нулями.

96. Произвольно выбрали четыре натуральных числа, а затем эти числа возвели в четвертую степень. Докажите, что среди полученных чисел найдутся два таких, разность которых оканчивается нулем.

97. 1) Необходимо разложить 250 предметов по  коробкам так, чтобы во всех коробках было разное количество предметов (возможно, что одна из коробок пуста). При каком наибольшем  это можно сделать?

     2) Сформулируйте и решите аналогичную задачу, заменив 250 на 1000.

98. 16 человек пошли на рынок. Из них арбуз купили 10 человек, дыню - 12. Какое наименьшее количество человек могли купить и арбуз, и дыню?

99. В классе 25 человек. При этом кошка есть у 16 из них, собака - у 18, а попугай - у 17. Какое наименьшее количество учеников могут иметь дома кошку, собаку и попугая?

100*. Записаны 15 натуральных чисел. Среди них 12 чисел четные, 11 чисел кратны пяти, а 9 чисел кратны трем. Какое наименьшее количество чисел может быть кратно тридцати?

101. 1) Имеются  одинаковых на вид монет, среди которых одна фальшивая (легче остальных). Покажите, что если , то с помощью чашечных весов без гирь фальшивую монету можно обнаружить за четыре взвешивания.

     2) Сколько потребуется взвешиваний, чтобы обнаружить фальшивую (более легкую) монету среди  одинаковых на вид монет, если ? Поясните свой ответ на примерах.

102. 1) Среди девяти одинаковых на вид монет одна фальшивая, однако неизвестно, легче или тяжелее она настоящей монеты. Как за три взвешивания на весах без гирь можно обнаружить эту монету?

     2) Решите задачу пункта «1», если имеются не 9, а 10 одинаковых на вид монет.

103. 1) Среди 30 одинаковых на вид монет одна фальшивая, отличающаяся по весу от остальных. Как за два взвешивания на весах без гирь можно узнать, легче или тяжелее фальшивая монета, чем настоящая? (Саму монету находить не нужно.)

     2) Ответьте на вопрос пункта «1», если одна фальшивая монета находится среди: а) 1000 монет;  б) 1000000 монет.

104. Имеются 6 одинаковых на вид металлических шаров, среди которых 4 шара немного тяжелее двух других. Как за три взвешивания на весах без гирь можно отделить более тяжелые шары от более легких?

105. Среди шести одинаковых на вид деталей три бракованных (тяжелее остальных). За сколько взвешиваний на весах без гирь можно обнаружить бракованные детали?

106*. Среди десяти одинаковых на вид монет имеются настоящие и фальшивые (легче настоящих), причем количество фальшивых монет неизвестно. Как за 6 взвешиваний на весах без гирь можно обнаружить все фальшивые монеты?

 40

1

39

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

24

17

18

19

 21

48

41

                D

А

                                       A

D

                                                B

       C

47

42

43

44