alfutova(алгебра и теория чисел). Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике
 Скачать 2 Mb.
|
|
имея две такие веревки, отмерить промежуток времени в 15 минут? б) Сколько промежутков времени (считая нулевой) можно отмерить, имея три такие веревки. а) У одного человека был подвал, освещавшийся тремя электрическими лампочками. Выключатели этих лампочек находились вне подвала, так что включив любой из выключателей, хозяин должен был спуститься в подвал, чтобы увидеть, какая именно лампочка зажглась. Однажды он придумал способ, как определить для каждого выключателя, какую именно лампочку он включает, сходив в подвал ровно один раз. Какой это способ? б) Сколько лампочек и выключателей можно идентифицировать друг с другом, если разрешается 2 раза спуститься в подвал. С числом разрешается производить две операции увеличить в два раза и увеличить на 1». За какое наименьшее число операций можно из числа 0 получить а) число б) число n? (См. также. Бинарный метод возведения в степень. Предположим, что необходимо возвести число x в степень n. Если, например, n = 16, 3. Двоичная и троичная системы счисления 77 то это можно сделать выполнив 15 умножений x 16 = x · x · . . . · x, а можно обойтись лишь четырьмя x · x = x 2 , x 2 = x 1 · x 1 = x 4 , x 3 = x 2 · x 2 = x 8 , x 4 = x 3 · x 3 = Пусть n = 2 e 1 + 2 e 2 + . . . + 2 e r (e 1 > e 2 > . . . > e r > Придумайте алгоритм, который позволял бы вычислять x при помощи b(n) = e 1 + ν(n) − 1 умножений, где ν(n) = r — число единиц в двоичном представлении числа n. (См. также. Пусть l(n) — наименьшее число умножений, необходимое для нахождения x n . На примере чисел n = 15 и n = 63 покажите, что бинарный метод возведения в степень не всегда оптимален, то есть для некоторых n выполняется неравенство l(n) < b(n). 5.66. Коля Васин задумал число от 1 до 31 включительно и выбрал изданных карточек 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31 4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 те, на которых это число присутствует. Как, зная эти карточки, угадать задуманное число Какими должны быть карточки, чтобы по ним можно было угадывать числа от 1 до 63? 5.67. Карточный фокуса) Берется колода из 27 карт (без одной масти. Ваш друг загадывает одну из карт. После чего вы раскладываете все карты в три равные кучки, кладя каждый раз по одной карте (в первую кучку, затем во вторую, затем в третью, потом снова в первую и т. д. Ваш друг указывает на ту кучку, в которой лежит его карта. Далее вы складываете все три кучки вместе, вставляя при этом указанную кучку между двумя другими. Эта процедура повторяется еще два раза. На каком месте в колоде окажется загаданная карта, после того, как вы сложите вместе три кучки в третий раз 78 5. Числа, дроби, системы счисления б) На каком месте окажется загаданная карта, если с самого начала было 3n (n < 9) карт. Коля Васин задумал число 1, 2 или 3. Вы задаете ему только один вопрос, на который он может ответить да, нет или не знаю». Сможете ли вы угадать число, задав всего лишь один вопрос. Коля Васин задумал число от 1 до 200. За какое наименьшее число вопросов вы сможете его отгадать, если он отвечает на каждый вопроса) да или «нет»; б) да, нет или не знаю. Как и раньше загадывается число от 1 до 200, а загадавший отвечает на вопросы да или нет. При этом ровно один раз (за все ответы) он имеет право соврать. Сколько теперь понадобится вопросов, чтобы отгадать задуманное число. Докажите, что каждое целое число A представимо в виде = a 0 + 2a 1 + 2 2 a 2 + . . . + 2 n где каждое из чисел a k = 0 , 1 или −1 и a k a k+1 = для всех 0 6 k 6 причем такое представление единственно. Множество Кантора. Отрезок числовой оси от 0 до покрашен в зеленый цвет. Затем его средняя часть — интервал (1/3; перекрашивается в красный цвет, потом средняя часть каждого из оставшихся зелеными отрезков тоже перекрашивается в красный цвет, с оставшимися зелеными отрезками проделывается та же операция итак до бесконечности. Точки, оставшиеся зелеными, образуют множество Кантора. а) Найдите сумму длин красных интервалов. б) Докажите, что число 1/4 останется окрашенным в зеленый цвет. в) Из суммы 3 + 2 9 + 2 27 + 2 81 + . . произвольным образом вычеркнуты слагаемые. Докажите, что сумма оставшихся слагаемых — зеленое число. г) Докажите, что всякое число x ∈ [0, 2] представимо в виде x = α + β , где α и β — элементы множества Кантора. Последовательность Морса. Бесконечная последовательность из нулей и единиц . . . 3. Двоичная и троичная системы счисления 79 построена последующему правилу. Сначала написан нуль. Затем делается бесконечное количество шагов. На каждом шаге к уже написанному куску последовательности приписывается новый кусок той же длины, получаемый из него заменой всех нулей единицами, а единиц — нулями. а) Какая цифра стоит на 2001 месте? б) Будет ли эта последовательность, начиная с некоторого места, периодической? в) Докажите, что данная последовательность переходит в себя при замене каждого нуля на комбинацию 01, а каждой единицы — на комбинацию г) Докажите, что ни одно конечно слово из нулей и единиц не встречается в последовательности Морса три раза подряд. д) Как, зная представление числа n в двоичной системе счисления, найти й элемент данной последовательности (См. также. Ханойская башня и двоичная система счисления. Рассмотрим два процесса, каждый из которых состоит из 2 8 − 1 шагов. Первый — это процесс решения головоломки Ханойская башня (см) при помощи оптимального алгоритма. Второй — это процесс прибавления единицы, который начинается си заканчивается числом 8 − 1 . Опишите связь между этими двумя процессами. Задача Иосифа Флавия. n человек выстраиваются по кругу и нумеруются числами от 1 до n. Затем из них исключается каждый второй до тех пор, пока не останется только один человек. Например, если n = 10, то порядок исключения таков 2, 4, 6, 8, 10, 3, 7, 1, 9, так что остается номер 5. Для данного n будем обозначать через J(n) номер последнего оставшегося человека. Докажите, что а) J(2n) = 2J(n) − б) J(2n + 1) = 2J(n) + в) если n = (1b m−1 b m−2 . . . b 1 b 0 ) 2 , то J(n) = (b m−1 b m−2 . . . b 1 b 0 1) 2 5.76. Ним-сумма. Будем говорить, что число n является ним-сум- мой чисел m и k (m ⊕ k = n), если оно получается из чисел m и k после следующих преобразований) m и k записываются в двоичной системе счисления m = (m s . . . m 1 m 0 ) 2 , k = (k s . . . меньшее число дополняется спереди нулями) Полученные наборы цифр как векторы складываются покомпо- нентно по модулю 2: (m s , . . . , m 1 , m 0 ) + (k s , . . . , k 1 , k 0 ) ≡ (n s , . . . , n 1 , n 0 ) ( mod 2). 80 5. Числа, дроби, системы счисления) Набор цифр (n s , . . . , n 1 , переводится в число n: (n s . . . n 1 n 0 ) 2 = Например, 4 ⊕ 9 = 3, так как, 9=(111) 2 , (1, 0, 0) + (1, 1, 1) ≡(0, 1, 1) ( mod 2), (Докажите, что ним-сумма удовлетворяет следующим свойствам: а) m ⊕ m = 0; б) m ⊕ k = k ⊕ m; в) (m ⊕ t) ⊕ k = m ⊕ (t ⊕ г) если n 6= 0 и m 1 ⊕ m 2 ⊕ . . . ⊕ m l = то найдется такой номер j (1 6 j 6 l), для которого m j ⊕ n < m j 5.77. Игра «Ним». Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень. Для анализа игры каждому набору кучек камней m 1 , m 2 , . . . , m поставим в соответствие его ним сумму (а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, тов результате получается позиция с ним-суммой n 6= б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = в) Опишите выигрышную стратегию в игру «Ним». г) Какой следует сделать ход, если перед вами три кучки 3, 4 и камней. Марсианские амебы II. При помощи ним-сумм можно исследовать самые разные игры и процессы. Например, можно получить еще одно решение задачи 4.20 Постройте на множестве марсианских амеб, B, C} функцию f, для которой выполнялись бы равенства f(A) ⊕ f(B) = f(C), f(A) ⊕ f(C) = f(B), f(B) ⊕ f(C) = Какие рассуждения остается провести, чтобы решить задачу про амеб. Игра Йога II. Проанализируйте при помощи ним-сумм игру Йога из задачи 5.80. Игра Шоколадка. Имеется шоколадка, состоящая из 8 = 48 долек. Одна из долек отмечена 3. Двоичная и троичная системы счисления 81 Двое игроков по очереди разламывают ее по какой-нибудь прямой, делящей шоколадку на дольки, и съедают ту половину, которая не содержит отмеченной дольки. Проигрывает тот, кто не может сделать хода, то есть ему остается лишь одна отмеченная долька. а) Опишите выигрышную стратегию в этой игре. Кто из игроков выиграет, если отмеченная долька располагается так, как показано на рисунке? б) При каких размерах шоколадки начинающий игрок выигрывает при любом расположении отмеченной дольки? в) При каких размерах шоколадки начинающий игрок проигрывает при любом расположении отмеченной дольки. Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять из одной кучки от 1 до 5 камней. Определите выигрышную стратегию в этой игре, если тот, кто взял последний камень а) выигрывает; б) проигрывает. (См. также. Пешечное противостояние. На доске 3 × n расставлены n черных и n белых пешек так, как показано на рисунке: Пешки ходят и бьют по шахматным правилам, к которым добавляется одно бить обязательно. Тот, кто не может сделать хода) выигрывает б) проигрывает. Какой из игроков выигрывает в этой игре в зависимости от значения n? 5.83. 4 монеты. Из четырех монет одна фальшивая (она отличается повесу от настоящей, ноне известно, в какую сторону. Требуется за два взвешивания на двухчашечных весах без гирь найти фальшивую монету. 12 монет. Из двенадцати монет одиннадцать настоящих, а одна фальшивая (она отличается повесу от настоящей, ноне известно, в какую сторону. Требуется затри взвешивания на двухчашечных весах без гирь найти фальшивую монету и выяснить, легче она или тяжелее настоящей 82 5. Числа, дроби, системы счисления. 13 монет. Предположим теперь, что имеется 13 монет, из которых одна — фальшивая. Как затри взвешивания на двухчашечных весах без гирь найти фальшивую монету, если не требуется выяснять, легче она или тяжелее настоящей Глава Многочлены. Квадратный трехчлен Теорема Виета для квадратного уравнения. Пусть x 1 , корни уравнения x 2 + px + q = 0 . Тогда справедливы равенства x 1 + x 2 = −p, x 1 x 2 = q. 6.1. Пусть x 1 , x 2 — корни уравнения x 2 + px + q = 0 . Выразите через и q следующие величины а) 1 x 1 + 1 x 2 ; б) 1 x 2 1 + 1 x 2 в) x 3 1 + x 3 г+ p) 2 + 1 (x 2 + p) 2 6.2. Для многочленов f(x) = x 2 + ax + b и g(y) = y 2 + py + q с корнями x 1 , и y 1 , соответственно, выразите через a, b, p, q их результант, который определяется равенством, g) = (x 1 − y 1 )(x 1 − y 2 )(x 2 − y 1 )(x 2 − Вычисление результанта позволяет проверить многочлены и g(y) на наличие у них общих корней. Уравнение x 2 + px + q = имеет корни и x 2 . Напишите уравнение, корнями которого будут числа y 1 , y 2 равные: а) x 3 1 , x 3 б 1 , 1 x 2 в) x 1 + 1 x 2 , г 6.4. Пусть x 1 , x 2 — корни квадратного уравнения ax 2 + bx + c = и x n 1 + x n 2 (n > 0). Докажите формулу aS m + bS m−1 + cS m−2 = 0 (m > 2). 6.5. При каких значениях параметра a сумма квадратов корней уравнения x 2 + 2ax + 2a 2 + 4a + 3 = является наибольшей Чему равна эта сумма. Какими должны быть p и q, чтобы выполнялось равенство+ Bx 2 + C = A(x 2 + px + q)(x 2 − px + q)? 84 6. Многочлены. При каких значениях параметра a один из корней уравнения x 2 − 15 4 x + a 3 = является квадратом другого. Пусть f(x) = x 2 +px+q . При каких p и q выполняются равенства f(p) = f(q) = 0 ? 6.9. При каких p и q уравнению x 2 + px + q = удовлетворяют два различных числа 2p и p + q? 6.10. При каких a уравнение а) ax 2 + (a + 1)x − 2 = б) (1 − a)x 2 + (a + 1)x − 2 = имеет два различных корня. Нарисуйте множество всех таких точек координатной плоскости, из которых к параболе y = можно провести две перпендикулярные друг другу касательные. Рассмотрим графики функций y = x 2 + px + q , которые пересекают оси координат в трех различных точках. Докажите, что все окружности, описанные около треугольников с вершинами в этих точках, имеют общую точку. Известно, что уравнение x 2 + 5bx + c = имеет корни и x 2 , x 1 6= x 2 , а некоторое число является корнем уравнения y 2 +2x 1 y+2x 2 = и корнем уравнения z 2 + 2x 2 z + 2x 1 = 0 . Найти b. 6.14. Известно, что многочлены ax 2 + bx + c и bx 2 + cx + a (a 6= имеют общий корень. Найдите его. При каких a уравнения x 2 + ax + 1 = и x 2 + x + a = имеют хотя бы один общий корень. Пусть α — корень уравнения x 2 + px + q = 0 , а β — уравнения x 2 − px − q = 0 . Докажите, что между α и β лежит корень уравнения x 2 − 2px − 2q = 0 6.17. Укажите все точки плоскости (x; y), через которые не проходит ни одна из кривых семейства y = p 2 + (4 − 2p)x − x 2 6.18. Укажите все точки плоскости (x; y), через которые не проходит хотя бы одна кривая семейства y = p 2 + (2p − 1)x + 2x 2 6.19. Изобразите ту часть плоскости (x; y), которая накрывается всевозможными кругами вида − a) 2 + (y − a) 2 6 2 + a 2 1. Квадратный трехчлен 6.20. Докажите, что корни уравнения а) (x − a)(x − b) + (x − b)(x − c) + (x − a)(x − c) = б) c(x − a)(x − b) + a(x − b)(x − c) + b(x − a)(x − c) = 0 — всегда вещественные. Определение. Каждому квадратному трехчлену x 2 + px + q будем ставить в соответствие на координатной плоскости Opq точку с координатами (p; q). Эту плоскость назовем фазовой. Прямые вида a 2 + ap + q = будем называть корневыми, а параболу p 2 − 4q = 0 — дискриминантной. 6.21. Каким точкам фазовой плоскости соответствуют квадратные трехчлены, не имеющие корней. Для каждого действительного a построим на плоскости Opq корневую прямую a 2 +ap+q = 0 . Докажите, что полученное множество прямых совпадает с множеством всех касательных к дискриминантной параболе p 2 − 4q = 0 . (См. также. Обозначим корни уравнения x 2 + px + q = через x 1 , x 2 . Нарисуйте на фазовой плоскости Opq множества точек M(p; q), которые задаются условиями: а) x 1 = 0 , x 2 = в) x 1 = б) x 1 6 0, x 2 > г) −1 6 x 1 6 0, 1 6 x 2 6 2. 6.24. Найдите все значения параметра a, для каждого из которых уравнение 4x 2 − 2x + a = имеет два корня, причем x 1 < 1 , x 2 > 1 6.25. Найдите все такие q, что при любом p уравнение x 2 +px+q = имеет два действительных корня. Фазовая плоскость Opq разбивается параболой p 2 − 4q = и прямыми p + q + 1 = 0, −2p + q + 4 = 0 на несколько областей. Для точек каждой области укажите, сколько корней имеет соответствующий им многочлен x 2 + px + q = на интервале (−2; 1). 6.27. На фазовой плоскости через точку (p; q) проведены касательные к дискриминантной параболе p 2 − 4q = 0 . Найдите координаты точек касания. При каких значениях параметра a один из корней уравнения+ a + 1)x 2 + (2a − 3)x + (a − 5) = больше 1, а другой — меньше 1? 6.29. Известно, что модули корней уравнений x 2 + ax + b = и x 2 + cx + d = меньше 1. Докажите, что модули корней уравнения x 2 + a + c 2 x + b + d 2 = 0 86 6. Многочлены также меньше 1. 6.30. В квадратном уравнении x 2 + px + q = коэффициенты p и q независимо пробегают все значения от −1 до 1. Найдите множество значений, которые могут при этом принимать действительные корни этого уравнения. При каких значениях параметра a оба корня уравнения − a)x 2 − 3ax + 2a = больше 2 ? 6.32. При каких значениях параметра a оба корня уравнения + a)x 2 − 3ax + 4a = больше 1? 6.33. При каких значениях параметра a уравнение (a − 1)x 2 − − 2(a + 1)x + 2(a + 1) = имеет только одно неотрицательное решение. При каком значении параметра m сумма квадратов корней уравнения x 2 − (m + 1)x + m − 1 = является наименьшей. Найдите все значения параметра r, при которых уравнение − 4)x 2 − 2(r − 3)x + r = имеет два корня, причем каждый из которых больше −1. 6.36. Найдите все значения x, удовлетворяющие неравенству − a)x 3 + (1 − 2a)x 2 − 6x + 5 + 4a − a 2 < хотя бы при одном значении a ∈ [−1; 2]. 2. Алгоритм Евклида для многочленов и теорема Безу 6.37. Деление многочленов с остатком. Пусть P(x) и Q(x) многочлены, причем Q(x) неравен нулю тождественно. Докажите, что существуют многочлены T (x) и R(x) такие, что) = Q(x)T (x) + и deg R(x) < deg Q(x); и покажите, что при этом T (x) и R(x) определяются однозначно. Определение. Если многочлен P(x) поделен нас остатком) = Q(x)T (x) + то T (x) называется неполным частным, а R(x) — остатком. Если многочлен) тождественно равен нулю, тов этом случае T (x) — полное частное, и Q(x) называется делителем P(x) (Q(x) | P(x)). 2. Алгоритм Евклида для многочленов и теорема Безу 87 6.38. Теорема Безу. Докажите, что остаток отделения многочлена P(x) на x − c равен P(c). 6.39. Докажите, что многочлен степени n имеет не более чем n корней. Можно ли из какой-то точки плоскости провести к графику многочлена й степени больше, чем n касательных. Пусть x 1 , x 2 , . . . , x n — корни уравнения a n x n +. . .+a 1 x+a 0 = Какие корни будут у уравнений а) a 0 x n + . . . + a n−1 x + a n = б) a n x 2n + . . . + a 1 x 2 + a 0 = 0 ? 6.42. Пусть многочлен) = x n + a n−1 x n−1 + . . . + a 1 x + имеет корни x 1 , x 2 , . . . , x n , то есть) = (x − x 1 )(x − x 2 ) . . . (x − x Рассмотрим многочлен Q(x) = P(x) P(−x). Докажите, что а) многочлен Q(x) имеет степень 2n и содержит только четные степени переменной б) функция является многочленом с корнями x 2 1 , x 2 2 , . . . , См. также. Разделите многочлены с остатком: а) x 4 − 4x 3 + 6x 2 − 3x + наб+ на x 2 + 2x + в) x 4 + на x 5 + 1 6.44. Найдите остаток отделения многочлена P(x) = x 5 |