В условиях предыдущей задачи какое число может быть записано на доске после применения 20 операций
В условиях предыдущей задачи какое число может быть записано на доске после применения 20 операций
На доске записано число 2. Разрешается записывать новые числа, применяя одну из операций:
1) можно увеличить любое из записанных чисел на 3;
2) можно любое из записанных чисел возвести в квадрат.
Можно ли в какой-то момент получить на доске число:
в) За какое наименьшее число ходов можно получить на доске число 2017?
а) (операция прибавления тройки повторяется 671 раз).
б) Если число не кратно трем, то и после применения любой из двух операций оно не будет кратно трем. Поэтому получить 2016 нельзя.
в) Посмотрим, из чего могло получиться число 2017. Поскольку оно не квадрат, то только из числа 2014, а оно только из 2011 и так далее до
Если оно было получено из 1933, то аналогично придется дойти до 1849=43 2 , что потребует 29 действий. Но получить 44 можно гораздо быстрее (см. ниже). Значит, было получено из 44. Проследим теперь его получение — 41, 38, 35, 32, 29, 26, 23, 20, 17, 14, 11, 8, 5, 2 (ни одно из этих чисел не квадрат). Итак, самый короткий способ для получения 2017 это 14 раз прибавить тройку, возвести в квадрат и еще 27 раз прибавить тройку. Итого 42 хода.
Ответ: а) да, б) нет, в) 42.
Критерии проверки:— обоснованное решение п. б;
— обоснование в п. в того, что S может принимать все целые значения (отличные от -1 и 1);
В условиях предыдущей задачи какое число может быть записано на доске после применения 20 операций
На доске написаны числа 1, 2, 3, . 19, 20. Разрешается стереть любые два числа a и b и вместо них написать число a + b – 1.
Какое число может остаться на доске после 19 таких операций?
Решение
Для любого набора из n чисел на доске рассмотрим следующую величину X: сумму всех чисел, уменьшенную на n. Нетрудно проверить, что это – инвариант. В наборе из условия X = (1 + 2 + . + 20) – 20 = 190. После 19 операций, когда на доске останется одно число p, X = p – 1. Значит, p = 191.
1. На доске написаны числа 1,2,3 . 20,21. Можно стереть любые два числа а и B и записать число а+b+1. Какое число получится после 20 таких действий?
2. Правую верхнюю клетку белого квадрата 5*5 покрасили в черный цвет. За один ход можно выбрать любую строку или любой столбец и перекрасить все клетки на противоположный цвет (белые клетки покрасить в черный, чёрные - в белый). Можно ли с помощью таких операций все клетки покрасить в черный цвет?
3. На доске написано 5 чисел. Разрешается у одному из них прибавить 1, из другого вычесть 1. Можно ли получить из 2,3,4,5,6 набор 4,2,6,1,6?
В условиях предыдущей задачи какое число может быть записано на доске после применения 20 операций
Задача 1:
В алфавите языка племени УЫУ всего две буквы: У и Ы, причем этот язык обладает такими свойствами: если из слова выкинуть стоящие рядом буквы УЫ, то смысл слова не изменится. Точно так же смысл слова не изменится при добавлении в любое место слова буквосочетания ЫУ или УУЫЫ. Можно ли утверждать, что слова УЫЫ и ЫУУ имеют одинаковый смысл?
Решение:
Обратите внимание, что при любой разрешенной нам операции добавления или выкидывания куска слова количества букв У и Ы в этом куске равны. Это означает, что разность между числом букв У и букв Ы в слове не изменяется. Проследите это на примере
Ы → ЫЫУ → ЫУУЫЫЫУ → ЫУЫЫУ
Во всех этих словах букв Ы на одну больше, чем букв У. Вернемся к решению. В слове УЫЫ разность равна ( – 1), а в слове ЫУУ равна 1. Значит, из слова УЫЫ нельзя разрешенными операциями получить слово ЫУУ, и следовательно, нельзя утверждать, что эти слова обязательно имеют одинаковый смысл.
Задача 2:
Круг разделен на 6 секторов, в каждом из которых стоит фишка. Разрешается за один ход сдвинуть любые две фишки в соседние с ними сектора. Можно ли с помощью таких операций собрать все фишки в одном секторе?
Решение:
Занумеруем сектора по кругу числами от 1 до 6 и для любой расстановки фишек рассмотрим следующую величину S – сумму номеров секторов, в которых стоят данные нам 6 фишек (с учетом кратности).
Очевидно, что при сдвиге фишки в соседний сектор соответствующее ей слагаемое в сумме S меняет четность. Значит, если сдвигаются одновременно две фишки, то четность величины S не меняется – она инвариантна. Для начальной расстановки S = 21. Если же все фишки находятся в одном секторе с номером A, то S = 6A – это четное число (а 21 – число нечетное). Следовательно, из исходной расстановки нельзя получить расстановку, в которой все 6 фишек находятся в одном секторе.
Задача 3:
На доске написаны числа 1, 2, 3, …, 19, 20. Разрешается стереть любые два числа a и b и вместо них написать число a + b – 1. Какое число может остаться на доске после 19 таких операций?
Решение:
Для любого набора из n чисел на доске рассмотрим следующую величину X: сумму всех чисел, уменьшенную на n. Допустим, что с набором произведено описанное в условии преобразование. Как же изменится эта величина? Если сумма всех чисел набора, кроме a и b, равна S, то до преобразования величина X равнялась S + a + b – n, а после преобразования X = S + (a + b – 1) – (n – 1) = S + a + b – n. Итак, значение величины X не изменилось, она – инвариант. Исходно (для набора из условия задачи) X = (1 + 2 + … + 19 + 20) – 20 = 190. Значит, и после 19 операций, когда на доске останется одно число p, X также будет равно 190. Но по своему определению, в этот момент X будет равно p – 1. Значит, p = 191. Следовательно, число, оставшееся на доске обязательно будет равно 191.
Задача 4:
На доске выписаны числа 1, 2, …, 20. Разрешается стереть любые два числа a и b и заменить их на число ab + a + b. Какое число может остаться на доске после 19 таких операций?
Подсказка: В качестве инварианта рассмотрите следующую величину: произведение всех чисел на доске, предварительно увеличенных на 1.
Задача 5:
На шести елках сидят шесть чижей, на каждой елке – по чижу. Елки растут в ряд с интервалами в 10 метров. Если какой-то чиж перелетает с одной елки на другую, то какой-то другой чиж обязательно перелетает на столько же метров, но в обратном направлении. Могут ли все чижи собраться на одной елке? А если чижей и елок – семь?
Решение:
В качестве инварианта рассмотрите следующую величину: пусть каждый чиж получает номер, равный номеру елки, на которой он сидит (считая слева). Тогда сумма номеров чижей S – инвариант.
Задача 6:
В таблице 8 × 8 одна из клеток закрашена черным цветом, все остальные – белым. Докажите, что с помощью перекрашивания строк и столбцов нельзя добиться того, чтобы все клетки стали белыми. Под перекрашиванием строки или столбца понимается изменение цвета всех клеток в строке или столбце.
Задача 7:
В таблице 3 × 3 одна из угловых клеток закрашена черным цветом, все остальные – белым. Докажите, что с помощью перекрашивания строк и столбцов нельзя добиться того, чтобы все клетки стали белыми. Под перекрашиванием строки или столбца понимается изменение цвета всех клеток в строке или столбце.
Решение:
Докажите, что четность числа черных клеток среди четырех угловых не меняется при перекрашиваниях.
Задача 8:
В таблице 8 × 8 все четыре угловые клетки закрашены черным цветом, все остальные – белым. Докажите, что с помощью перекрашивания строк и столбцов нельзя добиться того, чтобы все клетки стали белыми. Под перекрашиванием строки или столбца понимается изменение цвета всех клеток в строке или столбце.
Решение:
Докажите, что четность числа черных клеток в квадрате из клеток a1, a2, b1, b2 не меняется при перекрашиваниях.
Задача 9:
На доске написаны числа 1, 2, 3, …, 1989. Разрешается стереть любые два числа и написать вместо них разность этих чисел. Можно ли добиться того, чтобы все числа на доске были нулями?
Решение:
Проверьте, что четность суммы чисел на доске неизменна.
Задача 10:
В стране Серобуромалин живет 13 серых, 15 бурых и 17 малиновых хамелеонов. Когда встречаются два хамелеона разного цвета, они одновременно приобретают окраску третьего цвета (например, серый и бурый становятся малиновыми). Может ли через некоторое время оказаться, что все хамелеоны имеют один цвет?
Решение:
Задача 11:
В вершинах правильного 12-угольника расставлены числа + 1 и – 1 так, что во всех вершинах, кроме одной, стоят + 1. Разрешается изменять знак в любых k подряд идущих вершинах. Можно ли такими операциями добиться того, чтобы единственное число – 1 сдвинулось в соседнюю с исходной вершину, если а) k = 3; б) k = 4; в) k = 6?
Решение:
Ответ во всех пунктах отрицателен. Доказательство проходит по единой схеме: отметим некоторое множество вершин, обладающее тем свойством, что любой набор из k вершин подряд содержит четное число отмеченных вершин.
В качестве инварианта рассмотрим произведение всех чисел в отмеченных вершинах. В начале оно равно – 1, а в случае, когда число – 1 сместилось в соседнюю слева (неотмеченную) вершину, равно 1. Инвариантность же введенной величины следует из описанного выше свойства множества отмеченных вершин.
Разработка занятия на тему "Олимпиадная математика. Инварианты."
В некоторых задачах по математике дается набор преобразований исходного объекта и спрашивается: можно ли, используя эти преобразования, получить из одного состояния объекта другое? Перебором вариантов часто легко убедиться в правильности ответа “нельзя”, однако обосновать этот ответ бывает трудно. Методом, позволяющим во многих случаях решать доказательную часть таких задач, является метод инвариант.
Инвариантом называется нечто, не меняющееся в преобразованиях, например, число, набор чисел, четность какого – либо числа и другое. Если значение инварианта в двух состояниях объекта различно, то одно из них нельзя получить из другого. Придумать инвариант должен ученик, самостоятельно решающий задачу; обычно это вызывает у него затруднения. В качестве инварианта чаще всего рассматриваются четность (нечетность) чисел и остаток от деления. Причем применение четности – одна из наиболее встречающихся идей при решении олимпиадных задач.
Вспомним определения четного и нечетного числа. Особое внимание надо уделить абстрактному понятию четности, объяснить, что такое “разная четность”. Например, число х + 2 имеет ту же четность, что и число х (или оба четные, или оба нечетные), а при прибавлении единицы четность меняется. Применение идеи четности и нечетности основано на двух важных утверждениях (леммах):
Лемма 1. Четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых.
Пример1. Число 1 +2 + 3 + … + 10 – нечетное, так как в сумме 5 нечетных слагаемых.
Пример 2. Число 5 + 7 + 9 + 11 +13 + 15 – четное, так как в сумме 6 нечетных слагаемых.
Лемма 2. Знак произведения нескольких (отличных от 0) чисел определяется четностью количества отрицательных сомножителей.
Пример 3 . Число (-1) *(-2) *(-3) *(-4) положительно, так как в произведении четное число отрицательных сомножителей.
Пример 4. Число (-1) *2 * (-3) * (-4) отрицательно, так как в произведении нечетное число отрицательных сомножителей.
Задача 1 . На листе бумаги написано число 11. Шестнадцать учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу – как хочет. Может ли в результате получиться число 0?
Нужно предложить выполнить эту операцию учащимся (результат каждого хода записывается на доске), заметить закономерность: после каждого хода характер четности меняется: после первого ученика число становится четным, после второго нечетным; после третьего - четным; после четвертого – нечетным. Тогда после шестнадцатого число будет нечетным. Поэтому нуль в конце получиться не может.
Задача 2. На доске написано 15 чисел: 8 нулей и 7 единиц. Вам предлагается 14 раз подряд выполнить такую операцию: зачеркиваем любые два числа, и если они одинаковые, то дописываем к оставшимся числам нуль, а если разные, то единицу. Какое число останется на доске?
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
1)Если вычеркиваем два нуля, то дописываем нуль, тогда «0»-7,
«1»-7.Осталось 14 чисел. Сумма -нечетное.
2)Если вычеркиваем две единицы, то дописываем нуль, тогда «0»-9, «1»-5. Сумма -нечетное.
3)Если нуль и единицу, то дописываем единицу, тогда «0»-7,
После выполнения данной операции на доске получается на одно число меньше.
---сумма оставшихся чисел все время число нечетное.
Значит, после 14 раз указанной операции на доске останется одно и нечетное число, а это-1!
Задача 3. В таблице, где имеются 15 чисел (-1), можно производить следующую операцию: одновременно изменить знак двух (не более, не меньше) чисел в таблице. Можно ли, применяя эту операцию конечное число раз, получить таблицу, состоящую из (+ 1)?
Решение. Ответ: нельзя. Так как число чисел в таблице нечетно, а после каждой операции число чисел (+ 1) в таблице четно. На языке инвариантов это означает: инвариантом таблицы относительно введенной операции является произведение всех чисел в таблице. В начальный момент это произведение равно ( - 1), а нам нужно получить таблицу, инвариант которой равен ( + 1).
Задача 4. Квадрат 5х5 заполнен числами так, что произведение чисел в каждой строке отрицательно. Доказать, что найдется
столбец, в котором произведение чисел также отрицательно.
Найдем произведение всех чисел. Оно отрицательно.
Произведение всех чисел равно произведению чисел в столбцах.
А так как произведение всех чисел отрицательно, то оно должно быть отрицательно в пяти, трех или хотя бы в одном столбце.
Что и требовалось доказать!
Задача 5. 16 корзин расположили по кругу. Можно ли в них разложить 55 арбузов так, чтобы количество арбузов в любых двух соседних корзинах отличалось на 1?
Т.к количество арбузов в любых двух соседних корзинах отличается на 1, то рассмотрим сумму: ч + н + ч +…+ н =55
Или н + ч + н +…+ ч = 55.
Значит, разложить 55 арбузов нельзя!
Задачи для самостоятельного решения(6-7 классы):
На вешалке висят 20 платков. 17 девочек по очереди подходят к вешалке, и каждая либо снимает, либо вешает ровно один платок. Может ли после ухода девочек на вешалке остаться 10 платков?
Решение: После подхода первой девочки количество оставшихся платков либо 19, либо 21 (нечетное количество); после подхода второй девочки – либо 18, либо 20, либо 22 (четное количество); после подхода третьей девочки – либо 17, либо 21, либо 23, либо 19 (нечетное количество). После подхода 17 девочки остается нечетное количество платков. Получается противоречие. Значит, 10 платков остаться не может.
Разменный автомат меняет одну монету на пять других. Можно ли с его помощью разменять металлический рубль на 26 монет?
Решение: Нельзя. Проследите за остатками по модулю 4.
На столе 6 стаканов, Из них 5 стоят правильно, а один перевернут вверх дном. Разрешается переворачивать одновременно 4 любых стакана. Можно ли все стаканы поставить правильно?
Решение. Нет, так как в любом случае перевернутых вверх дном стаканов будет числом нечетным.
В марсианском алфавите есть две буквы - У и Ы, причем если из любого слова выкинуть стоящие рядом буквы УЫ, то смысл слова не изменится. Точно также смысл не изменится при добавлении в любое место слова буквосочетания ЫУ или УУЫЫ. Верно ли, что слова ЫУЫУЫ и УЫУЫУ имеют одинаковый смысл?
Решение: Обратите внимание, что при любой разрешенной нам операции добавления или выкидывания куска слова количества букв У и Ы в этом куске равны. Это означает, что разность между числом букв У и букв Ы в слове не изменяется. Проследите это на примере
Ы -> ЫЫУ -> ЫУУЫЫЫУ -> ЫУЫЫУ
Во всех этих словах букв Ы на одну больше, чем букв У. Вернемся к решению. В слове ЫУЫУЫ разность равна (-1), а в слове УЫУЫУ равна 1. Значит, из слова ЫУЫУЫ нельзя разрешенными операциями получить слово УЫУЫУ, и следовательно, нельзя утверждать, что эти слова обязательно имеют одинаковый смысл.
100 фишек выставлены в ряд. Разрешено менять местами две фишки, стоящие через одну фишку. Можно ли с помощью таких операций переставить все фишки в обратном порядке?
Решение: нельзя.
Решение. Пронумеруем места, на которых стоят фишки.
В итоге же картинка должна стать такой:
Итак, если изначально фишка стояла на четном месте, то должна оказаться на нечетном месте, но это невозможно, так как разрешено менять местами две фишки, стоящие через одну фишку (если фишка лежала на четном месте, то ее можно переложить только на четное место). То есть четность места фишки является инвариантом.
Круг разделен на 6 секторов, в каждом из которых стоит фишка-рыбка. Разрешается за один ход сдвинуть любые две фишки в соседние с ними сектора. Можно ли с помощью 20 таких операций собрать все фишки в одном секторе?
Решение. Занумеруем сектора по часовой стрелке числами от 1 до 6. Для любого расположения фишек рассмотрим величину S – сумму номеров секторов, в которых лежат данные нам 6 фишек (при этом если в каком-то секторе лежит две фишки, то его номер учитывается дважды, если три фишки – трижды и т.д. Например, для ситуации, приведенной на рис. эта величина равна 1+2+3+3+5+6=20). Тогда, если мы перекладываем фишку на соседний сектор, S меняется или на 1 или на 5 (если мы перекладываем с 1 на 6 или наоборот). В любом случае четность S меняется. Следовательно, после 20 ходов четность S будет такая же, как в начале. В начале S =1+2+3+4+5+6=21. А если бы все фишки лежали в одном секторе с номером n , то S равнялось бы 6n – четное число. Значит, собрать все фишки в одном секторе за 20 ходов не получится.
На доске написаны десять чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными?
Решение: нельзя.
Проследим за суммой всех чисел. При операции из условия эта сумма увеличивается на 2. Значит, четность суммы всех чисел не меняется, она инвариант. В начале сумма всех чисел равна 1+2+…+9+10=45. То есть сумма была нечетной. А если все числа сделать равными какому-то числу n , то их сумма станет равно 10n – четное число. Следовательно, сделать все числа равными невозможно.
Замечание. Сумму чисел от 1 до 10 можно подсчитать аналогично Замечанию 1. А можно не считать, а заметить что она нечетная так как в ней участвует 5 нечетных слагаемых – 1,3,5,7,9.
На доске написаны шесть чисел: 1, 2, 3, 4, 5, 6. За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными? (задача, аналогичная предыдущей).
На квадратном поле 10*10 девять клеток 1*1 поросли бурьяном. После этого бурьян может распространиться на клетку, у которой не менее двух соседних клеток уже поросли бурьяном. Докажите, что тем не менее бурьян не сможет распространиться на все клетки.
Как изменяется периметр области, поросшей бурьяном?
Рассмотрим границу области, поросшей бурьяном (т.е. все отрезки длиной 1 между узлами, по одну сторону от которых бурьян, а по другую - нет). Вначале длина границы была не более 9*4=36, поскольку бурьян рос только в девяти клетках. Нетрудно заметить, что в процессе распространения бурьяна длина границы не может увеличиваться. Но если бы все поле 10*10 в некоторый момент оказалось поросшим бурьяном, то длина границы стала бы равной 10*4=40, что противоречит соображениям, приведенным выше .
Для построения инвариантов иногда бывают полезны вспомогательные раскраски, т.е. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета).
Задача 1. С таблицей, где имеется 15 чисел ( ? 1), а остальные равны 1, можно производить следующую операцию ? изменить знак двух (не больше, не меньше) чисел в таблице. Можно ли применяя эту операцию конечное число раз, получить таблицу, состоящую из чисел (+1)?
Решение . Ответ очевиден: нельзя. Инвариантом таблицы относительно рассматриваемой операции является произведение всех чисел в таблице. В начальный момент это произведение равно ( ? 1), а нам нужно получить таблицу, инвариант которой равен (+1).
Задача 2. Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна черная клетка?
Решение . При перекрашивании горизонтали или вертикали, содержащей k черных и 8 ? k белых клеток, получится 8 ? k черных клеток, и k белых клеток. Поэтому число черных клеток изменится на (8 ? k) ? k= 8 ? 2 k, т.е. на четное число. Т.к. четность числа черных клеток сохраняется, из исходных 32 черных клеток мы не можем получить одну черную клетку.
Задача 3. В каждой клетке доски 5х5 клеток сидит жук. В некоторый момент все жуки переползают на соседние по горизонтали или по вертикали клетки. Обязательно ли при этом останется пустая клетка?(есть в презентации)
Решение. Т.к. общее число клеток нечетно, то черных и белых клеток не может быть поровну. Пусть для определенности черных клеток больше, тогда жуков, сидящих на белых клетках, меньше, чем на черных клетках. Поэтому, хотя бы одна из черных клеток останется пустой, т.к. на черные клетки переползают жуки, сидящие на белых клетках.
Задача 4. На шести елках сидят шесть чижей, на каждой елке ? по чижу. Елки растут в ряд с интервалами 10м. Если какой-то чиж перелетает с одной елки на другую, то какой-то другой чиж обязательно перелетает на столько же метров, но в обратном направлении. Могут ли все чижи собраться на одной елке? А если чижей и ёлок ? семь?
а) Пронумеруем деревья с 1 по 6 и пусть первоначально на каждой елке сидит по чижу и каждый чиж имеет тот же номер, что и ель. Т. к. чижи перелетают на елки в разных направлениях, то сумма номеров чижей не меняется – инвариант.
Первоначально сумма была (1+6):2*6 = 21. Если предположить, что все чижи собрались на одной елке, то сумма номеров будет 6* n (т. к. все чижи получили номер елки, на которую прилетели), зн 6* n =21, n =3,5 – не натуральное. Значит предположение неверно и такого не может быть.
Задача 5 Дно прямоугольной коробки вымощено плитками 1х4 и 2х2. Плитки высыпали из коробки, и одна плитка 2х2 потерялась. Её заменили на плитку 1х4. Докажите, что теперь дно коробки вымостить не удастся.
Готовимся к олимпиаде. Инварианты
Олимпиадные задачи на инварианты можно условно разбить на два вида: те, в которых требуется доказать некий инвариант, т. е. он явно определен, и те, в которых инвариант используется при решении и сразу не очевиден. Существует также класс задач, при решении которых используются полуинварианты – значения точной верхней и нижней граней для некоторой величины. Наиболее часто они используются в задачах на доказательство экстремума какой - либо величины. Рассмотрим способ решения задач по методу “Инвариант”.
В некоторых задачах по математике дается набор преобразований исходного объекта и спрашивается: можно ли, используя эти преобразования, получить из одного состояния объекта другое? Перебором вариантов часто легко убедиться в правильности ответа “нельзя”, однако обосновать этот ответ бывает трудно. Методом, позволяющим во многих случаях решать доказательную часть таких задач, является метод инвариант. Инвариантом называется нечто, не меняющееся в преобразованиях, например, число, набор чисел, четность какого – либо числа и другое. Если значение инварианта в двух состояниях объекта различно, то одно из них нельзя получить из другого. Придумать инвариант должен ученик, самостоятельно решающий задачу; обычно это вызывает у него затруднения. В качестве инварианта чаще всего рассматриваются четность (нечетность) чисел и остаток от деления. Причем применение четности – одна из наиболее встречающихся идей при решении олимпиадных задач.
Вспомним определения четного и нечетного числа. Особое внимание надо уделить абстрактному понятию четности, объяснить, что такое “разная четность”. Например, число х =2 имеет ту же четность, что и число х (или оба четные, или оба нечетные), а при прибавлении единицы четность меняется. Применение идеи четности и нечетности основано на двух важных утверждениях (леммах):
Лемма 1. Четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых.
Пример. Число 1 +2 + 3 + … + 10 – нечетное, так как в сумме 5 нечетных слагаемых. Пример 2. Число 5 + 7 + 9 + 11 +13 + 15 – четное, так как в сумме 6 нечетных слагаемых.
Лемма 2. Знак произведения нескольких (отличных от 0) чисел определяется четностью количества отрицательных сомножителей.
Рассматриваем с учащимися несколько примеров.
Арифметика, алгебра, комбинаторика.
Пример 1. Число (-1) *(-2) *(-3) *(-4) положительно, так как в произведении четное число отрицательных сомножителей.
Пример 2. Число (-1) *2 * (-3) * (-4) отрицательно, так как в произведении нечетное число отрицательных сомножителей.
После этого разбираем подробно следующие задачи.
Задача 1. На листе бумаги написано число 11. Шестнадцать учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу – как хочет. Может ли в результате получиться число 0?
Нужно предложить выполнить эту операцию учащимся (результат каждого хода записывается на доске), заметить закономерность: после каждого хода характер четности меняется: после первого ученика число становится четным, после второго нечетным; после третьего - четным; после четвертого – нечетным. Тогда после шестнадцатого число будет нечетным. Поэтому нуль в конце получиться не может.
Задача 2. На вешалке висят 20 платков. 17 девочек по очереди подходят к вешалке и либо снимают, либо вешают платок. Может ли после ухода девочек остаться ровно 10 платков?
Решение. После подхода первой девочки количество оставшихся платков либо 19, либо 21 (нечетное количество); после подхода второй девочки – либо 18, либо 20, либо 22 (четное количество); после подхода третьей девочки – либо 17, либо 21, либо 23, либо 19 (нечетное количество). После подхода 17 девочки остается нечетное количество платков. Получается противоречие. Значит, 10 платков остаться не может.
В первой и во второй задачах инвариантом является четность суммы чисел.
Задача 3. В таблице, где имеются 15 чисел (-1), можно производить следующую операцию: одновременно изменить знак двух (не более, не меньше) чисел в таблице. Можно ли, применяя эту операцию конечное число раз, получить таблицу, состоящую из (+ 1)?
Решение. Ответ: нельзя. Так как число чисел в таблице нечетно, а после каждой операции число чисел (+ 1) в таблице четно. На языке инвариантов это означает: инвариантом таблицы относительно введенной операции является произведение всех чисел в таблице. В начальный момент это произведение равно ( - 1), а нам нужно получить таблицу, инвариант которой равен ( + 1).
Задача 4. Имеется набор чисел а, в, с. Данный набор чисел меняется на тройку чисел: а + в – с, в + с – а, а + с – в. Дан набор чисел 2000, 2002, 2003. Можно ли из него получить набор из чисел 2001, 2002, 2003?
Решение. Ответ: нельзя. Так как (а + в + с) и (а + в - с) +(в +с – а) +(а + с – в) равны, а сумма 2000+2002 +2003 и сумма 2001 + 2002 +2003 различны.
Задача 5. На столе 6 стаканов, Из них 5 стоят правильно, а один перевернут вверх дном. Разрешается переворачивать одновременно 4 любых стакана. Можно ли все стаканы поставить правильно?
Решение. Нет, так как в любом случае перевернутых вверх дном стаканов будет числом нечетным.
Задача 6. Из цифр 2, 3, 4,… 9 составили два натуральных числа. Каждая цифра использовалась один раз. Могло ли одно из этих чисел оказаться вдвое больше другого?
Решение. Ответ: нет. Пусть а и b = 2а – полученные числа, S(a) и S(b) – суммы их цифр. По признаку делимости числа N и S(N) имеют одинаковые остатки при делении на 3. Поскольку число a + b = 3a делится на 3, то сумма S = S(a) + S(b) должна делиться на 3, что неверно, так как S = 2 + 3 + 4 + … + 9 = 44.
Задача 7. На доске написаны числа 1, 2, …, 1998. За один ход разрешается стереть любое количество чисел и вместо них записать остаток от деления их суммы на 11. Через несколько ходов на доске остались два числа, одно из которых – 1000. Чему равно второе число?
Решение. Так как в конечном итоге на доске оказались записанными два числа, то хотя бы одно из них является остатком от деления некоторого числа на 11, т.е. не превосходит 10.Число 1000 не может являться остатком от деления какого-то числа на 11, поэтому искомое число не больше 10. Заметим, что в результате выполнения указанных операций остаток от деления суммы всех написанных чисел не изменится, так как для любых чисел а и в (а + в)(mod p) (a(mod p) + b(mod p))(mod p), где р – произвольное простое число. Первоначально 1 + 2 + … +1998 = 1997001 6 (mod 11) 1000 (mod p) + второе число. Так как 1000 10 (mod 11), то второе число 7.
Задача 8. В некотором государстве было 10 банков. С момента перестройки общества все захотели стать банкирами. Но по закону открыть банк можно только путем деления уже существующего банка на 4 новых. Через некоторое время министр финансов сообщил президенту, что в стране действует 2007 банков, после чего был немедленно уволен за некомпетентность. Что не понравилось президенту?
Решение. Заметим, что в результате превращения одного старого банка в четыре новых общее количество банков увеличится на 3. Таким образом, в любой момент времени число банков равно Б = 10 + 3 k и остаток от деления числа банков на 3 постоянен. (Это и есть инвариант). То есть Б . Первоначально Б ( mod 3) >, а 2007 .
Задача 9. Разместите цифры 0,1,2,3, …, 9 по кругу так, чтобы сумма всех разностей (по модулю) между соседними числами оказалась равна 25.
Решение. Пусть заданные числа каким-то образом проставлены по кругу и a, b, c, d – четыре соседних числа. Поменяем местами числа a >и c. Исследуем, как изменилась сумма рассматриваемых в задаче разностей. Для расстановки a, b, c, d она равна , а для расстановки a , c, b , d – , где – сумма разностей для оставшихся чисел. Изменение общей суммы Если b >и c имеют одинаковую четность, то будет представлять собой сумму двух четных чисел, а если они разной четности, то является суммой двух нечетных чисел, но в любом случае четно. Следовательно, мы получили инвариант – при перестановке двух соседних чисел четность суммы разностей не изменится. Любую расстановку заданных чисел по кругу можно получить, переставляя несколько раз соседние числа, тем самым мы доказали, что для любой расстановки заданных чисел сумма разностей имеет одну и ту же четность. Рассмотрев произвольную расстановку чисел (от одного до девяти), мы получим, что сумма разностей четна, и, значит, требуемая в задаче расстановка невозможно.
Задача 10. На доске написаны числа 1, 2, 3, …, 1998. За один ход разрешается стереть любые два числа и вместо них записать их разность. В результате многократного выполнения таких действий на доске окажется записанным одно число. Может ли оно быть нулем?
Решение. Не может. Так как вначале на доске 999 нечетных чисел. На каждом шаге их количество не меняется, если среди выбранных чисел не более одного нечетного числа. А если выбранные числа оба нечетны, то количество нечетных чисел уменьшается на два. Таким образом, инвариант преобразования: количество нечетных чисел нечетно. Поэтому в конце должно остаться нечетное число. А нуль – четное число.
Задача 11. Числа 0,1,2,3, …, 9 записаны по кругу. За один ход разрешается прибавить к двум соседним числам одно и то же целое число. Можно ли за несколько ходов получить десять нулей?
Решение. Нельзя. При прибавлении одинаковых целых чисел к любым двум из имеющихся не меняет четность общей суммы всех чисел. Первоначально эта сумма равно 1 + 2 + 3 + … 9 = 45, следовательно, после каждого хода общая сумма полученных чисел должна быть нечетна, а нуль – четное число.
Задача 12. В десяти сосудах содержится 1, 2, 3,…, 10 литров воды. Разрешается перелить из сосуда А в сосуд В столько воды, сколько имеется в В. Можно ли добиться, чтобы после нескольких переливаний в 5 сосудах оказалось 3 литра, а в остальных 6, 7, 8, 9, 10?
Решение. Нельзя. Предложенная операция обладает полуинвариантом: при любом переливании число нечетных сосудов (содержащих нечетное число литров воды) не увеличивается. Количество таких сосудов уменьшается при переливании из нечетного сосуда в нечетный, а в остальных случаях не изменяется. Следовательно, переход 1, 2, … 10 —> 3, 3, 3, 3, 3, 6,…,10 невозможен, поскольку увеличивает число нечетных сосудов.
При решении математических задач важную роль играет анализ задач. Успех решения задачи во многом определяется качеством анализа. Однако владение искусством анализа дается нелегко. Причина тому - творческий характер этого метода. Как научить ребят сознательному владению приемами анализа в решении математических задач? В чем состоит его суть? Смысл анализа состоит в извлечении из формулировки задачи полезных сведений. Однако объём извлеченных сведений иногда оказывается недостаточен для решения. Тогда возникает необходимость в повторном, более глубоком анализе. Почему в одних случаях достигается решение, а в других – лишь некоторые осознание проблемной ситуации? Что мешает этому осознанию?
Одна из причин состоит в отсутствии достаточных знаний у учащихся. Вторая причина связана со сложностью задачи. Сложность математической задачи зависит от многих факторов. Один из них – формулировка задачи. Для её решения может оказаться достаточным знание одной единственной теоремы или же одного-единственного её следствия. Необходимо только отыскать подходящий критерий для выявления этой теоремы или следствия. Рассмотрим пример.
Задача 13. Доказать, что уравнение 3x 2 – 4xy + 2y 2 – 21x + 12y – 3 = 0 имеет лишь конечное число целочисленных решений.
Анализ задачи. Заданное уравнение связывает определенными отношениями переменные x и y. Левая её часть представляет собой довольно громоздкий многочлен, а правая равна 0. О самих же переменных известно, что они целые числа. Это обобщенное понятие является и ключевым в нашей задаче. Если рассмотреть каждое слагаемое, легко заметить, что второе, третье, пятое из них всегда являются четными числами, а свободный член – нечетным. Перепишем уравнение в виде: 3x(x – 1) – 18x – 4xy + 2y 2 + 12y = 3.
Вспомнив свойство четности произведения двух последовательных целых чисел, установим четность первого слагаемого. Теперь мы знаем, что каждое слагаемое левой части уравнения всегда четно, следовательно, четна и их сумма. А в правой части –нечетное число. Приходим к выводу о том, что уравнение не имеет целочисленных решений. >
Задача 14. Найдите множество точек плоскости XOY, координаты которых удовлетворяют уравнению .
Решение. Левая часть уравнения представляет собой сумму расстояний OM + MC, где , . Для любых трех точек имеем полуинвариант, следующий из неравенства треугольника: . В нашем случае . Следовательно, точка должна лежать на отрезке .
В условиях предыдущей задачи какое число может быть записано на доске после применения 20 операций
На доске записаны целые числа $$$1, 2, 3, \dots n$$$ (то есть все целые числа от $$$1$$$ до $$$n$$$ по одному разу). Вы можете за одну операцию стереть с доски два любых числа $$$a$$$ и $$$b$$$ и вместо них записать новое число, равное $$$\frac$$$ округленному вверх .
Вы должны выполнить ровно $$$n - 1$$$ описанную операцию, при этом число, которое будет записано на доске в ходе последней операции, должно быть минимально возможным.
Например, если $$$n = 4$$$, то следующая последовательность действий является оптимальной:
- выбрать $$$a = 4$$$ и $$$b = 2$$$, тогда вы запишете $$$3$$$, и на доске останутся числа $$$[1, 3, 3]$$$;
- выбрать $$$a = 3$$$ и $$$b = 3$$$, тогда вы запишете $$$3$$$, и на доске останутся числа $$$[1, 3]$$$;
- выбрать $$$a = 1$$$ и $$$b = 3$$$, тогда вы запишете $$$2$$$, и на доске останется $$$[2]$$$.
Легко показать, что после $$$n - 1$$$ операции на доске будет записано всего одно число, его и нужно минимизировать.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В первой строке каждого набора задано целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество целых чисел, изначально записанных на доске.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выходные данныеВ первую строку каждого набора входных данных выведите минимальное число, которое может остаться на доске после $$$n - 1$$$ операции. В каждой из следующих $$$n - 1$$$ строк выведите по два целых числа — числа $$$a$$$ и $$$b$$$, которые должны быть стерты с доски во время очередной операции.
В условиях предыдущей задачи какое число может быть записано на доске после применения 20 операций
Чужой компьютер
Олимпиадная математика
вернуться к странице
Олимпиадная математика запись закреплена
Свои решения оставляйте в комментариях. Разбор задачи будет не далее чем через неделю.
Нравится Показать список оценивших
Сначала старые
Мы уменьшаем сумму 2 стёртых чисел (а + в) на а+в-(а-в) = а+в-а+в = 2в. Сумма чисел от 1 до 2016 чётна (2033136), значит вычитая каждый раз из этой суммы чётное число (2в) получится 0. Следовательно если на доске написаны числа от 1 до 2016 мы сможем получить 0. Если на доске написаны числа от 1 до 2017, мы не сможем получить 0 на доске, тк сумма чисел от 1 до 2017 не чётна.
Нравится Показать список оценивших
Решение 13 задания ВПР за 6 класс "На доске записано число. Олег играет в арифметическую игру. "
Сегодня пришла заявка на решение 13 задания ВПР по математике за 6 класс.
На доске записано число. Олег играет в арифметическую игру. Он может либо стереть последнюю цифру написанного числа, либо прибавить к написанному числу число 2018 и записать полученный результат, стерев предыдущее число. Может ли Олег, действуя таким образом, в конце получить число 1. Если да, то покажите как, если нет, то объясните почему.
Во-первых . Условие не совсем понятно для шестиклассника. Смущают слова "либо. либо".
Во-вторых . Не сказано, какое число написано на доске. Натуральное? Целое? Дробное? В качестве компенсации указано, что игра арифметическая . Читаю в словаре.
Значит, арифметика-наука о числах. Имеются ввиду натуральные, целые, рациональные числа.
Со всеми этими числами и действиями над ними шестиклассники уже знакомы.
Начнем с конкретного примера.
Предположим, что на доске натуральное число 137. Олег играет в этом случае так. Он стирает по одной две последние цифры, остаётся 1. Игра закончена. Что-то слишком просто.
Предположим, что на доске натуральное число 237. Олег стирает две последние цифры по очереди. Остаётся 2- число старшего разряда.
Как он может получить 1, имея 2? Олег использует второе "либо" из условия задачи несколько раз. Прибавит к 2 число 2018 несколько раз, пока в старшем разряде не увидит цифру 1.
8074+2018=10092 или короче
Итак, он получает число 1 0092. Стерев последовательно четыре последние цифры, получает 1.
Теперь от частного к общему.
1. Если число имеет в старшем разряде 1, т. е. имеет вид 1xxxxx, то, стирая по одной последней цифре, в конце можно получить число 1 сразу.
2. Пусть число имеет цифру старшего разряда не 1, а 2,3,4,5,6,7,8,9, т е. имеет вид 2xxxx, 3xxxx, 4xxxx, 5xxxx, 6xxxx, 7xxxx, 8xxxx, 9xxxx. Тогда необходимо стереть последние цифры числа и к оставшейся цифре старшего разряда прибавить 5 раз по 2018 и получить результаты соответственно 10092, 10093,10094,10095,10096,10097,10098,10099.
Теперь снова стоит стереть четыре последние цифры по очереди и получить число 1.
В условиях предыдущей задачи какое число может быть записано на доске после применения 20 операций
На доске записаны целые числа $$$1, 2, 3, \dots n$$$ (то есть все целые числа от $$$1$$$ до $$$n$$$ по одному разу). Вы можете за одну операцию стереть с доски два любых числа $$$a$$$ и $$$b$$$ и вместо них записать новое число, равное $$$\frac$$$ округленному вверх .
Вы должны выполнить ровно $$$n - 1$$$ описанную операцию, при этом число, которое будет записано на доске в ходе последней операции, должно быть минимально возможным.
Например, если $$$n = 4$$$, то следующая последовательность действий является оптимальной:
- выбрать $$$a = 4$$$ и $$$b = 2$$$, тогда вы запишете $$$3$$$, и на доске останутся числа $$$[1, 3, 3]$$$;
- выбрать $$$a = 3$$$ и $$$b = 3$$$, тогда вы запишете $$$3$$$, и на доске останутся числа $$$[1, 3]$$$;
- выбрать $$$a = 1$$$ и $$$b = 3$$$, тогда вы запишете $$$2$$$, и на доске останется $$$[2]$$$.
Легко показать, что после $$$n - 1$$$ операции на доске будет записано всего одно число, его и нужно минимизировать.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В первой строке каждого набора задано целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество целых чисел, изначально записанных на доске.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выходные данныеВ первую строку каждого набора входных данных выведите минимальное число, которое может остаться на доске после $$$n - 1$$$ операции. В каждой из следующих $$$n - 1$$$ строк выведите по два целых числа — числа $$$a$$$ и $$$b$$$, которые должны быть стерты с доски во время очередной операции.
Читайте также: