WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 21 | 22 || 24 | 25 |   ...   | 65 |

16.4. а) Конечно или бесконечно множество пар натуральных чисел a, b, обладающих следующим свойством: простые делители чисел a и b одинаковые и простые делители чисел a + 1 и b + 1 тоже одинаковые (и при этом a = b) б) Конечно или бесконечно множество пар натуральных чисел a, b, обладающих следующим свойством: простые делители чисел a и b + одинаковые и простые делители чисел a + 1 и b тоже одинаковые 16.5. Укажите попарно различные натуральные числа p, q, r, p1, q1, 2 2 4 r1, для которых p2 + q2 + r2 = p2 + q1 + r1 и p4 + q4 + r4 = p4 + q1 + r1 (Рамануджан).

Глава 16. Примеры и конструкции 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 принимает различные значения 192 Глава 16. Примеры и конструкции 16.5. Разные примеры и конструкции 16.12. Можно ли разбить на пары 2n человек 2n - 1 способами так, чтобы каждый человек был в паре с каждым другим ровно при одном разбиении 16.13. а) Имеется кусок цепи из 60 звеньев, каждое из которых весит 1 г. Какое наименьшее число звеньев надо расковать, чтобы из образовавшихся частей можно было составить все веса в 1 г, 2 г, 3 г,..., 60 г (раскованное звено весит тоже 1 г) б) Тот же вопрос для цепи из 150 звеньев.

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

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. Примеры и конструкции Решения 16.1. О т в е т: да, можно. Пусть p1,..., p10 различные простые числа, N = p1... p10. Тогда числа N1 = p1N,..., N10 = p10N обладают требуемыми свойствами. Действительно, число Ni делится на p2, а число Nj, где j = i, i делится только на pi, а на p2 оно уже не делится. С другой стороны, Ni i делится на N2, а N2 делится на Nj.

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

б) Положим a1 = a2!... am!-1. Тогда a1!a2!... am! = n!, где n = a2!... am!.

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 - 2 и b = 2n(2n - 2).

Тогда a + 1 = 2n - 1 и b + 1 = 22n - 2 · 2n + 1 = (2n - 1)2.

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

У чисел a + 1 = 2(2k-1 + 1) и b = 2k+1(2k-1 + 1) тоже одинаковые простые делители.

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

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

16.7. О т в е т: существует. Положим a1 = 2, a2 = 223, a3 = 22325,..., an = 2232... p2 pn, где pn n-е простое число. Число ak + ak+l +... + n-+ak+r делится на pk и не делится на p2, поэтому оно не может быть степенью k натурального числа.

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

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

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

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

16.10. Да, существует. Пусть, например, f(x, y) = x2 + (xy - 1)2. Если f(x, y) = 0, то x = 0 и xy - 1 = 0, чего не может быть. С другой стороны, для любого > 0 можно положить x = и xy - 1 =, т.е. 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). Тогда q3m(m2 - 2n2) = n3p(p2 - 2q2). (1) Числа p и q взаимно простые, поэтому числа p2 - 2q2 и 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. Примеры и конструкции составляют люди, стоящие в концах хорд, перпендикулярных проведённому диаметру.

16.13. а) О т в е т: 3 звена. Выясним, при каком наибольшем n достаточно расковать k звеньев n-звенной цепи, чтобы из образовавшихся частей можно было составить все веса от 1 до 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.

Итак, если 2kk 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, а к другой число an-1. Затем будем последовательно относить числа an-2, an-3,..., a1 к той группе, в которой сумма чисел меньше (если суммы равные, то число можно относить к любой группе). Пусть k 0 разность между суммами чисел в группах, полученных после отнесения к ним ak. Покажем, что k ak. Действительно, n-1 = an - an-1 2an-1 - an-1 = = an-1. Ясно также, что если k ak, то k-1 = |k - ak-1| и -ak-1 k - ak-1 ak - ak-1 2ak-1 - ak-1 = ak-1.

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

16.16. О т в е т: да, можно. Занумеруем контакты лампы по порядку, а отверстия штепселя в противоположном порядке. Тогда контакт с номером k попадает в отверстие с номером a-k, где a фиксированное число. (Точнее говоря, речь идёт не о самих номерах, а об их остатках от деления на 7, 196 Глава 16. Примеры и конструкции но номера совпадают тогда и только тогда, когда совпадают остатки.) Нам нужно выбрать 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, и в каждом из них написано натуральное A + 2n A число. Сопоставим ему квадрат со стороной 2n+1. Если A A + 2n мы начнём с квадрата со стороной 1, в котором написано число 1, то последовательно заполним весь прямой угол. Ясно, что при этом в каждом квадрате со стороной 2n в каждом ряду квадратов со стороной 1, параллельном одной из сторон прямого угла, любое число от 1 до 2n встречается ровно один раз.

Глава 17.

Принцип Дирихле.

Pages:     | 1 |   ...   | 21 | 22 || 24 | 25 |   ...   | 65 |



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

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