WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 25 | 26 || 28 | 29 |   ...   | 65 |

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

Мост выдерживает только двоих. Как им перейти мост за 17 минут (Если по мосту идут двое, то они идут с меньшей из их скоростей. Идти по мосту без фонарика нельзя. Светить издали нельзя, перебрасывать фонарик через реку тоже нельзя.) 20.4. Двое играют в следующую игру. Есть 9 карточек с числами 1, 2,..., 9. Играющие по очереди берут себе по одной карточке. Выигрывает тот, у кого есть три карточки с числами, дающими в сумме 15. Докажите, что эта игра эквивалентна игре в крестики-нолики на доске размером 3 3.

220 Глава 20. Стратегии. Турниры. Таблицы 20.2. Переливания 20.5. Есть полный кувшин молока в 8 литров и два пустых кувшина в 5 литров и 3 литра. Как разделить молоко на две равные части 20.6. Есть полный кувшин молока в 12 литров и два пустых кувшина в 8 литров и 5 литров. Как разделить молоко на две равные части 20.7. Есть четыре бочки. В первую входит 24 ведра, во вторую 13, в третью 11, в четвёртую 5. Первая бочка наполнена водой, а остальные бочки пустые. Как разделить воду на три равные части 20.3. Турниры При решении задач о турнирах нужно знать следующие правила:

а) в волейболе не бывает ничьих;

б) в шахматах за победу присуждается 1 очко, за ничью 1/2 очка, за поражение 0 очков.

20.8. Восемь волейбольных команд сыграли каждая с каждой по одному матчу. Докажите, что можно выбрать четыре команды a1, a2, a3, a4 так, что команда ai выиграла у aj при i < j.

20.9. Алик, Боря и Вася сыграли несколько партий в шахматы, причём каждый сыграл одинаковое число партий. Могло ли при этом оказаться, что у Алика меньше всех проигрышей, у Бори больше всех выигрышей, а у Васи больше всего очков 20.10. а) В шахматном турнире участвовали два ученика 7 класса и некоторое число учеников 8 класса. Два семиклассника набрали 8 очков, а каждый из восьмиклассников набрал одно и то же число очков. Сколько восьмиклассников участвовало в турнире Найдите все возможные решения.

б) В шахматном турнире участвовали ученики 9 и 10 классов. Десятиклассников было в 10 раз больше, чем девятиклассников, и они набрали вместе в 4, 5 раза больше очков, чем все девятиклассники. Сколько очков набрали девятиклассники 20.11. В соревнованиях участвуют 2n боксёров. Каждый день проходят бои 2n-1 пар боксёров (каждый боксёр проводит ровно один бой).

Все боксёры имеют разную силу, и в каждом бою побеждает сильнейший. Докажите, что за n(n+1)/2 дня можно определить место каждого боксёра. (Расписания на каждый день составляются накануне вечером и в день соревнований не меняются.) Глава 20. Стратегии. Турниры. Таблицы 20.4. Взвешивания 20.12. Есть несколько мешков, в каждом из которых достаточно много монет. В одном мешке монеты фальшивые, а во всех других настоящие. Известен вес настоящей монеты и известно, что фальшивая монета на 1 грамм легче настоящей. Как при помощи одного взвешивания на весах с разновесками обнаружить мешок с фальшивыми монетами 20.13. Среди 26 одинаковых по виду монет есть одна фальшивая, которая легче остальных. Докажите, что за три взвешивания на чашечных весах (без стрелок и гирь) можно найти фальшивую монету.

20.14. Среди 2n + 1 монет есть 2k фальшивых (k n), причём вес фальшивой монеты отличается от веса настоящей монеты на 1 грамм.

Как за одно взвешивание на чашечных весах со стрелкой про одну выбранную монету узнать, фальшивая она или нет 20.15. Есть n мешков, в каждом из которых достаточно много монет. Есть несколько разных сортов монет. Монеты разного сорта имеют разный вес, причём их веса различаются на целое число граммов. Вес монеты каждого сорта известен. В каждом мешке лежат монеты одного сорта, но количество мешков с монетами данного сорта может быть произвольным. Как при помощи одного взвешивания на весах с разновесками выяснить, какого сорта монеты лежат в каждом мешке 20.16. Некоторые из 20 металлических кубиков, одинаковых по размерам и внешнему виду, алюминиевые, остальные1 дюралевые (более тяжёлые). Как при помощи 11 взвешиваний на весах с двумя чашками без гирь определить число дюралевых кубиков 20.17. а) Дано (3n - 3) монет (n 2), среди которых есть одна фальшивая монета, отличающаяся по весу от настоящей. За n взвешиваний на чашечных весах без гирь нужно найти фальшивую монету и выяснить, тяжелее она или легче, чем настоящая.

б) Сделать то же самое в случае, когда монет меньше (3n - 3), но больше двух.

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

222 Глава 20. Стратегии. Турниры. Таблицы 20.5. Таблицы 20.18. а) В прямоугольной таблице, составленной из положительных чисел, произведение суммы чисел любого столбца на сумму чисел любой строки равно числу, стоящему на их пересечении. Докажите, что сумма всех чисел в таблице равна единице.

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

20.19. Квадратная таблица в n2 клеток заполнена числами от 1 до n так, что в каждой строке и каждом столбце встречаются все эти числа.

Докажите, что если n нечётно и таблица симметрична относительно диагонали, идущей из левого верхнего угла в правый нижний, то на этой диагонали встретятся все числа 1, 2, 3,..., n.

20.20. В клетках таблицы 8 8 записаны неотрицательные числа, сумма которых равна 1956.

а) Сумма чисел, стоящих на одной из диагоналей, равна 112. Числа, расположенные симметрично относительно этой диагонали, равны.

Докажите, что сумма чисел в любом столбце меньше 1035.

б) Сумма чисел, стоящих на двух диагоналях, равна 112. Числа, расположенные симметрично относительно любой диагонали, равны. Докажите, что сумма чисел в любой строке меньше 518.

20.21. Числа 1, 2,..., k2 расположены в виде квадратной таблицы:

1, 2,..., k, k + 1, k + 2,..., 2k,............

(k - 1)k + 1,...,..., k2.

Выпишем произвольное число из этой таблицы, а затем вычеркнем строку и столбец, содержащие это число. То же самое проделаем с оставшейся таблицей из (k - 1)2 чисел и т.д. k раз. Найдите сумму выписанных чисел.

Решения 20.1. Сначала нужно перевезти через реку козу. После этого перевозчик возвращается, и есть два варианта дальнейших действий. Нужно перевезти капусту (волка), вернуться обратно с козой, оставить козу на берегу, перевезти волка (капусту) и потом перевезти козу.

Глава 20. Стратегии. Турниры. Таблицы 20.2. Будем указывать в скобках, кто плывёт в лодке. Переправиться через реку можно следующим образом: РРСС(РС), РРСС(Р)С, РСС(РР)С, РСС(Р)РС, СС(РР)РС, СС(С)РРР, С(СС)РРР, С(Р)РРСС, (РС)РРСС.

20.3. Основная идея состоит в том, что бабушка должна пройти по мосту вместе с внуком. Сначала идут папа с мамой, затем папа возвращается с фонариком, после этого идут бабушка с внуком, затем мама возвращается с фонариком, наконец, папа с мамой переходят через мост. Всего на это будет затрачено 2 + 1 + 10 + 2 + 2 = 17 минут.

20.4. Легко проверить, что есть ровно 8 троек карточек, дающих в сумме 15: (1,5,9), (1,6,8), (2,4,9), (2,5,8), (2,6,7), (3,4,8), (3,5,7) и (4,5,6). Эти 8 троек чисел в точности тройки чисел, лежащих на одной прямой в таблице 2 9 7 5 3.

6 1 Таким образом, цель играющего состоит в том, чтобы занять в этой таблице три клетки на одной вертикали, горизонтали или диагонали.

20.5. П е р в о е р е ш е н и е. Если в 8-литровый, 5-литровый и 3-литровый кувшин налито, соответственно, a, b, c литров молока, то будем обозначать это (a, b, c). Можно применить такую последовательность переливаний:

(8, 0, 0) (3, 5, 0) (3, 2, 3) (6, 2, 0) (6, 0, 2) (1, 5, 2) (1, 4, 3) (4, 4, 0).

В т о р о е р е ш е н и е. Если есть три кувшина ёмкостью a, b, c литров, то последовательные переливания n литров жидкости удобно изображать в правильном треугольнике со стороной n. Каждой точке внутри правильного треугольника со стороной n можно сопоставить три неотрицательных числа x, y, z, сумма которых равна n. А именно, если через точку внутри правильного треугольника со стороной n провести прямые, параллельные сторонам треугольника, то образуются три маленьких треугольника со сторонами x, y, z; легко доказать, что x + y + z = n. Каждое из чисел x, y, z соответствует одной из сторон правильного треугольника. Будем считать, что этой стороне соответствует один из кувшинов, т.е. будем считать, что в кувшины ёмкостью a, b, c литров налито, соответственно, x, y, z литров. Переливания происходят в области, заданной неравенствами x a, y b, z c. Каждое отдельное переливание представляет собой перемещение из одной точки границы данной области в другую точку границы в направлении, параллельном одной из сторон треугольника.

Два различных варианта решения задачи изображены на рис. 20.1.

20.6. Можно применить такую последовательность переливаний:

(12, 0, 0) (4, 8, 0) (0, 8, 4) (8, 0, 4) (8, 4, 0) (3, 4, 5) (3, 8, 1) (11, 0, 1) (11, 1, 0) (6, 1, 5) (6, 6, 0).

224 Глава 20. Стратегии. Турниры. Таблицы (8, 0, 0) (7, 1, 0) (7, 0, 1) (5, 3, 0) (5, 0, 3) (4, 4, 0) (4, 1, 3) (2, 3, 3) (2, 5, 1) Рис. 20.1. Переливания 20.7. Можно применить следующие переливания: (24, 0, 0, 0) (19, 0, 0, 5) (8, 0, 11, 5) (8, 11, 0, 5) (0, 11, 8, 5) (0, 13, 8, 3) (8, 13, 0, 3) (8, 13, 3, 0) (8, 8, 3, 5) (8, 8, 8, 0).

20.8. Общее количество выигрышей равно общему количеству проигрышей. Каждая команда сыграла 7 матчей. Поэтому среднее количество выигрышей равно 3, 5. Значит, есть команда a1, выигравшая по крайней мере у четырёх команд. Для этих четырёх команд среднее число выигрышей в их матчах друг с другом равно 1, 5. Поэтому есть команда a2, которая выиграла по крайней мере у двух команд a3 и a4 (a3 это та команда, которая выиграла у другой).

20.9. О т в е т: да, могло. Чтобы построить соответствующий пример, рассмотрим три вида турниров со следующими турнирными таблицами:

Выигрыши Ничьи Проигрыши Очки Алик 0 4 0 Боря 1 2 1 Вася 1 2 1 Выигрыши Ничьи Проигрыши Очки Алик 1 2 1 Боря 1 2 1 Вася 0 4 0 Выигрыши Ничьи Проигрыши Очки Алик 0 1 1 1/Боря 0 1 1 1/Вася 2 0 0 Пусть было сыграно a турниров первого вида, b второго, c третьего.

Тогда у Алика b + c проигрышей, у Бори и Васи a + b + c и a проигрышей.

Глава 20. Стратегии. Турниры. Таблицы У Бори a + b выигрышей, у Алика и Васи b и a + 2c выигрышей. У Васи 2(a + b + c) очков, у Алика и Бори по 2a + 2b + c/2 очков. Поэтому должны выполняться неравенства a > b + c, b > 2c и c > 0. Например, можно взять c = 1, b = 3 и a = 5.

20.10. а) О т в е т: 7 или 14. Пусть x число восьмиклассников, y число очков, набранных каждым восьмиклассником. Подсчитывая двумя способами сумму очков, набранных всеми участниками турнира, приходим к уравнению (x + 2)(x + 1) xy + 8 =, т.е.

(x + 2)(x + 1) - 16 2y = = x + 3 -.

x x Поэтому x принимает одно из значений 1, 2, 7, 14. Значения 1 и 2 отпадают, поскольку в этих случаях число y будет отрицательным. Задача имеет два ответа: x = 7 и x = 14.

б) О т в е т: 10. Пусть в турнире участвовало x девятиклассников. Тогда 11x(11x - 1) всего было 11x участников и они набрали очков. По условию отношение числа очков, набранных девятиклассниками, к числу очков, набранных десятиклассниками, равно 1 : 4, 5. Поэтому девятиклассники набрали x(11x - 1) очков, а значит, каждый из девятиклассников выиграл все 11x - партий, которые он сыграл. Но если бы среди участников турнира было два девятиклассника, то партию между собой они должны были оба выиграть, что невозможно. Поэтому в турнире участвовал один девятиклассник; он набрал 10 очков.

20.11. Применим индукцию по n. Для n = 1 утверждение очевидно. Предположим, что 2n-1 боксёров можно упорядочить за n(n-1)/2 дней. Докажем, что тогда 2n боксёров можно упорядочить за n(n + 1)/2 дней. Разобьём боксёров на две группы X и Y по 2n-1 человек. Сначала будут происходить бои только между боксёрами из одной и той же группы. По предположению индукции за n(n - 1)/2 дней в каждой из этих групп боксёров можно упорядочить: X1 <... < XN и Y1 <... < YN, где N = 2n-1.

Теперь нужно за n(n+1)/2-n(n-1)/2 = n дней повести поединки между боксёрами из разных групп и упорядочить всех боксёров. Это мы тоже будем делать по индукции. При n = 1 утверждение очевидно. Сделаем теперь шаг индукции. Возьмём нечётную группу X1, X3,..., Y1, Y3,... и чётную группу X2, X4,..., Y2, Y4,... По предположению индукции за n - 1 дней можно упорядочить боксёров в каждой из этих групп (каждая группа состоит из двух уже упорядоченных меньших групп). Пусть Yj-< Xi < Yj+1. Тогда боксёра Xi нужно сравнить с Yj. Но это сравнение необходимо лишь во том случае, когда Xi-1 < Yj < Xi+1. Поэтому те пары боксёров {Xi, Yj}, между которыми необходимо провести бой, определены так, что ни один из боксёров не входит в две группы.

20.12. Занумеруем мешки и возьмём из каждого мешка столько монет, каков его номер. Взвесим все эти монеты. Их вес меньше веса такого же 226 Глава 20. Стратегии. Турниры. Таблицы количества настоящих монет на столько же граммов, каков номер мешка с фальшивыми монетами.

20.13. Возьмём 18 монет и положим половину из них на одну чашку весов, а другую половину на другую чашку. Если одна группа монет окажется легче, то фальшивая монета входит в эту группу. Если же чашки весов уравновесятся, то фальшивая монета находится среди восьми оставшихся монет.

После первого взвешивания у нас осталось 8 или 9 подозрительных монет.

Возьмём из них 6 монет и половину положим на одну чашку весов, половину на другую. После этого останется две или три подозрительных монеты.

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

20.14. Отложим выбранную монету и положим половину оставшихся монет на одну чашку весов, а другую половину на другую чашку. Пусть среди первых n монет есть k1 фальшивых, а среди других n монет есть k2 фальшивых. Тогда на первой чашке лежит груз весом na ± k1, где a вес настоящей монеты, а на второй чашке лежит груз весом na ± k2. Стрелка весов покажет разность k1 - k2 k1 + k2 (mod 2). Таким образом, если выбранная монета фальшивая, то показание стрелки весов нечётное число, а если выбранная монета настоящая, то показание стрелки весов чётное число.

Pages:     | 1 |   ...   | 25 | 26 || 28 | 29 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.