WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |

«ЗАД АЧИ П О АЛГЕ БР Е, АР И Ф МЕ Т И КЕ И АН АЛИ ЗУ Учебное пособие Москва Издательство МЦНМО 2007 УДК 512.1+517.1+511.1 ББК 22.141+22.161 П70 Прасолов В. В. П70 Задачи по алгебре, арифметике и анализу: Учебное пособие. ...»

-- [ Страница 3 ] --

14.26. Докажите, что НОД(a1,..., an ) = Pнечет /Pчёт, где Pнечет — произведение НОК всех наборов, состоящих из нечётного числа различных чисел a1,..., an, а Pчёт — произведение НОК всех наборов, состоящих из чётного числа различных чисел a1,..., an. (Предполагается, что числа a1,..., an попарно различны.) 14.27. Даны 6 цифр: 0, 1, 2, 3, 4, 5. Найдите сумму всех четырёхзначных чётных чисел, которые можно написать этими цифрами (одна и та же цифра в числе может повторяться).

14.28. Сколькими различными способами можно представить 1 000 000 в виде произведения трёх натуральных чисел? Произведения, отличающиеся лишь порядком сомножителей, считаются одинаковыми.

14.5. Неравенства для биномиальных коэффициентов 14.6. Арифметика биномиальных коэффициентов 14.30. Пусть p — простое число и 1 k p 1. Докажите, что Ck делится на p.

14.31. Пусть p — простое число. Докажите, что для всех натуральных m p 1 число (1)m Cm 1 делится на p.

14.32. Докажите, что если p — простое число, то Cn n (mod p2 ).

14.33. Пусть p — нечётное простое число, n = p 2, где 2. Докажите, что если m 2, то Cm делится на p m.

14.34. Пусть p — простое число. Докажите, что если См. также задачи 21.31, 21.32.

14.7. Формула включений и исключений 14.35. Дано N предметов и некоторый набор свойств P1,..., Pn. Пусть Ni — количество предметов, обладающих свойством Pi, Nij — количество предметов, обладающих свойствами Pi и Pj, и т. д. Докажите, что количество предметов, не обладающих ни одним из данных свойств, равно C выигрывает у B, если на C выпадает 6 или на C выпадает 3, а на B выпадает 2. Вероятность этого равна 1/6 + 5/6 · 1/2 = 7/12 > > 1/2.

A выигрывает у C, если на A выпадает 4, а на C выпадает 3.

Вероятность этого равна 5/6 · 5/6 = 25/36 > 1/2.

РЕКУРРЕНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

Рекуррентной последовательностью порядка k называют последовательность чисел u1, u2,..., где числа u1, u2,..., uk произвольные, а при всех n 1 выполняется соотношение un+k = a1 un+k1 +... + ak un, где a1, a2,..., ak — некоторые фиксированные числа.

15.1. Пусть a1, a2,..., ak — фиксированные числа и un+k = = a1 un+k1 +... + ak un. Докажите, что где Pk1 (x) — многочлен степени не выше k 1.

15.2. Пусть a1, a2,..., ak — фиксированные числа и un+k = = a1 un+k1 +... + ak un. Предположим, что x1,..., xk — попарно различные корни уравнения xk = a1 xk1 + a2 xk2 +... + ak.

Докажите, что тогда un = c1 xn1 +... + ck xn1 для некоторых фиксированных чисел c1,..., ck.

Числами Фибоначчи называют последовательность чисел F1 = 1, F2 = 1, Fn = Fn1 + Fn2 при n 3. Начало этой последовательности имеет вид 1, 1, 2, 3, 5, 8, 13, 21,...

15.3. Докажите, что Fn+k = Fn1 Fk + Fn Fk+1.

15.4. а) Докажите, что числа Fn и Fn+1 взаимно просты.

б) Докажите, что НОД(Fm, Fn ) = Fd, где d = НОД(m, n).

15.5. Докажите, что если m>2, то Fn делится на Fm тогда и только тогда, когда n делится на m.

202 Глава 15. Рекуррентные последовательности 15.6. Докажите, что (Бине).

15.7. Докажите, что для любого натурального n число делится на 2n1.

15.8. а) Пусть f1 (x)=1, f2 (x)=x и fn (x)=xfn1 (x)+fn2 (x) при n 3. Докажите, что б) Докажите, что 15.9. Докажите, что 15.10. Докажите, что для любого натурального числа n найдётся число Фибоначчи, делящееся на n.

15.11. Докажите, что сумма восьми последовательных чисел Фибоначчи не может быть равна числу Фибоначчи.

15.12. Докажите, что если a2 ab b2 = ±1, где a и b — натуральные числа, то a = Fn+1 и b = Fn для некоторого n.

15.13. Найдите все решения в натуральных числах уравn!

эффициент.

15.14. а) Докажите, что F2n+1 F2n1 = F2 + 1.

15.15. При каких натуральных a и b число a2 + b2 + делится на ab?

15.16. Найдите все пары натуральных чисел a и b, для которых a2 + 1 делится на b, а b2 + 1 делится на a.

15.17. Докажите, что любое натуральное число n единственным образом можно представить в виде n=Fk1 +Fk2 +...

15.18. Докажите, что число Фибоначчи с нечётным номером не может делиться на простое число вида 4k + 3.

15.3. Числа Фибоначчи и алгоритм Евклида 15.19. Пусть a и b — натуральные числа, причём a > b и НОД(a, b) = d. Докажите, что если алгоритм Евклида, применённый к a и b, останавливается после n шагов, то a dFn+2 и b dFn+1.

15.20. а) Докажите, что Fn+5 > 10Fn при n 2.

б) Докажите, что если Fn+1 < 10k, то n 5k.

15.21. Докажите, что количество шагов алгоритма Евклида, применённого к паре натуральных чисел a > b, не превосходит количества цифр десятичной записи числа b, умноженного на 5.

15.4. Числа Фибоначчи в комбинаторике 15.22. Чему равно количество подмножеств множества {1, 2, 3,..., n}, не содержащих двух последовательных чисел?

15.23. Сколькими способами можно представить число n в виде суммы нескольких слагаемых, равных 1 или 2?



(Представления, различающиеся порядком слагаемых, считаются различными.) 15.24. Сколькими способами можно представить число n в виде суммы нескольких целых слагаемых ai 2? (Представления, различающиеся порядком слагаемых, считаются различными.) 15.25. Сколькими способами можно представить число n в виде суммы положительных нечётных слагаемых? (Представления, различающиеся порядком слагаемых, считаются различными.) 204 Глава 15. Рекуррентные последовательности 15.26. Пусть a1 = 1, a2 = 0, a3 = 1 и при n 1. Докажите, что an — квадрат целого числа для любого n 1.

15.27. Пусть u1 = 1, u2 = 0, u3 = 1 и un = un2 + un3 при n 4. Докажите, что u2n u2 и u2n+1 u2 делятся на un.

15.1. В произведении коэффициент при xn+k1, n 1, равен un+k a1 un+k1... ak un = 0.

Значит, это произведение представляет собой многочлен Pk1 (x) степени не выше k 1.

15.2. Согласно задаче 10.35 можно выбрать числа c1,..., ck так, что Тогда Аналогично c1 xk+1 +... + ck xk+1 = uk+2 и т. д.

15.3. Применим индукцию по k. При k = 1 получаем Fn+1 = = Fn1 + Fn, а при k = 2 получаем Fn+2 = Fn1 + 2Fn = Fn1 + Fn + Fn = = Fn+1 + Fn. База индукции доказана. Предположим теперь, что Fn+k2 = Fn1 Fk2 + Fn Fk1 и Fn+k1 = Fn1 Fk1 + Fn Fk. Тогда Fn+k = = Fn1 (Fk2 + Fk1 ) + Fn (Fk1 + Fk ) = Fn1 Fk + Fn Fk+1.

15.4. а) Предположим, что числа Fn и Fn+1 делятся на целое число d > 1. Тогда Fn1 = Fn+1 Fn тоже делится на d и т. д. В итоге получим, что F2 = 1 делится на d.

б) Воспользуемся формулой Fn+k =Fn1 Fk +Fn Fk+1 (задача 15.3).

Положим m = n + k. При m > k получаем НОД(Fm, Fk ) = НОД(Fmk1 Fk + Fmk Fk+1, Fk ) = поскольку числа Fk и Fk+1 взаимно простые. Теперь можно воспользоваться результатом задачи 4.11.

15.5. Число Fn делится на Fm тогда и только тогда, когда НОД(Fn, Fm ) = Fm. С другой стороны, согласно задаче 15. НОД(Fn, Fm ) = FНОД(n,m) . Таким образом, получаем следующее условие: НОД(n, m) = m (здесь мы пользуемся тем, что m > 2).

Полученное равенство, в свою очередь, эквивалентно тому, что n делится на m.

15.6. Согласно задаче 15.2 Fn = c1 xn + c2 xn, где x1 и x2 — корни уравнения x2 = x + 1, а c1 и c2 — некоторые константы. Решая квадратное уравнение, получаем x1,2 =. Константы c1 и c мы находим, воспользовавшись тем, что F1 = 1 и F2 = 1.

15.7. Формула Бине (задача 15.6) показывает, что 15.8. а) Многочлены f1 (x) и f2 (x) имеют указанный вид. Поэтому достаточно проверить, что многочлены указанного вида удовлетворяют указанному рекуррентному соотношению. Но если посмотреть на коэффициенты при степенях x по отдельности, то это рекуррентное соотношение сводится к основному тождеству для биномиальных коэффициентов: Ck = Ck nk1 + Cnk1.

б) Непосредственно следует из а), поскольку Fn = fn (1).

15.10. Рассмотрим пары остатков от деления на n соседних чисел Фибоначчи Fk и Fk+1 для k = 1, 2,..., n2 + 1. Количество различных пар остатков равно n2, поэтому среди рассматриваемых пар остатков найдутся две одинаковые пары, т. е. числа Fk Fl и Fk+1 Fl+1 делятся на n для некоторых чисел 1 k < l n2 + 1.

Тогда число Fk1 Fl1 = Fk+1 Fl+1 (Fk Fl ) тоже делится на n и т. д. В конце концов получаем, что числа F2 Flk+ и F1 Flk+1 делятся на n. Поэтому Flk = Flk+2 Flk+1 F2 F 0 (mod n).

15.11. Пусть S = Fk+1 + Fk+2 +... + Fk+8 — сумма восьми последовательных чисел Фибоначчи. Достаточно доказать, что 206 Глава 15. Рекуррентные последовательности Fk+9 < S < Fk+10. Первое неравенство очевидно: S > Fk+7 + Fk+8 = = Fk+9. Докажем теперь второе неравенство. Ясно, что Последнее выражение, очевидно, больше S.

15.12. Равенство a2 = b2 + ab ± 1 показывает, что a b, причём a = b лишь в том случае, когда оба эти числа равны 1. Поэтому будем считать, что a > b. Для пары b, a b тоже выполняется требуемое равенство, поскольку b2 (a b)b (a b)2 = (a2 ab b2 ).

Поэтому после нескольких таких замен мы дойдём до пары (1, 1).

Обратное преобразование имеет вид (x, y) (x + y, x), поэтому из пары (1, 1) мы будем последовательно получать пары (Fn+1, Fn ) для n = 2, 3,...

15.13. Рассматриваемое уравнение эквивалентно уравнению mn=(nm)(nm+1). Пусть d=НОД(m, n), n=da и m=db. После сокращения на d получаем уравнение abd = (a b)((a b)d + 1).

Число d взаимно просто с (a b)d + 1, а число ab взаимно просто с a b, поэтому ab = (a b)d + 1 и d = a b. Подставим в первое уравнение выражение a = b + d и заменим a b на d. В результате получим b2 + bd = d2 + 1, т. е. b2 + bd d2 = 1. В задаче 15.12 приведено решение уравнения чуть более общего вида, когда в правой части стоит ±1. Отбросив те решения, которые соответствуют 1, получим d = F2k, b = F2k1 и a = b + d = F2k+1. Таким образом, n = F2k F2k+1 и m = F2k F2k1.

З а м е ч а н и е. Равенство Cn = Cm эквивалентно равенству Cn1 + Cn1 = Cn1.

15.14. а) Применим индукцию по n. При n = 1 равенство очевидно. Предположим, что доказано равенство F2n+1 F2n1 = F2 + 1 2n для некоторого n. Тогда 2n+2 + 1 = (F2n+1 + F2n ) + 1 = F2n+1 + 2F2n+1 F2n + F2n + 1 = 2n+1 + 2F2n+1 F2n + F2n+1 F2n1 = F2n+1 (F2n+1 + 2F2n + F2n1 ).

Остаётся заметить, что F2n+1 + 2F2n + F2n1 = F2n+2 + F2n+1 = F2n+3.

б) Воспользовавшись задачей а), получаем 2n+1 + F2n1 2F2n+1 F2n1 = (F2n+1 F2n1 ) = F2n = F2n+1 F2n1 1, 15.15. Можно считать, что a b. Согласно задаче 15.14 б) пара чисел (a, b) = (F2n+1, F2n1 ), n 1, обладает требуемым свойством; пара чисел (a, b) = (1, 1) тоже. Покажем, что никакие другие пары натуральных чисел (a, b), где a b, этим свойством не обладают. Применим индукцию по a. Прежде всего отметим, что если a = b, то число 2a2 + 1 делится на a2, поэтому a = 1. Предположим, что a2 + b2 + 1 = kab, где k — натуральb2 + поэтому числа (a1, b1 ) обладают требуемым свойством. Проверим, б) Применим индукцию по k. При k = 1 достаточно заметить, что F7 = 13 > 10. Предположим, что для данного k 1 мы уже доказали, что из неравенства Fn+1 < 10k следует неравенство n 5k.

Пусть Fm+1 < 10k+1. Тогда согласно задаче а) 10Fm4 < Fm+1 < 10k+1, поэтому F(m5)+1 < 10k. Следовательно, согласно предположению индукции m 5 5k, т. е. m 5(k + 1), что и требовалось.

15.21. Пусть алгоритм Евклида, применённый к паре (a, b), останавливается после n шагов. Тогда согласно задаче 15.19 b Fn+1.

Если количество цифр в десятичной записи числа b равно k, то b < 10k, поэтому Fn+1 < 10k. Остаётся воспользоваться результатом задачи 15.20.

15.22. О т в е т: Fn+2. Пусть искомое число равно xn. При n = 1 есть подмножества и {1}, поэтому x1 = 2. При n = 2 есть подмножества, {1} и {2}, поэтому x2 = 3. Легко проверить, что xn = xn1 + xn2 при n 3. Действительно, если рассматриваемое подмножество содержит n, то оно не содержит n 1, и никаких других ограничений на него не накладывается. Количество таких подмножеств равно xn2. Ясно также, что количество рассматриваемых подмножеств, не содержащих n, равно xn1.

15.23. О т в е т: Fn+1. Пусть искомое число равно xn. Ясно, что x1 = 1 и x2 = 2. Докажем, что xn = xn1 + xn2 при n 3. Действительно, количество представлений числа n с первым слагаемым равно xn1, а с первым слагаемым 2 — xn2.

15.24. О т в е т: Fn1. Пусть искомое число равно xn. Ясно, что x1 = 0, x2 = 1 и x3 = 1. Докажем, что xn = xn1 + xn2 при n 3.

Первое слагаемое может быть равно 2; количество таких представлений равно xn2. Первое слагаемое может быть больше 2. Тогда из него можно вычесть 1 и получить представление числа n 1.

Поэтому количество таких представлений равно xn1.

15.25. О т в е т: Fn. Пусть искомое число равно xn. Ясно, что x1 = 1 и x2 = 1. Докажем, что xn = xn1 + xn2 при n 3. Действительно, количество представлений с первым слагаемым 1 равно xn1. Если же первое слагаемое не меньше 3, то из него можно вычесть 2 и получить представление числа n 2.

15.26. Рассмотрим последовательность bn, для которой b1 = 1, b2 = 0 и bn+2 = nbn+1 + bn при n 1. Возведём в квадрат равенства bn = bn+2 nbn+1 и bn+3 = (n + 1)bn+2 + bn+1. Затем, чтобы уничтожить член bn+2 bn+1, умножим первое из полученных равенств на n + 1, второе на n и сложим их. В результате получим Кроме того, b3 = 1. Значит, an = b2.

15.27. Проверим, что при 0 < k < m 2 имеет место равенство При k = 1 это равенство очевидно. Поэтому достаточно доказать, что uk+1 umk + uk+2 umk1 + uk umk2 = uk+2 umk1 + uk+3 umk2 + + uk+1 umk3. Сократим члены uk+2 umk1 в обеих частях этого равенства и воспользуемся тем, что uk+1 umk = uk+1 umk2 + + uk+1 umk3. После сокращения членов uk+1 umk3, приходим к очевидному равенству (uk+1 + uk )umk2 = uk+3 umk2.

Положив в равенстве (1) m = 2n и k = n 1, получим u2n u2 = = 2un un+1. Положив в равенстве (1) m = 2n + 1 и k = n 1, получим u2n+1 u2 = un (un1 + un+2 ).

ПРИМЕРЫ И КОНСТРУКЦИИ

16.1. Можно ли выбрать 10 натуральных чисел так, чтобы ни одно из них не делилось ни на какое другое, но квадрат любого числа делился бы на каждое из чисел?

16.2. а) Докажите, что существует бесконечно много пар натуральных чисел k, l 2, для которых k! l! = n! для некоторого натурального n.

б) Докажите, что для каждого натурального числа m существует бесконечно много наборов натуральных чисел a1,..., am 2, для которых a1 ! a2 !... am ! = n! для некоторого n.

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

16.4. а) Конечно или бесконечно множество пар натуральных чисел a, b, обладающих следующим свойством:

простые делители чисел a и b одинаковые и простые делители чисел a + 1 и b + 1 тоже одинаковые (и при этом a = b)?

б) Конечно или бесконечно множество пар натуральных чисел a, b, обладающих следующим свойством: простые делители чисел a и b+1 одинаковые и простые делители чисел a + 1 и b тоже одинаковые?

16.5. Укажите попарно различные натуральные числа и p + q + r = p1 + q1 + r1 (Рамануджан).

16.2. Бесконечные последовательности 16.6. Для любого ли натурального n из последовательности 1, 1/2, 1/3, 1/4,... можно выделить арифметическую прогрессию длины n?

16.7. Существует ли бесконечная последовательность натуральных чисел a1, a2,..., в которой нет степеней натуральных чисел и никакая сумма нескольких различных членов этой последовательности не является степенью натурального числа?

16.3. Последовательности операций 16.8. Карточки с числами 1, 2, 3,..., 32 сложены в стопку по порядку. Разрешается снять сверху любое число карточек и вложить их между оставшимися карточками, не меняя порядка карточек в каждой из двух частей, а в остальном произвольно.

а) Докажите, что за 5 таких операций можно разложить карточки в произвольном порядке.

б) Докажите, что за 4 такие операции нельзя разложить карточки в обратном порядке.

16.4. Многочлены и рациональные функции 16.9. Приведите пример рациональной функции R(x) (т. е. отношения двух многочленов), которая отлична от константы и R(x) = R(1/x) и R(x) = R(1 x).

16.10. Существует ли многочлен f(x, y) от двух вещественных переменных, который всюду отличен от нуля, но принимает значения, сколь угодно близкие к нулю?

16.11. Существует ли многочлен f(x) с целыми коэффициентами, который при некоторых различных вещественных x принимает одинаковые значения, но при всех различных рациональных значениях x принимает различные значения?

212 Глава 16. Примеры и конструкции 16.12. Можно ли разбить на пары 2n человек 2n 1 способами так, чтобы каждый человек был в паре с каждым другим ровно при одном разбиении?

16.13. а) Имеется кусок цепи из 60 звеньев, каждое из которых весит 1 г. Какое наименьшее число звеньев надо расковать, чтобы из образовавшихся частей можно было составить все веса в 1 г, 2 г, 3 г,..., 60 г (раскованное звено весит тоже 1 г)?

б) Тот же вопрос для цепи из 150 звеньев.

16.14. Можно ли провести в городе 10 автобусных маршрутов и установить на них остановки так, что какие бы 8 маршрутов ни были взяты, найдётся остановка, не лежащая ни на одном из них, а любые 9 маршрутов проходят через все остановки.

16.15. Дано n целых чисел a1 = 1, a2, a3,..., an, причём ai ai+1 2ai (i = 1, 2,..., n 1) и сумма всех чисел чётна. Можно ли эти числа разбить на две группы так, чтобы суммы чисел в этих группах были равны?

16.16. Радиолампа имеет семь контактов, расположенных по кругу и включаемых в штепсель, имеющий семь отверстий. Можно ли занумеровать контакты лампы и отверстия штепселя так, чтобы при любом включении лампы хотя бы один контакт попал на своё место (т. е. в отверстие с тем же номером)?

16.17. а) Имеется 555 гирь весом 1 г, 2 г, 3 г, 4 г,...

..., 555 г. Разложите их на три равные по весу кучи.

б) Имеется 81 гиря весом 12 г, 22 г, 32 г,..., 812 г.

Разложите их на три равные по весу кучи.

16.18. Рассматриваются всевозможные десятизначные числа, записываемые при помощи цифр 2 и 1. Разбейте их на два класса так, чтобы при сложении любых двух чисел каждого класса получилось число, в записи которого содержится не менее двух троек.

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

См. также задачу 20.9.

16.1. О т в е т: да, можно. Пусть p1,..., p10 — различные простые числа, N = p1... p10. Тогда числа N1 = p1 N,..., N10 = p10 N обладают требуемыми свойствами. Действительно, число Ni делится на p2, а число Nj, где j = i, делится только на pi, а на p2 оно уже не делится. С другой стороны, N2 делится на N2, а N2 делится на Nj.

16.2. а) Положим k = l! 1. Тогда k! l! = n!, где n = l!.

16.3. Для n = 2 можно взять числа 1 и 2. Пусть числа a1,...

..., an удовлетворяют требуемому условию. Покажем, что тогда числа A, A + a1,..., A + an, где A = a1... an, тоже удовлетворяют требуемому условию. Ясно, что A+ak +A делится на A+ak A=ak, поскольку A делится на ak. Проверим, что A + ai + A + aj делится на A + ai (A + aj ) = ai aj. По условию ai + aj делится на ai aj.

Кроме того, 2ai = (ai + aj ) + (ai aj ) делится на ai aj, а значит, 2A делится на ai aj.

16.4. а) О т в е т: бесконечно. Пусть, например, a = 2n б) О т в е т: бесконечно. Пусть, например, a = 2k + 1 и b= a2 1= = 2k+1 (2k1 + 1). Тогда у чисел a и b + 1 = a2 одинаковые простые делители. У чисел a + 1 = 2(2k1 + 1) и b = 2k+1 (2k1 + 1) тоже одинаковые простые делители.

16.5. Воспользуемся тождеством Рамануджана f2 = f4 = 0 из задачи 32.23. Положив a = 1, b = 2, c = 3 и d = 6, получим требуемый набор чисел 11, 6, 5 и 10, 9, 1.

16.6. О т в е т: для любого. Числа 1/n!, 2/n!,..., n/n! образуют арифметическую прогрессию длины n с разностью 1/n!. Эти числа имеют вид, где числа n!/k целые.

16.7. О т в е т: существует. Положим a1 = 2, a2 = 22 · 3, a3 = = 22 · 32 · 5,..., an = 22 · 32 ·... · p2 pn, где pn — n-е простое число.

Число ak + ak+l +... + ak+r делится на pk и не делится на p2, поэтому оно не может быть степенью натурального числа.

16.8. а) После перенумерации карточек можно считать, что карточки сложены в произвольном порядке, а сложить их нужно по порядку. Назовём беспорядком пару соседних карточек с номерами i и i + 1, на которых написаны числа ai > ai+1. Разобьём карточки на блоки, в которых нет беспорядков (блок может состоять из одной карточки). Любые два блока можно слить так, чтобы получился набор карточек без беспорядков и при этом в каждом блоке порядок карточек не изменился.

Первоначально количество блоков не превосходит 32. Снимем сверху первые 16 блоков и сольём блок с номером i с блоком с номером i + 16. После этого получится не более 16 упорядоченных блоков. Снимем теперь сверху первые 8 блоков и сольём блок с номером i с блоком с номером i + 8. После этой (второй) операции останется не более 8 блоков, после третьей операции на более 4 блоков, после четвёртой не более 2 блоков, а после пятой операции карточки будут упорядочены.

б) Если карточки расположены в обратном порядке, то количество беспорядков равно 31. Когда мы снимаем сверху часть карточек, один беспорядок пропадает и в двух наборах карточек вместе будет 30 беспорядков, поэтому в одной части будет не менее 15 беспорядков. Ясно также, что если между двумя карточками, образующими беспорядок, вставить любую карточку, то образуется по крайней мере один беспорядок. Значит, если между ними вставить несколько карточек, то всё равно образуется по крайней мере один беспорядок. Поэтому после первой операции останется не менее 15 беспорядков, после второй не менее 7, после третьей не менее 3, а после четвёртой операции останется не менее одного беспорядка.

16.9. При заменах x на 1 x и на 1/x из каждого числа можно получить всего шесть различных чисел: x, 1/x, 1 x,,,. Поэтому функция обладает требуемыми свойствами.

16.10. Да, существует. Пусть, например, f(x, y) = x2 + (xy 1)2.

Если f(x, y) = 0, то x = 0 и xy 1 = 0, чего не может быть. С другой т. е. y = 1 +. Тогда f(x, y) = 2.

16.11. О т в е т: существует. Пусть, например, f(x) = x3 2x.

Этот многочлен обращается в нуль при x = 0, ± 2. Предположим, что x = m/n и y = p/q — несократимые дроби (n > 0 и q > 0), причём f(x) = f(y). Тогда Числа p и q взаимно простые, поэтому числа p 2q и q тоже взаимно простые. Следовательно, n3 делится на q3. Аналогично q3 делится на n3, поэтому n = q. В таком случае равенство (1) переписывается в виде m3 2mq2 = p3 2pq2, т. е. m3 p3 = 2q2 (m p).

При m = p получаем m2 + pm + p2 = 2q2. Но в таком случае оба числа m и p чётные, а значит, число q тоже чётное. Это противоречит взаимной простоте чисел p и q.

16.12. О т в е т: да, можно. Поместим одного человека в центр окружности, а всех остальных расставим по окружности через равные промежутки. Разбиение на пары будем строить следующим образом. Выберем одного человека, стоящего на окружности, и проведём через него диаметр. Одну пару составляет выбранный человек и человек, стоящий в центре. Остальные пары составляют люди, стоящие в концах хорд, перпендикулярных проведённому диаметру.

16.13. а) О т в е т: 3 звена. Выясним, при каком наибольшем n достаточно расковать k звеньев n-звенной цепи, чтобы из образовавшихся частей можно было составить все целые веса от до n. Если расковано k звеньев, то любое число звеньев от 1 до k можно набрать из них. Но k + 1 звеньев мы не сможем набрать, если не будет части из k + 1 или менее звеньев (мы здесь не учитываем раскованные звенья). Наиболее выгодно иметь часть из ровно k + 1 звеньев. Тогда мы сможем получить любое число звеньев от 1 до 2k + 1. (Иначе мы сможем получить лишь число звеньев от 1 до l1 + k, где l1 k.) Затем наиболее выгодно иметь часть из 2(k + 1) звеньев, затем из 4(k + 1) звеньев и т. д.

Итак, если мы расковали k звеньев, то наиболее выгодна ситуация, когда полученные при этом k + 1 частей состоят из k + 1, 2(k + 1), 4(k + 1), 8(k + 1),..., 2k (k + 1) звеньев (раскованные звенья мы здесь не учитываем). В таком случае можно составить любое число звеньев от 1 до n = 2k+1 (k + 1) 1. Итак, если 2k k n 2k+1 (k + 1) 1, то можно обойтись k разрывами и нельзя обойтись k 1 разрывами. В частности, если 24 n 63, то наименьшее число раскованных звеньев равно 3. Полученные при расковке четыре части цепи должны состоять при этом из 4, 8, 16, 29 звеньев.

б) О т в е т: 4 звена. Согласно решению задачи а) для цепи, состоящей из n звеньев, где 64 n 159, достаточно расковать 4 звена.

16.14. О т в е т: да, можно. Проведём 10 попарно пересекающихся прямых. Пусть маршруты проходят по этим прямым, а остановками служат точки пересечения прямых. Любые 9 маршрутов проходят через все остановки, поскольку через каждую остановку, лежащую на оставшейся прямой, проходит одна из 9 прямых, соответствующих этим маршрутам. Любые 8 маршрутов не проходят через остановку, которая является точкой пересечения двух остальных маршрутов.

16.15. О т в е т: да, можно. Отнесём к одной группе число an, а к другой — число an1. Затем будем последовательно относить числа an2, an3 ,..., a1 к той группе, в которой сумма чисел меньше (если суммы равные, то число можно относить к любой группе). Пусть k 0 — разность между суммами чисел в группах, полученных после отнесения к ним ak. Покажем, что k ak. Действительно, n1 = an an1 2an1 an1 = an1. Ясно также, что если k ak, то k1 = |k ak1 | и ak1 k ak1 ak ak 2ak1 ak1 = ak1.

После того как мы распределим по двум группам все числа, получим группы с суммами S1 и S2, причём |S1 S2 | a1 = 1. По условию число S1 + S2 чётное, поэтому S1 = S2.

16.16. О т в е т: да, можно. Занумеруем контакты лампы по порядку, а отверстия штепселя — в противоположном порядке.

Тогда контакт с номером k попадает в отверстие с номером a k, где a — фиксированное число. (Точнее говоря, речь идёт не о самих номерах, а об их остатках от деления на 7, но номера совпадают тогда и только тогда, когда совпадают остатки.) Нам нужно выбрать k так, чтобы числа k и a k давали одинаковые остатки при делении на 7, т. е. число 2k давало такой же остаток, как и a.

Легко убедиться, что когда k пробегает все остатки при делении на 7, то 2k тоже пробегает все остатки.

16.17. а) Девять гирь весом n, n + 1,..., n + 8 можно разложить на три равные по весу кучи: 1) n, n + 4, n + 8; 2) n + 1, n + 5, n + 6;

3) n + 2, n + 3, n + 7. Это позволяет разложить на три равные по весу кучи гири весом 1, 2,..., 549 = 61 · 9. Оставшиеся шесть гирь весом 550, 551,..., 555 можно разложить на три равные по весу кучи следующим образом: 1) 550 и 555; 2) 551 и 554; 3) 552 и 553.

б) Разложим девять гирь весом n2, (n + 1)2,..., (n + 8)2 на три кучи следующим образом: 1) n2, (n + 5)2, (n + 7)2 ; 2) (n + 1)2, (n + 3)2, (n + 8)2 ; 3) (n + 2)2, (n + 4)2, (n + 6)2. Первые две кучи весят одинаково, а вес третьей кучи на 18 г меньше. Поэтому 27 гирь весом n2, (n + 1)2,..., (n + 26)2 можно разложить на 9 куч так, что 6 куч будут одного веса, а ещё 3 кучи будут весить каждая на 18 г меньше, чем первые 6. Из этих девяти куч можно сложить 3 равные по весу кучи. Таким образом, 27k гирь весом 12, 22, 32,..., (27k)2 можно разложить на 3 равные по весу кучи. При k = 3 получаем требуемое утверждение.

16.18. Отнесём к первому классу все числа, в записи которых встречается чётное число двоек, а ко второму классу — все числа, в записи которых встречается нечётное число двоек. Два числа одного класса либо содержат одинаковое число двоек, либо в одном числе двоек по крайней мере на две больше, чем в другом. Если два числа различны, то на каком-то месте в одном числе стоит 1, а в другом числе стоит 2; если же двоек у этих чисел одинаковое количество, то таких мест по крайней мере два. Если в одном числе двоек по крайней мере на две больше, чем в другом, то по крайней мере двум двойкам в записи первого числа соответствуют единицы в записи второго числа.

16.19. О т в е т: да, можно. Пусть A — квадрат со стороной 2n, который разбит на квадраты со стороной 1, и в каждом из них написано натуральное число. Сопоставим ему квадрат со стороной 2n+1. Если мы начнём с квадрата со стороной 1, в котором написано число 1, то последовательно заполним весь прямой угол. Ясно, что при этом в каждом квадрате со стороной 2n в каждом ряду квадратов со стороной 1, параллельном одной из сторон прямого угла, любое число от 1 до 2n встречается ровно один раз.

ПРИНЦИП ДИРИХЛЕ. ПРАВИЛО

КРАЙНЕГО

Самая популярная формулировка принципа Дирихле такова:

«Если в n клетках сидит m зайцев, причём m > n, то хотя бы в одной клетке сидят по крайней мере два зайца». На первый взгляд даже непонятно, почему это совершенно очевидное замечание является весьма эффективным методом решения задач.

Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь «зайцы» и «клетки» и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден;

далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле. А главное, этот метод даёт неконструктивное доказательство (мы, естественно, не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть), а попытка дать конструктивное доказательство, т. е. доказательство путём явного построения или указания требуемого объекта, может привести к гораздо большим трудностям.

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

З а м е ч а н и е. По поводу обратного утверждения см. задачу 9.3.

17.2. Докажите, что если натуральные числа a и b взаимно простые, то an 1 делится на b для некоторого натурального n.

17.3. Пусть p < q — натуральные числа, причём q не делится на 2 и на 5. Согласно задаче 17.2 можно выбрать n так, что 10n 1 делится на q. Докажите, что p/q — чисто периодическая дробь, длина периода которой делится на n.

17.4. Докажите, что из любых ста целых чисел можно выбрать одно или несколько чисел так, чтобы их сумма оканчивалась двумя нулями.

17.5. Из чисел 1, 2,..., n выбрано более различных чисел. Докажите, что одно из выбранных чисел делится на другое.

17.6. Простые числа a1, a2,..., ap образуют возрастающую арифметическую прогрессию и a1 > p. Докажите, что если p — простое число, то разность прогрессии делится на p.

17.7. Пусть n > 1 — натуральное число, e — наименьшее целое число, превосходящее n. Докажите, что для любого натурального числа a, взаимно простого с n, можно выбрать натуральные числа x и y, не превосходящие e 1, так, что ay ±x (mod n).

См. также задачу 15.10.

17.8. Докажите, что среди любых n 2 человек найдутся два человека, имеющих одинаковое число знакомых среди этих n человек.

17.9. Докажите, что любая последовательность из mn + попарно различных чисел содержит либо возрастающую последовательность из m + 1 чисел, либо убывающую последовательность из n + 1 чисел.

17.10. Числа [a], [2a],..., [Na] различны между собой, и числа [1/a], [2/a],..., [M/a] тоже различны между собой.

Найдите все такие a.

220 Глава 17. Принцип Дирихле. Правило крайнего 17.3. Приближения иррациональных чисел 17.11. Пусть — иррациональное число. Докажите, что существует бесконечно много пар взаимно простых чисел x, y, для которых |x/y | < 1/y2.

17.12. Пусть — положительное число. Докажите, что для любого числа C > 1 можно выбрать натуральное число x и целое число y так, что x < C и |x y| 1/C.

17.13. а) Пусть — иррациональное число. Докажите, что для любых чисел a < b можно выбрать целые числа m и n, для которых a < m n < b.

б) Докажите, что числа m и n можно выбрать натуральными.

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

17.14. На полях бесконечной шахматной доски написаны натуральные числа так, что каждое число равно среднему арифметическому четырёх соседних чисел — верхнего, нижнего, левого и правого. Докажите, что все числа на доске равны между собой.

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

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

17.17. Есть 13 гирь, каждая из которых весит целое число граммов. Известно, что любые 12 из них можно так разложить на 2 чашки весов, по 6 гирь на каждой, что наступит равновесие. Докажите, что все гири одного веса.

17.18. а) Из чисел 1, 2, 3, 4, 5, 6, 7,..., 199, 200 произвольно выбрали 101 число. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое.

б) Из двухсот чисел: 1, 2, 3,..., 199, 200 выбрали одно число, меньшее 16, и ещё 99 чисел. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое.

17.19. Из одной бактерии получилось n бактерий следующим образом. Сначала бактерия разделилась на две, затем одна из двух получившихся бактерий разделилась на две, затем одна из трёх получившихся бактерий разделилась на две и т. д. Докажите, что для любого натурального числа a n/2 в некоторый момент существовала бактерия, число потомков которой среди получившихся в конце n бактерий не меньше a и не больше 2a 1.

17.20. Взяли три числа x, y, z и вычислили абсолютные величины попарных разностей x1 = |x y|, y1 = |y z|, z1 = |z x|. Тем же способом по числам x1, y1, z1 построили числа x2, y2, z2 и т. д. Оказалось, что при некотором n получилось xn = x, yn = y, zn = z. Зная, что x = 1, найдите y и z.

17.21. Набору чисел a1, a2,..., an сопоставляется набор Затем с полученным набором чисел производится аналогичная операция и т. д. Докажите, что если при этом всегда будут получаться наборы целых чисел, то b1 = b2 =... = bn.

См. также задачу 19.6.

17.1. Достаточно рассмотреть рациональные числа вида p/q, где 1 p < q. В таком случае цифры десятичной записи p/q = 0,a1 a2 a3...

222 Глава 17. Принцип Дирихле. Правило крайнего 10k1 p = Mq + rk, где rk — остаток от деления 10k1 p на q. Тогда два одинаковых: ri = ri+n. Но rk+1 — остаток от деления 10rk на q.

Поэтому ri+1 = ri+n+1 и т. д. Значит, последовательность цифр ak тоже периодически повторяется (после номера i).

17.2. Два из чисел a, a2,..., ab+1 дают одинаковые остатки при делении на b. Пусть это будут числа ak и al, где k > l. Тогда ak al = al (akl 1) делится на b. Числа al и b взаимно простые, поэтому akl 1 делится на b.

+ rp · 102n + rp · 103n +... При этом rp < rq = 10n1.

17.4. Пусть a1,..., a100 — данные числа. Предположим, что ни одно из чисел S1 = a1, S2 = a1 + a2,..., S100 = a1 + a2 +... + a100 не делится на 100. Тогда при делении на 100 они могут давать только 99 разных остатков: 1, 2,..., 99. Поэтому два числа Sn и Sm, n > m, дают одинаковые остатки при делении на 100. Значит, число Sn Sm = am+1 +... + an делится на 100.

17.5. Сопоставим каждому выбранному числу его наибольший нечётный делитель. Количество нечётных чисел, не превосходящих n, равно n/2 при чётном n и (n + 1)/2 при нечётном n.

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

17.6. Рассмотрим остатки от деления чисел a1,..., ap на p. Числа a1,..., ap простые и все они строго больше p, поэтому ни одно из них не делится на p. Таким образом, мы получили p остатков, отличных от p. Следовательно, есть два числа ai и aj, дающие одинаковые остатки при делении на p. Поэтому их разность делится на p. Но ai aj = (i j)d, где d — разность прогрессии. Число |i j| строго меньше p, поэтому на p должно делиться число d.

17.7. Рассмотрим e2 чисел ay + x, где x, y = 0, 1, 2,..., e 1. Так как e2 > n, среди этих чисел найдутся числа ay1 + x1 и ay2 + x2 , дающие одинаковые остатки при делении на n. Следовательно, a(y1 y2 ) x2 x1 (mod n). Числа |y1 y2 | и |x1 x2 | не превосходят e 1, поэтому они могут делиться на n лишь в том случае, когда они равны 0. По условию число a взаимно просто с n. Поэтому x1 = x2 тогда и только тогда, когда y1 = y2. Следовательно, обладают требуемым свойством.

17.8. Сопоставим каждому из данных n человек число, равное количеству его знакомых среди этих n человек. Это число может принимать одно из n значений: 0, 1,..., n 1. Но если у кого-то вообще нет знакомых, то никто не может быть знаком со всеми.

Наоборот, если кто-то знаком со всеми, то нет человека, который ни с кем не знаком. Таким образом, количество знакомых принимает одно из не более чем n 1 значений. Поэтому для каких-то двух человек эти значения одинаковы.

17.9. Сопоставим члену ak данной последовательности два числа xk и yk, где xk — наибольшая длина возрастающей последовательности, начинающейся с ak, yk — наибольшая длина убывающей последовательности, начинающейся с ak. Предположим, что xk m и yk n для всех k. Тогда количество всех различных пар (xk, yk ) не превосходит mn. Поэтому xk = xl и yk = yl для некоторых номеров k = l. Но этого не может быть. Действительно, пусть для определённости k < l. Тогда если ak < al, то xk > xl, а если ak > al, Числа [x] и [y] различны тогда и только тогда, когда числа [x] и [y] различны. Поэтому достаточно рассмотреть случай, когда a > 0. Если a <, то среди чисел [a], [2a],..., [Na] есть совN падающие, поскольку эти N чисел содержатся среди N 1 чисел 0, 1,..., N 2. Поэтому a. Те же самые рассуждения для..., [Na] различны. Действительно, если a 1, то вообще все числа [a], [2a], [3a],... различны, а если a < 1, то 1 1/N a < 1,..., N. Для чисел [1/a], [2/a],..., M/a] рассуждения аналогичны.

17.11. Фиксируем натуральное число n. Дробные части чисел 0,, 2,..., n лежат в полуоткрытом интервале [0, 1), поэтому по крайней мере две из них попадают в один и тот же полуоткрытый интервал [k/n, (k + 1)/n), 0 k n 1. Это означает, что для некоторых целых чисел p1 и p2, удовлетворяющих неравенствам 0 p2 < p1 n. Положим y = p1 p2 и x = [p2 ] [p1 ]. Тогда |y x| < 1/n. Числа x и y здесь можно считать взаимно простыми, 224 Глава 17. Принцип Дирихле. Правило крайнего поскольку после деления их на НОД(x, y) требуемое неравенство Выберем теперь натуральное число n1 так, что |x/y | > 1/n1.

Описанная выше конструкция даёт пару целых чисел x1, y1, для которых |x1 /y1 | < < |x/y |. Так можно получить бескоn1 y нечно много различных пар чисел x, y.

17.12. Предположим сначала, что число C целое. Рассмотрим число 1 и числа k [k ] для k = 0, 1,..., C 1. Эти C + 1 чисел лежат на отрезке [0, 1], поэтому расстояние между какими-то двумя из них не превосходит 1/C. Если это окажутся числа k1 [k1 ] и k2 [k2 ], где k1 < k2, то положим x = k2 k1 и y = [k2 ] [k1 ].

Тогда 0 < x < C и Если же это окажутся числа k [k ] и 1, то положим x = k и y = [k ] + 1. Тогда Из этого, в частности, следует, что x = 0.

Пусть теперь число C не целое. Рассмотрим целое число C = = [C] + 1. Как только что было доказано, можно выбрать натуральное число x и целое число y так, что x < C и |x y| 1/C < 1/C.

Число C не целое, поэтому любое целое число, не превосходящее C, не превосходит и C. Следовательно, x < C.

17.13. а) Пусть = b a. Для каждого целого числа m1 можно выбрать целое число n1 так, что 0 m1 n1 1. Разделим отрезок [0, 1] на равные отрезки, длина каждого из которых меньше. Пусть количество этих отрезков равно k. Тогда среди чисел m1 n1,..., mk+1 nk+1 есть два числа, попадающих в один и тот же отрезок. Вычтем из большего числа меньшее:

mp np (mq nq ) = t. Ясно, что 0 t <. Более того, t = 0, Рассмотрим числа вида Nt, где N — целое число. Каждое из этих чисел имеет вид m n. А из того, что 0 < t <, следует, что хотя бы одно из этих чисел расположено строго между a и b.

б) Нужно доказать, что число t можно выбрать как вида M N, так и вида M + N, где M и N — натуральные числа.

Пусть t = M N. Между 0 и t есть бесконечно много чисел вида m n, m и n — целые. Предположим, что у всех этих чисел m > 0. Тогда для одного из них m > M, а в таком случае число t = M N (m n) искомое. Если же t = M + N, то рассуждения аналогичны.

17.14. Среди написанных чисел можно выбрать наименьшее.

Действительно, сначала возьмём произвольное написанное число n. Если есть число, которое меньше выбранного числа, то на следующем шаге выберем его и т. д. Этот процесс конечен, потому что всего мы можем выбрать не более n различных чисел.

Пусть m — наименьшее из написанных чисел, a, b, c, d — соседние с ним числа. Тогда a, b, c, d m и a + b + c + d = 4m. Поэтому Из любого поля шахматной доски можно попасть в любое другое поле, перемещаясь сначала по горизонтали, а затем по вертикали. Поэтому на всех полях написано одно и то же число m.

17.15. Рассмотрим квадрат, состоящий из 16 клеток, и вырежем из него 4 угловые клетки. Среди оставшихся 12 клеток выберем ту, в которой стоит наименьшее число (если таких клеток несколько, то выбираем любую из них). Выбранная клетка обладает требуемым свойством.

17.16. Предположим, что наибольшее число a стоит не с края.

Тогда у него в таблице есть все четыре соседних числа a1, a2, a3, a Поэтому a > (a1 + a2 + a3 + a4 )/4. Приходим к противоречию.

17.17. Сначала докажем, что все гири одновременно имеют либо чётный, либо нечётный вес. Пусть 12 гирь разложены на две чашки весов по 6 гирь так, что наступило равновесие. Предположим, что отложена гиря весом a г, а одна из гирь, лежащих на чашках, весит b г, причём числа a и b разной чётности. Заменим гирю a гирей b и снова разложим гири так, чтобы наступило равновесие. Вес гирь на каждой чашке весов изменился на |a b|, поэтому число |a b| чётно.

Предположим, что не все гири одинаковые. Вычтем из каждой гири вес наименьшей гири. В результате получим набор гирь, которые снова удовлетворяют условию задачи (по крайней мере одна из полученных гирь имеет нулевой вес). Все новые гири имеют чётный вес, строго меньший веса первоначальных гирь. Поделив вес каждой гири пополам (в том числе и гири с нулевым весом), мы снова получим набор гирь, удовлетворяющий условию задачи. Если при этом мы не получим гири нечётного веса, то снова поделим веса всех гирь пополам и т. д. В конце концов получим 226 Глава 17. Принцип Дирихле. Правило крайнего систему гирь, которая удовлетворяет условию задачи и в которой есть как гири чётного (нулевого) веса, так и гири нечётного веса.

Но мы уже доказали, что такого быть не может.

17.18. а) Рассмотрим наибольшие нечётные делители выбранных чисел. У чисел от 1 до 200 есть ровно 100 различных наибольших нечётных делителей (числа 1, 3,..., 199). Итак, два из выбранных чисел имеют одинаковые наибольшие нечётные делители. Это означает, что два выбранных числа отличаются только тем, что множитель 2 входит в них в разных степенях. Большее из них делится на меньшее.

б) Предположим, что из чисел 1, 2, 3,..., 199, 200 мы выбрали 100 чисел так, что ни одно из них не делится на другое. Достаточно доказать, что среди выбранных чисел нет чисел, меньших 16.

Рассмотрим наибольшие нечётные делители всех выбранных чисел. Если наибольшие нечётные делители двух чисел совпадают, то одно из них делится на другое. Поэтому наибольшие нечётные делители выбранных чисел — это в точности все числа 1, 3, 5,..., 199. В частности, среди выбранных чисел есть числа с наибольшими нечётными делителями 1, 3, 9, 27 и 81. Ни одно из выбранных чисел не делится на другое, поэтому выбранное число с наибольшим нечётным делителем 27 делится на 2, с наибольшим нечётным делителем 9 делится на 22, с наибольшим нечётным делителем 3 делится на 23, с наибольшим нечётным делителем делится на 24. Следовательно, среди выбранных чисел нет чисел 1, 2, 3, 4, 6, 8, 9 и 12. Далее, рассматривая выбранные числа с наибольшими нечётными делителями 5, 15 и 45, убеждаемся, что среди выбранных чисел нет чисел 5, 10 и 15; рассматривая выбранные числа с наибольшими нечётными делителями 7, 21 и 63, убеждаемся, что нет чисел 7 и 14; рассматривая выбранные числа с наибольшими нечётными делителями 11 и 33, убеждаемся, что нет числа 11; рассматривая выбранные числа с наибольшими нечётными делителями 13 и 39, убеждаемся, что нет числа 13.

17.19. Пусть некая бактерия, из которой в конце получилось m бактерий, разделилась на две бактерии. Из этих двух «сестёр»

в конце получилось m и m бактерий, причём m + m = m.

Значит, одно из чисел m и m не меньше m/2. Будем каждый раз выбирать ту из бактерий, у которой не меньше потомков, чем у её «сестры». В результате получим последовательность n = a1 > a2 >... > ak = 1, причём ai ai1 /2 (здесь ai — количество потомков выбранной бактерии). Выберем номер i так, что ai 2a > ai+1. Тогда ai+1 ai /2 a, а значит, a ai+1 2a 1.

17.20. О т в е т: y = z = 0. Числа xn, yn, zn неотрицательны, поэтому числа x, y, z тоже неотрицательны. Если бы все числа x, y, z были положительны, то наибольшее из чисел x1, y1, z1 было бы строго меньше наибольшего из чисел x, y, z, а тогда и наибольшее из чисел xn, yn, zn было бы строго меньше наибольшего из чисел x, y, z. Поэтому среди чисел x, y, z есть 0. Аналогично доказывается, что среди чисел x1, y1, z1 есть 0 (при n = 1 доказывать ничего не нужно, потому что тогда x1 = x, y1 = y, z1 = z).

Это означает, что два из чисел x, y, z равны. В итоге получаем, что неупорядоченный набор чисел x, y, z может быть равен либо 0, 0, 1, либо 0, 1, 1. Легко проверить, что второй набор не обладает требуемым свойством.

17.21. Предположим, что не все числа x1, x2,..., xn равны.

Пусть наибольшее из этих чисел равно N, причём оно встречается среди них ровно k раз. Тогда в новой последовательности нет чисел, превосходящих N, причём число N встречается не более k 1 раз. Поэтому после нескольких операций наибольшее значение уменьшится. Ясно также, что наибольшее значение не может стать меньше наименьшего значения чисел исходной последовательности. Поэтому после конечного числа операций все числа становятся равными.

Пусть набор равных чисел получается из набора x1, x2,..., xn.

Тогда x1 = x3, x2 = x4,..., xn1 = x1, xn = x2. Если n нечётно, то все числа x1,..., xn равны. Если n чётно, то x1 = x3 =... = xn1 = a и x2 = x4 =... = xn = b. Остаётся проверить, что если a = b, то такой набор чисел x1, x2,..., xn нельзя получить ни из какого набора и y2 + y3 +... + yn + y1 = 2nb. Поэтому a = b.

ИНВАРИАНТЫ И ПОЛУИНВАРИАНТЫ

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

Такую величину называют инвариантом. Ясно, что инвариант не может измениться не только при одном переходе, но и при нескольких переходах, поэтому значение инварианта в начальном и в конечном состоянии системы одно и то же.

На практике применение инвариантов к решению задач сводится к тому, что некоторая величина вычисляется двумя способами: сначала она просто вычисляется в начальном и конечном состоянии, а затем прослеживается её изменение при последовательных мелких переходах.

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

например, не увеличиваются (или не уменьшаются).

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

18.2. С тройкой чисел (a, b, c) разрешается проделать следующую операцию: одно число увеличить на 2, а два других одновременно с этим уменьшить на 1. Можно ли с помощью таких операций из тройки (13, 15, 17) получить тройку с двумя нулями?

18.3. В последовательности 1, 0, 1, 0, 1, 0,... каждый член начиная с седьмого равен последней цифре суммы шести предыдущих. Докажите, что в этой последовательности никогда не встретятся подряд шесть чисел 0, 1, 0, 1, 0, 1.

..., — произвольная перестановка чисел 1,..., n. Докажите, что 18.5. N солдат выстроены в одну шеренгу (плечом к плечу). По команде «налево» все одновременно повернулись на 90, но некоторые повернулись налево, а другие направо. Ровно через секунду каждый, кто оказался теперь лицом к лицу со своим соседом, поворачивается «кругом» — на 180. Ещё через секунду каждый, кто оказался теперь лицом к лицу со своим соседом, поворачивается на 180 и т. д.

а) Докажите, что каждый солдат повернётся «кругом» не более N 1 раз.

б) Докажите, что движение в строю не может продолжаться более N 1 секунд.

18.6. Целые числа x1, x2, x3, x4, x5, сумма которых положительна, расставлены по окружности. Если xi < 0, то числа xi1, xi, xi+1 разрешается заменить на xi1 + xi, xi, xi+1 + xi (подразумевается, что xi+5 = xi ). Докажите, что после конечного числа таких операций все числа станут неотрицательными.

Здесь мы рассматриваем понятие чётности перестановки чисел и доказываем, что это понятие определено корректно (задача 18.7). Понятие чётности перестановки применяется к анализу игры «15» (задача 18.8). Затем мы доказываем, что любая перестановка является композицией транспозиций (задача 18.9), 230 Глава 18. Инварианты и полуинварианты и приводим другие подходы к доказательству корректности определения чётности перестановки (задачи 18.10 и 18.11).

Транспозицией называют перестановку двух каких-то чисел в последовательности a1,..., an, т. е. при транспозиции последовательность a1,..., ai,..., aj,..., an заменяется на a1,..., aj,..., двумя разными способами получена посредством нескольких транспозиций: один раз m1 транспозициями, другой раз m2 транспозициями. Докажите, что m1 и m2 — числа одной чётности, т. е. число m1 m2 делится на 2.

18.8. Игра «15» заключается в следующем. В квадрате со стороной 4 расположено 15 фишек — квадратов со стороной 1. На фишках написаны числа от 1 до 15:

Любую фишку, граничащую (по стороне) со свободной клеткой, разрешается переместить на свободную клетку (освободив тем самым другую клетку). Можно ли поменять местами фишки 14 и 15, причём так, чтобы свободная клетка осталась на прежнем месте?

18.9. Докажите, что любую перестановку чисел 1,..., n можно получить из набора 1,..., n, сделав несколько транспозиций.

Перестановку чисел 1,..., n называют чётной, если её можно получить, сделав чётное число транспозиций; в противном случае её называют нечётной. Задача 18.7 показывает, что это определение корректно.

18.10. Пусть — некоторая перестановка чисел 1,..., n.

Назовём инверсией любую пару чисел i < j, для которой (i)>(j). Докажите, что чётность перестановки совпадает с чётностью числа всех инверсий.

Каждую перестановку чисел 1,..., n можно представить в виa 2 ) = a3,..., k ) = a1 и числа a1, a2,..., ak попарно различны. Тогда числа a1, a2,..., ak переставляются по циклу, и мы обозначим этот цикл (a1, a2,..., ak ). Отметим, что соответствующий цикл обозначаем (a1 ). Выберем теперь произвольное число от 1 до n, не вошедшее в первый цикл, и аналогично построим цикл, включающий это число. Продолжая действовать таким образом, мы сопоставим перестановке набор (12)(34).

18.11. а) Пусть перестановка чисел 1,..., n представляет собой произведение m циклов. Сделаем после этой перестановки транспозицию каких-либо двух чисел. Докажите, что в результате получится перестановка, которая представляет собой произведение m ± 1 циклов.

б) Докажите, что перестановка чётна тогда и только тогда, когда число n m чётно.

18.1. О т в е т: не смогут. Занумеруем деревья по часовой стрелке. Пусть в какой-то момент времени на k-м дереве сидит nk чижей. Рассмотрим сумму n1 + 2n2 +... + 44n44. Если один чиж перелетает на соседнее дерево по часовой стрелке, то эта сумма либо увеличивается на 1, либо уменьшается на 43, а если против часовой стрелки, то либо уменьшается на 1, либо увеличивается на 43. Поэтому при одновременных перелётах чижей остаток от деления рассматриваемой суммы на 44 не изменяется. Сначала равен 22. А если бы чижи собрались на одном дереве, то сумма делилась бы на 44. Поэтому чижи не смогут собраться на одном дереве.

232 Глава 18. Инварианты и полуинварианты З а м е ч а н и е. То же самое решение годится для произвольного чётного числа деревьев и чижей. Для нечётного числа легко строится пример, показывающий, что чижи могут собраться на одном дереве.

18.2. О т в е т: нельзя. При указанной операции первые два числа (a, b) заменяются либо на (a 1, b 1), либо на (a + 2, b 1), либо на (a 1, b + 2). Во всех трёх случаях остаток от деления числа a b на 3 не изменяется. Числа 13 и 15 дают разные остатки при делении на 3. Поэтому из тройки (13, 15, 17) нельзя получить тройку, состоящую из двух нулей и числа 45 = 13 + 15 + 17.

18.3. Будем заменять шестёрку чисел (x1,..., x6 ) на шестёрку чисел (x2, x3,..., x6, x7 ), где x7 — последняя цифра числа x1 +. .. + x6. Покажем, что при такой операции последняя цифра числа S(x1,..., x6 ) = 2(x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 ) не изменяется. Действительно, S(x2,..., x7 ) S(x1,..., x6 ) = 12x У чисел S(1, 0, 1, 0, 1, 0) = 18 и S(0, 1, 0, 1, 0, 1) = 24 последние цифры разные, поэтому в рассматриваемой последовательности не могут встретиться подряд шесть чисел 0, 1, 0, 1, 0, 1.

ai b(i) ai b(i) = (ak+1 ak )(b(k+1) b(k) ) 0.

то поменяем местами числа + 1) и В результате получим новую перестановку. Применим к ней ту же самую операцию и т. д. После нескольких таких операций получим пере- P становку n, n 1,..., 1. Это доказывает неравенство ai bni т. е. F(Y) < F(X). Это означает, что после каждой операции целое неотрицательное число F(X) строго уменьшается. Такой процесс не может продолжаться бесконечно долго.

18.7. Возьмём произвольные попарно различные числа x1,...

..., xn и рассмотрим число = ±1. Покажем, что если это число равно 1, то числа m1 и m2 чётные, а если оно равно 1, то числа m1 и m2 нечётные.

Предположим сначала, что — транспозиция, т. е. = j, Тогда в рассматриваемое произведение входит дробь = 1.

234 Глава 18. Инварианты и полуинварианты Легко также проверить, что для каждого k = i, j произведение соответствующих дробей для пар чисел (k, i) и (k, j) равно 1. Дейxi xk xj xk xk xi xk xj xk xj xk xi Таким образом, для одной транспозиции получаем число 1.

Если после транспозиции мы сделаем ещё транспозицию то для полученной в результате перестановки рассматриваемое число равно 1, поскольку т. е. рассматриваемые числа для и для перемножаются. Аналогично доказывается, что после каждой транспозиции рассматриваемое число меняет знак.

18.8. О т в е т: нет, нельзя. Сопоставим свободной клетке номер 16. Тогда после каждого хода получается некоторая перестановка чисел 1,.. ., 16. При этом каждый ход представляет собой транспозицию. Мы хотим в итоге получить транспозицию 14 15.

Покажем, что свободная клетка может вернуться на исходное место только после чётного числа ходов, т. е. чётного числа транспозиций. Согласно задаче 18.7 из этого следует, что так нельзя получить транспозицию.

Чтобы вернуться на исходное место, свободная клетка должна сделать вверх столько же ходов, сколько вниз, и влево столько же, сколько вправо. Поэтому общее число ходов должно быть чётно.

18.9. Достаточно доказать, что из любой перестановки...

..., можно получить набор 1,..., n, сделав несколько транспозиций (эти транспозиции можно будет сделать в обратном порядке). Если = 1, то поменяем местами 1 и Затем в новом 18.10. Достаточно доказать, что после каждой транспозиции изменяется чётность числа всех инверсий. Пусть при транспозиi) (j).

появиться или исчезнуть только для пар (i, k) и (j, k). Легко видеть, что появление или исчезновение инверсии может произойk) ти только в том случае, когда k заключено между i и j, а заключено между и Но в этом случае обе инверсии одновременно либо появляются, либо исчезают.

18.11. а) Пусть при транспозиции переставляются числа a и b.

Рассмотрим два случая.

Тогда после транспозиции из этого цикла получаются два цикла (a, a1,..., ap ) и (b, b1,..., bq ), поскольку a a1, a2 a3,...

меняются.

..., bq ). Тогда после транспозиции из этих двух циклов получится один цикл (a, a1,..., ap, b, b1,..., bq ), поскольку a a1,...

б) Разобьём все перестановки на два класса: те, для которых число n m чётно, и те, для которых число n m нечётно. Первый класс содержит тождественную перестановку 1, 2,..., n (для неё n m = 0). Второй класс содержит все транспозиции (для них n m = 1). Согласно задаче а) применение транспозиции изменяет класс. Поэтому перестановки, которые получаются из тождественной чётным числом транспозиций, лежат в первом классе, а перестановки, которые получаются из тождественной нечётным числом транспозиций, лежат во втором классе.

ЛОГИКА

19.1. В трёх ящиках лежат шары — чёрный, белый и зелёный (в каждом ящике по одному шару). На первом ящике написано «белый», на втором — «чёрный», на третьем — «белый или зелёный». Известно, что ни одна надпись не соответствует действительности. Выясните, где какие шары лежат.

19.2. Путешественник попал на остров, часть обитателей которого всегда говорит правду, а остальные всегда лгут.

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

19.3. Один человек всегда говорит правду, а другой человек всегда лжёт. Какой вопрос нужно им задать, чтобы они ответили на него одинаково?

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

19.5. Дано 8 предметов, один из которых выделен. Требуется задать 3 вопроса, на которые даются только ответы «да» и «нет», и узнать, какой предмет выделен.

19.6. В институте работают правдолюбы, которые всегда говорят правду, и лжецы, которые всегда лгут. Однажды каждый из сотрудников сделал два заявления.

1) В институте нет и десяти человек, которые работают больше меня.

2) В институте по крайней мере у ста человек зарплата больше, чем у меня.

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

19.7. Три мудреца сидят на стульях в затылок друг другу так, что сидящий впереди не видит тех, кто сидит сзади.

Они знают, что есть 3 белых и 2 чёрных шляпы. Мудрецы зажмуривают глаза и им на головы надевают шляпы, после чего оставшиеся шляпы убирают. Мудрецы открывают глаза, и сидящий сзади всех говорит, что он не знает, какого цвета на нём шляпа. После этого сидящий посредине говорит, что он тоже не знает, какого цвета на нём шляпа. Знает ли теперь сидящий впереди, какого цвета на нём шляпа?

19.8. В вагоне поезда едут несколько мудрецов. Когда поезд проехал туннель, в окна попала пыль. Вошёл проводник и сказал: «У некоторых из вас испачкались лица. К сожалению, в поезде нет воды. Но сейчас будут большие остановки, поэтому можно будет выйти из поезда и умыться.» На n-й остановке испачкавшиеся мудрецы вышли из поезда, чтобы умыться. Сколько мудрецов испачкалось? (Мудрец идёт умываться тогда и только тогда, когда он точно знает, что испачкался.) П а р а д о к с л ж е ц а. Некто произносит фразу: «Высказывание, которое я сейчас произношу, ложно». Ложно само это высказывание или нет?

Если допустить, что это высказывание истинно, то оно должно быть ложным, а если допустить, что это высказывание ложно, то оно должно быть истинным.

П а р а д о к с п а р и к м а х е р а. Деревенский парикмахер бреет тех и только тех жителей своей деревни, которые не бреют себя сами. Бреет ли он себя?

Если допустить, что он не бреет себя, то он должен себя брить, а если допустить, что он бреет себя, то он не должен себя брить.

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

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

Пусть p и q — некоторые высказывания, каждое из которых может быть либо истинным (И), либо ложным (Л). Из них можно составить следующие составные высказывания:

¬p — отрицание: «p неверно»;

p & q — конъюнкция: «верны p и q»;

p q — дизъюнкция: «верно p или q»;

p q — импликация: «p влечёт q», т. е. q верно, если p верно;

p q — эквивалентность: «p эквивалентно q».

Эти составные высказывания имеют следующие таблицы истинности:

И И Л И И И И

И Л Л Л И Л Л

Л И И Л И И Л

Л Л И Л Л И И

Для конъюнкции часто используется также обозначение, а для эквивалентности — обозначение.

19.9. Выпишите таблицу истинности для каждого из следующих высказываний: а) p & (¬p); б) p (¬p); в) ¬(p & q);

г) (p q) (¬p).

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

19.10. Являются ли следующие высказывания тавтологиями: а) p (¬p); б) (¬(¬p)) p; в) ((p q) p) p;

г) ¬(p & (¬p))?

19.11. Докажите, что следующие высказывания эквивалентны, т. е. имеют одинаковые таблицы истинности: p & q и ¬((¬p) (¬q); p q и ¬((¬p) & (¬q); p q и (¬q) (¬p);

19.12. Докажите, что для любой данной таблицы истинности с помощью связок &, ¬ и можно составить высказывание, имеющее данную таблицу истинности, в случае:

а) одной переменной; б) двух переменных; в) n переменных.

19.13. Часть жителей острова всегда говорит правду, а остальные всегда лгут. Путешественник хочет выяснить, какая из двух дорог ведёт в деревню A, задав один вопрос встретившемуся ему местному жителю. Сможет ли он это сделать?

19.1. В третьем ящике может лежать только чёрный шар. Белый шар может лежать только во втором ящике. Зелёный шар лежит в первом ящике.

19.2. Нужно задать такой вопрос: «Если бы ты всегда говорил правду, то как бы ты ответил на вопрос: „Ты лжец?“?» Тот, кто всегда говорит правду, на этот вопрос ответит: «нет», а тот, кто всегда лжёт, ответит: «да».

19.3. «Ты всегда говоришь правду?»

19.4. «Я тебя сегодня о чём-нибудь спрашивал?»

19.5. Занумеруем предметы номерами от 0 до 7. Зададим вопросы, входит ли выделенный предмет в группы {0, 2, 4, 6}, {0, 1, 4, 5} и {0, 1, 2, 3}. Пусть i = 0, если на i-й вопрос получен ответ «да», и i = 1 в противном случае. Тогда выделенный предмет имеет Действительно, запишем номера предметов в двоичной системе счисления: a0 + a1 · 2 + a2 · 4, где ai = 0 или 1. Тогда k-й вопрос можно переформулировать так: «Равно ли ak1 нулю?»

19.6. О т в е т: 110. Из первого заявления для правдолюба с наименьшей нагрузкой следует, что в институте не более 10 правдолюбов, а для лжеца с наибольшей нагрузкой — что в институте не менее 10 правдолюбов. Из второго заявления для правдолюба с самой большой зарплатой следует, что в институте не менее 100 лжецов, а для лжеца с самой маленькой зарплатой — что в институте не более 100 лжецов. Таким образом, в институте работает 10 правдолюбов и 100 лжецов.

19.7. О т в е т: сидящий впереди знает, что на нём белая шляпа.

Если бы на двух передних мудрецах были чёрные шляпы, то сидящий сзади мудрец знал бы, что на нём белая шляпа. Значит, хотя бы на одном из них шляпа белая. Поэтому если бы на сидящем впереди мудреце была бы чёрная шляпа, то сидящий посредине понял бы, что на нём самом — белая. Значит, на мудреце, сидящем впереди, шляпа белая.

19.8. Докажем, что если испачкалось n мудрецов, то все они пойдут умываться на n-й остановке. При n = 1 это очевидно: испачкавшийся мудрец видит, что все остальные не испачкались, причём он знает, что кто-то испачкался. Предположим, что требуемое утверждение доказано, если испачкалось не более n мудрецов.

Рассмотрим случай, когда испачкалось n + 1 мудрецов. Каждый из испачкавшихся мудрецов рассуждает так. Возможны два варианта: (1) я не испачкался, (2) я испачкался. При первом варианте испачкалось n мудрецов; они выйдут на n-й остановке. Поэтому до n-й остановки мне не следует выходить, потому что первый вариант остаётся возможным. Но если на n-й остановке никто не выйдет, то, значит, я испачкался.

19.9. О т в е т: а) ЛЛ; б) ИИ; в) ЛИИИ; г) ИИИИ.

19.10. О т в е т: да, являются. В случае в) достаточно заметить, что для высказывания (p q) p таблица истинности имеет вид ИИЛЛ.

19.11. Все требуемые таблицы истинности легко составляются.

19.12. а) Легко видеть, что высказывания p, ¬p, p & ¬p и p ¬p соответствуют всем возможным таблицам истинности.

б) Высказывания p & q, p & (¬q), ¬p & q и ¬p & (¬q) принимают значение И ровно для одного из четырёх возможных наборов значений переменных p и q. Чтобы получить высказывание, принимающее значение И на двух, трёх или четырёх наборах, можно применить дизъюнкцию. Например, высказывание (p & q) (p & ¬q) принимает значение И, если (p, q) = (И,И) или (p, q) = (И,Л).

Высказывание p &¬p принимает значение Л для всех наборов переменных. Теперь мы построили требуемые высказывания для всех таблиц истинности. Отметим, что высказывание, принимающее значение И на всех четырёх наборах переменных, можно построить проще, а именно, взять высказывание p ¬p.

б) Решение для n переменных точно такое же, как для двух переменных. Высказывание p1 & ¬p1 принимает значение Л для всех наборов переменных. Высказывания p1 & p2 &... & pn, ¬p1 & p2 &...

... & pn и т. д. принимают значение И ровно для одного набора значений переменных (всего можно составить 2n таких высказываний — столько же, сколько есть разных наборов значений переменных). Высказывание, принимающее значение И в точности для данных наборов значений, составляется из этих высказываний с помощью дизъюнкции.

19.13. Пусть p — это утверждение, что дорога ведёт в A, q — это утверждение, что встретившийся местный житель правдив. Получаем следующую таблицу желаемых ответов и, соответственно, таблицу истинности требуемого высказывания (она, естественно, составляется на основе того, что правдивый говорит правду, а лжец лжёт):

Требуемое высказывание строится теперь так, как описано в решении задачи 19.12. Это будет высказывание (p&q)(¬p&¬q).

Таким образом, нужно задать вопрос: «Верно ли, что ты правдив и эта дорога ведёт в A, или что ты лжец и эта дорога не ведёт в A?»

Житель ответит «Да» тогда и только тогда, когда дорога ведёт в A.

З а м е ч а н и е. Легко проверить, что таблица истинности построенного высказывания (p & q) (¬p & ¬q) совпадает с таблицей истинности высказывания p q. Поэтому можно задать вопрос:

«Верно ли, что ты правдив тогда и только тогда, когда эта дорога ведёт в A?»

СТРАТЕГИИ. ТУРНИРЫ. ТАБЛИЦЫ

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

20.2. Три солдата и три разбойника должны переправиться через реку. Они нашли лодку, в которую помещаются только два человека. На каждом берегу солдаты не могут оставаться, если их меньше, чем разбойников. Как им всем переправиться через реку?

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

У них есть один фонарик. Мост выдерживает только двоих.

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

20.6. Есть полный кувшин молока ёмкостью 12 литров и два пустых кувшина в 8 литров и 5 литров. Как разделить молоко на две равные части?

20.7. Есть четыре бочки. В первую входит 24 ведра, во вторую 13, в третью 11, в четвёртую 5. Первая бочка наполнена водой, а остальные бочки пустые. Как разделить воду на три равные части?

При решении задач о турнирах нужно знать следующие правила:

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

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

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

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

20.10. а) В шахматном турнире участвовали два ученика 7 класса и некоторое число учеников 8 класса. Два семиклассника набрали 8 очков, а каждый из восьмиклассников набрал одно и то же число очков. Сколько восьмиклассников участвовало в турнире? Найдите все возможные решения.

б) В шахматном турнире участвовали ученики 9 и классов. Десятиклассников было в 10 раз больше, чем 244 Глава 20. Стратегии. Турниры. Таблицы девятиклассников, и они набрали вместе в 4,5 раза больше очков, чем все девятиклассники. Сколько очков набрали девятиклассники?

20.11. В соревнованиях участвуют 2n боксёров. Каждый день проходят бои 2n1 пар боксёров (каждый боксёр проводит ровно один бой). Все боксёры имеют разную силу, и в каждом бою побеждает сильнейший. Докажите, что за n(n + 1)/2 дня можно определить место каждого боксёра.

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

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

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

20.15. Есть n мешков, в каждом из которых достаточно много монет. Есть несколько разных сортов монет. Монеты разного сорта имеют разный вес, причём их веса различаются на целое число граммов. Вес монеты каждого сорта известен. В каждом мешке лежат монеты одного сорта, но количество мешков с монетами данного сорта может быть произвольным. Как при помощи одного взвешивания на веУсловия задач сах с разновесками выяснить, какого сорта монеты лежат в каждом мешке?

20.16. Некоторые из 20 металлических кубиков, одинаковых по размерам и внешнему виду, алюминиевые, остальные* дюралевые (более тяжёлые). Как при помощи 11 взвешиваний на весах с двумя чашками без гирь определить число дюралевых кубиков?

20.17. а) Дано (3n 3) монет (n 2), среди которых есть одна фальшивая монета, отличающаяся по весу от настоящей. За n взвешиваний на чашечных весах без гирь нужно найти фальшивую монету и выяснить, тяжелее она или легче, чем настоящая.

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

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

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

20.19. Квадратная таблица в n2 клеток заполнена числами от 1 до n так, что в каждой строке и каждом столбце встречаются все эти числа. Докажите, что если n нечётно и таблица симметрична относительно диагонали, идущей из * Предполагается, что все кубики могут быть алюминиевыми, но они не могут быть все дюралевыми (если все кубики окажутся одного веса, то нельзя выяснить, алюминиевые они или дюралевые).

246 Глава 20. Стратегии. Турниры. Таблицы левого верхнего угла в правый нижний, то на этой диагонали встретятся все числа 1, 2, 3,..., n.

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

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

б) Сумма чисел, стоящих на двух диагоналях, равна 112.

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

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

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

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

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

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

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 троек чисел — в точности тройки чисел, лежащих на одной прямой в таблице Таким образом, цель играющего состоит в том, чтобы занять в этой таблице три клетки на одной вертикали, горизонтали или диагонали.

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

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

Пусть было сыграно a турниров первого вида, b — второго, c — третьего. Тогда у Алика b + c проигрышей, у Бори и Васи a + b + c и a проигрышей. У Бори 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 принимает одно из значений 1, 2, 7, 14. Значения 1 и отпадают, поскольку в этих случаях число y будет отрицательным.

Задача имеет два ответа: x = 7 и x = 14.

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

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

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

Поэтому те пары боксёров {Xi, Yj }, между которыми необходимо провести бой, определены так, что ни один из боксёров не входит в две группы.

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

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

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

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

20.15. Пусть вес самой лёгкой монеты равен a грамм, а вес самой тяжёлой монеты равен a + d 1 грамм. Занумерует мешки числами 0, 1, 2,..., n 1 и возьмём из мешка с номером i ровно di монет. Тогда если в мешке с номером i лежат монеты веса a + mi, то вес выбранных монет превышает вес такого же количества самых лёгких монет на m0 +m1 d+m2 d2 +...+mn1 dn1.

Это число можно узнать при помощи одного взвешивания. Кроме того, 0 mi d 1. Поэтому, записав полученное число в d-ичной системе счисления, мы узнаем все числа m0, m1,..., mn1.

20.16. Положим на чашки весов по одному кубику. Возможны два случая.

С л у ч а й 1. При первом взвешивании один из кубиков оказался тяжелее.

В этом случае один выбранный кубик алюминиевый, а другой дюралевый. Положим выбранные кубики на одну чашку и будем с ними сравнивать остальные кубики. А именно, оставшиеся 18 кубиков разбиваем на 9 пар и поочерёдно кладём их на другую чашку. Каждый раз мы узнаём, сколько в паре дюралевых кубиков. Действительно, если эталонная пара легче, то мы положили два дюралевых кубика; если эталонная пара имеет тот же самый вес, то мы положили один алюминиевый и один дюралевый кубик;

если эталонная пара тяжелее, то мы положили два алюминиевых кубика. Таким образом, в первом случае достаточно 10 взвешиваний.

С л у ч а й 2. При первом взвешивании кубики оказались равного веса.

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

Пусть первые k пар оказались того же самого веса, а (k + 1)-я 252 Глава 20. Стратегии. Турниры. Таблицы пара оказалась другого веса. (Если k = 9, то все кубики одного веса, поэтому дюралевых кубиков нет.) Пусть для определённости (k + 1)-я пара оказалась более тяжёлой. Тогда первые два кубика и кубики первых k пар алюминиевые. Положим на каждую чашку весов по одному кубику (k + 1)-й пары. Если эти кубики одного веса, то они оба дюралевые. Если кубики разного веса, то один алюминиевый, а другой дюралевый. В обоих случаях мы можем составить пару кубиков, один из которых алюминиевый, а другой дюралевый. Оставшиеся пары кубиков мы можем сравнивать с этой парой, как и в первом случае. Общее число взвешиваний во втором случае равно 11.

20.17. а) Рассмотрим все n-значные числа в троичной системе счисления, за исключением чисел 00... 0, 11... 1 и 22... 2. Разобьём эти числа на пары так, чтобы сумма чисел в каждой паре была равна 22... 2. Каждой монете сопоставим одну из таких пар.

Будем называть правым маркером монеты то из чисел соответствующей ей пары, для которого первая пара неравных цифр — это 01, 12 или 20. Другое число будем называть левым маркером. Для него первая пара неравных цифр — это 21, 10 или 02.

При k-м взвешивании положим на одну чашку весов те монеты, у которых k-й разряд правого маркера равен 0, а на вторую чашку — те монеты, у которых k-й разряд правого маркера равен 2.

Если перевесит первая чашка, то положим ak = 0; если перевесит вторая чашка, то положим ak = 2; если чашки уравновесятся, то положим ak = 1. Покажем, что тогда a1 a2... an — маркер фальшивой монеты, причём он левый, если фальшивая монета легче настоящей, и правый, если фальшивая монета тяжелее.

Прежде всего заметим, что на каждую чашку весов кладётся одинаковое число монет; более того, монет, у которых k-й разряд правого маркера равен 0, 1, 2, одинаковое число. Чтобы это доказать, нужно рассмотреть циклическую перестановку цифр 0120; при такой замене цифр каждый правый маркер переходит в некоторый другой правый маркер, и в результате правые маркеры разбиваются на тройки.

Предположим, что k-й разряд правого маркера фальшивой монеты равен 1. Тогда на обеих чашках весов при k-м взвешивании лежат настоящие монеты, поэтому ak = 1. Именно так и должно быть (k-й разряд левого маркера тоже равен 1).

Предположим, что k-й разряд правого маркера фальшивой монеты равен 0. Тогда при k-м взвешивании фальшивая монета лежит на первой чашке весов. Если фальшивая монета тяжелее настоящей, то ak = 0 (k-й разряд правого маркера тоже равен 0).

Если фальшивая монета легче настоящей, то ak = 2 (k-й разряд левого маркера тоже равен 2). Случай, когда k-й разряд правого маркера фальшивой монеты равен 2, разбирается аналогично.

б) Основная трудность, которая возникает в случае, когда коn личество монет меньше (3 3), связана с тем, что если мы применим ту же самую систему взвешиваний, то на одной чашке весов может оказаться меньше монет, чем на другой. Чтобы преодолеть эту трудность, воспользуемся разбиением правых маркеров на тройки, которое возникает при циклической перестановке цифр 0 1 2 0. Кроме того, выделим тройку правых маркеров 00... 01, 11... 12 и 22... 20. Эти маркеры мы не будем использовать до тех пор, пока это возможно.

Будем разбивать монеты на тройки до тех пор, пока это возможно. Каждой тройке монет сопоставим тройку правых маркеров (и соответствующих им левых маркеров); при этом выделенную тройку маркеров мы не используем. Если остаётся одна монета, то ей сопоставляем маркер 11... 12, а если остаются две монеты, то им сопоставляем маркеры 00... 01 и 22... 20.

Для первых n 1 взвешиваний можно применить прежние правила. Более того, если количество монет делится на 3, то последнее взвешивание тоже можно сделать по прежним правилам.

Предположим, что осталась одна монета с маркером 11... 12.

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

Предположим, что остались две монеты с правыми маркерами 00... 01 и 22... 20; им соответствуют левые маркеры 22... и 00... 02. Если после первых n1 взвешиваний получается число, отличное от 00... 0 и 22... 2, то фальшивая монета отлична от двух выделенных монет. Поэтому последнее взвешивание можно сделать без них. Если же после n 1 взвешиваний получается число 00... 0 или 22... 2, то мы знаем, что фальшивая монета — одна из двух выделенных, причём мы знаем, какая из выделенных монет легче. Сравнив одну из этих монет с настоящей, мы узнаем, какая монета фальшивая, и узнаем, легче она настоящей или тяжелее.

254 Глава 20. Стратегии. Турниры. Таблицы чисел в строках, y1,..., ym — суммы чисел в столбцах. На пересечении i-й строки и j-го столбца стоит число xi yj. Поэтому сумма чисел в i-й строке равна xi y1 + xi y2 +... + xi ym. С другой стороны, эта сумма равна xi. Таким образом, xi = xi (y1 + y2 +... + ym ). Число xi положительно; в частности, оно отлично от нуля, поэтому y1 + y2 +... + ym = 1. Но сумма y1 + y2 +... + ym это как раз и есть сумма всех чисел в таблице.

S = aij мы получили уравнение S2 = S. Но S > 0, поэтому S = 1.

б) Пусть x1,..., xn — суммы чисел в строках, y1,..., ym — суммы чисел в столбцах. На пересечении i-й строки и j-го столбца стоит число xi yj. Поэтому сумма чисел в i-й строке равна xi y1 + xi y2 +... + +xi ym. С другой стороны, эта сумма равна xi.

Таким образом, xi =xi (y1 +y2 +...+ym ). Сумма y1 +y2 +...+ym — это как раз сумма всех чисел в таблице. Если она не равна 1, то xi = 0.

Аналогично доказывается, что в таком случае все числа x1,..., xn, y1,..., ym равны 0. Но тогда и все числа xi yj тоже равны 0.



Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |


Похожие работы:

«Министерство образования Республики Беларусь УО ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра уголовного права и криминалистики УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ для самоподготовки и самоконтроля для студентов заочной формы обучения по дисциплине АДМИНИСТРАТИВНОЕ ПРАВО для специальности 24-01-02 Правоведение г. Новополоцк, 2013 Рассмотрены и рекомендованы к утверждению на заседании кафедры уголовного права и криминалистики, протокол №_ от _ _ 2012 г. Заведующий кафедрой И.В. Вегера Составитель:...»

«Методические и иные документы для обеспечения образовательного процесса 1. Учебно-методическое обеспечение для самостоятельной работы студентов Яцун С. Ф. Механика: учебное пособие. Ч. 1 / С. Ф. Яцун, В. Я. Мищенко. Курск: КГТУ, 2004. - 208 с. Яцун С. Ф. Механика: Учебник для студентов вузов: В 2 ч. Ч. 2 / С. Ф. Яцун, В. Я. Мищенко. - Курск: КГТУ, 2004. - 140 с. Теория механизмов и машин :[Текст] : методические рекомендации по курсовому проектированию / сост.: С. Ф. Яцун, Б. В. Лушников, В. Я....»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования УЛЬЯНОВСКИЙ ГОСУДАРСВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ МАТЕМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ Кафедра телекоммуникационных технологий и сетей С.В. Липатова Сборник задач по курсу Интеллектуальные информационные системы Учебное пособие Ульяновск Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) УДК 004. Печатается по решению Ученого совета...»

«РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ ПРОБЛЕМ ОСВОЕНИЯ СЕВЕРА МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНСТИТУТ ГОСУДАРСТВА И ПРАВА Н.М. Добрынин КОНСТИТУЦИОННОЕ (ГОСУДАРСТВЕННОЕ) ПРАВО РОССИЙСКОЙ ФЕДЕРАЦИИ Учебное пособие Современная версия новейшей истории государства Рекомендовано...»

«НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ СМОЛЕНСКИЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ, ЭКОНОМИКИ И ДИЗАЙНА КАФЕДРА МАТЕМАТИКИ И ИНФОРМАТИКИ Прогнозирование, проектирование и моделирование в социальной работе УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ по дисциплине ПРОГНОЗИРОВАНИЕ, ПРОЕКТИРОВАНИЕ И МОДЕЛИРОВАНИЕ СОЦИАЛЬНОЙ РАБОТЫ для студентов, обучающихся по специальности (для студентов специальности 040101.65 Социальная работа) — очная,...»

«Author: Таксанов Алишер Арсланович Смотришь в книгу, видишь. Учебники от Ислама Кар    Ислам Каримов велик. Но еще велика его деятельность для государства с великим будущим. Поэтому не зря в Узбекистане появились учебные пособия, в которых с разных сторон описываются мировоззрение, позиция, руководство президента по тому или иному явлению, имеющему место во времени и в пространстве. Ведь нет такой области человеческой деятельности, в которой бы он не разбирался. Вспомните, как объяснял он...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ ЮРИДИЧЕСКАЯ АКАДЕМИЯ имени О. Е. КУТАФИНА КАФЕДРА МЕЖДУНАРОДНОГО ПРАВА Учебно-методический комплекс по курсу ТАМОЖЕННОЕ ПРАВО для студентов всех форм обучения на 2010/11, 2011/12, 2012/13 учебные годы МОСКВА 2010 ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКАЯ...»

«Учреждение образования Белорусский государственный технологический университет УТВЕРЖДЕНА Ректором БГТУ профессором И.М. Жарским 17.05.2011 г. Регистрационный № УД-546 /баз. ТЕХНОЛОГИЯ ЛИСТОВОГО И ПОЛОГО СТЕКЛА Учебная программа для специальности 1-48 01 01 Химическая технология неорганических веществ, материалов и изделий специализаций 1-48 01 01 06 Технология стекла и ситаллов; 1-48 01 01 10 Технология эмалей и защитных покрытий 2011 г. УДК 666.151(073) ББК 35.41я73 Т 38 Рекомендована к...»

«Государственное образовательное учреждение высшего профессионального образования Московская академия рынка труда и информационных технологий Дворец Н.Н. ТЕОРИЯ И ПРАКТИКА ФИНАНСОВОГО ОЗДОРОВЛЕНИЯ ПРЕДПРИЯТИЯ Учебно-методическое пособие Москва Издательство МАРТИТ 2010 1 УДК 330.1 ББК 65.01 Д-24 Дворец Н.Н., Теория и практика финансового оздоровления предприятия: Учебно-методическое пособие. М.: Изд-во МАРТИТ, 2010. 101 с. В пособии рассмотрены следующие темы: правовое содержание процедур...»

«Н.А. Троицкая, М.В. Шилимов ТранспорТноТехнологические схемы перевозок оТдельных видов грузов Допущено УМО вузов РФ по образованию в области транспортных машин и транспортно-технологических комплексов в качестве учебного пособия для студентов вузов, обучающихся по специальности Организация перевозок и управление на транспорте (автомобильный транспорт) направления подготовки Организация перевозок и управление на транспорте УДК 629.3(075.8) ББК 39.3-08я73 Т70 Рецензенты: В. М. Беляев, д-р техн....»

«ПРОГРАММА ИТОГОВОГО ГОСУДАРСТВЕННОГО ЭКЗАМЕНА I. Пояснительная записка 1.1. Программа итогового государственного экзамена составлена на основе Государственного образовательного стандарта высшего профессионального образования (2005 г.), Типового положения о высшем учебном заведении (2008 г.), Положения об итоговой государственной аттестации выпускников высших учебных заведений Российской федерации (2003 г.), Методических рекомендаций по проведению итоговой государственной аттестации выпускников...»

«Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования Рязанский государственный университет имени С.А. Есенина Утверждено на заседании кафедры психологии личности, специальной психологии и коррекционной педагогики Протокол № 5 от 16.01.2009 г. Зав. кафедрой д-р психол. наук, проф. Н.А. Фомина ОБУЧЕНИЕ И ВОСПИТАНИЕ ДЕТЕЙ С НАРУШЕНИЕМ ИНТЕЛЛЕКТА Программа дисциплины и учебно-методические рекомендации Для...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Московский государственный агроинженерный университет имени В.П. Горячкина Загинайлов В.И.ам, Меренков А.А., Соболев А.В. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЭЛЕКТРОТЕХНИКИ Методические рекомендации по изучению дисциплины и задания на выполнение контрольных работ для студентов заочной формы обучения электротехнических специальностей Москва 2009 УДК 621.3.011.7.(075.8) Рецензент Кандидат технических наук, профессор кафедры автоматизированного электропривода...»

«1 2 Содержание: Пояснительная записка 1 4 Планируемые результаты (компетенции) обучения 2 7 Тематический план дисциплины 3 8 Содержание рабочей учебной программы дисциплины 4 10 Основное содержание 5 15 Контрольные работы 6 28 Самостоятельная работа 7 39 Грамматический материал для самостоятельного 8 40 изучения Лексический материал 9 Контрольные задания 10 Литература 11 Пояснительная записка Настоящее пособие включает рабочую программу, методические указания и контрольные задания для студентов...»

«СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ Г.Ф. Быстрицкий Общая энергетика Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов образовательных учреждений среднего профессионального образования Рекомендовано Учебно-методическим советом Института электротехники МЭИ (ТУ) в качестве учебного пособия для студентов электротехнических специальностей вузов по направлению обучения Электротехника, электромеханика и электротехнологии Второе издание, исправленное и...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Юго-Западный государственный университет Кафедра уголовного права УТВЕРЖДАЮ Проректор по учебной работе О. Г. Локтионова __2014г. УГОЛОВНОЕ ПРАВО Методические рекомендации по выполнению курсовых и выпускных квалификационных работ для специальностей 030900.62, 030900.68, 030501.65 Юриспруденция, 031001.65 Правоохранительная деятельность,...»

«Министерство образования и науки Российской Федерации Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Горно-Алтайский государственный университет Географический факультет Кафедра теории и методики физической культуры и спорта МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ Для студентов, обучающихся по специальности 050720 Физическая культура Горно-Алтайск РИО Горно-Алтайского госуниверситета 2010...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТУРИЗМА И СЕРВИСА (ФГБОУ ВПО РГУТиС) Институт туризма и гостеприимства (г.Москва) филиал Кафедра организации и технологии в туризме и гостиничной деятельности ДИПЛОМНАЯ РАБОТА на тему: Разработка рекомендаций по использованию информационных технологий в российских туроператорских компаниях по...»

«ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ для студентов ТЭФ специальность: 140101 (100500) – Тепловые электрические станции; 140103 (100600) – Технология воды и топлива на тепловых и атомных электрических станциях; 140104 (100700) – Промышленная теплоэнергетика; 140106 (101600) – Энергообеспечение предприятий. 9 семестр Раздел 1. Организационные структуры управления предприятием 1. Организационные структуры управления предприятием. 2. Организационные структуры управления ТЭС и энергоснабжающих...»

«2 Содержание: Пояснительная записка 1 4 Планируемые результаты (компетенции) обучения 2 6 Тематический план дисциплины 3 8 Содержание рабочей учебной программы дисциплины 4 11 Основное содержание дисциплины 5 15 Контрольные работы 6 27 Самостоятельная работа 7 38 Грамматический материал для самостоятельного 8 39 изучения Лексический материал 9 Контрольные задания 10 Литература Пояснительная записка Настоящее пособие включает рабочую программу, методические указания и контрольные задания для...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

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