Тема №8964 Инварианты и их применение при решении задач 20
Поиск задачи:

Рассмотрим тему Инварианты и их применение при решении задач 20 из предмета Математика и все вопросы которые связанны с ней. Из представленного текста вы познакомитесь с Инварианты и их применение при решении задач 20, узнаете ключевые особенности и основные понятия.

Уважаемые посетители сайта, если вы не согласны с той информацией которая представлена на данной странице или считаете ее не правильной, не стоит попросту тратить свое время на написание негативных высказываний, вы можете помочь друг другу, для этого присылайте в комментарии свое "правильное" решение и мы его скорее всего опубликуем.

  1. Конь вышел с поля al шахматной доски и через не­сколько ходов вернулся на него. Докажите, что он сделал чёт­ное число ходов.

  2. Можно ли доску размером 5 x 5 заполнить доминошками размером 1 x 2?

  3. 2003 человека выстроились в шеренгу. Всегда ли можно их расставить по росту, если за один ход разрешается пере­ставлять только двух людей, стоящих через одного?

  4. В древней рукописи приведено описание города, распо­ложенного на 8 островах. Острова соединены между собой и с материком мостами. На материк выходят 5 мостов; на 4 ост­ровах берут начало по 4 моста, на 3 островах берут начало по 3 моста и на один остров можно пройти только по одному мосту. Может ли быть такое расположение мостов?

  5. 16 корзин расположили по кругу. Можно ли в них раз­ложить 55 арбузов так, чтобы количество арбузов в любых двух соседних корзинах отличалось на 1?

  6. Можно ли выпуклый девятиугольник разрезать на па­раллелограммы?

  7. На столе стоят 7 стаканов - все вверх дном. Разрешает­ся за один раз перевернуть любые 4 стакана. Можно ли за не­сколько раз добиться того, чтобы все стаканы стояли правиль­но, то есть вниз дном?

  8. Сумма 2002 натуральных чисел — число нечётное. Ка­ким числом: чётным или нечётным является произведение этих чисел?

  9. На доске написаны числа 1, 2, 3, ... 1997, 1998, 1999, 2000, 2001. Разрешается стереть с доски любые 2 числа и вме­сто них записать модуль их разности. В конце концов, на дос­ке останется одно число. Может ли оно равняться нулю?

  10. На доске написано в строку 2003 целых числа. Дока­зать, что из них можно стереть одно число так, что сумма ос­тавшихся чисел будет чётной. Верно ли это для 2002 чисел?

  11. В каждую клетку квадратной таблицы размером 25 x 25 вписано произвольно одно из чисел: +1 или -1. Под каждым из столбцов записывается произведение всех чисел данного столбца, а справа от каждой строки — произведение всех чи­сел данной строки. Может ли сумма всех 50 произведений быть равной нулю?

  12. На доске написано 8 плюсов и 13 минусов. Разрешает­ся стирать любые два знака и написать вместо них плюс, если они одинаковы, и минус в противном случае. Какой знак оста­нется после выполнения 20 таких операций?

  13. Учитель написал на листке бумаги число 10. 25 учени­ков передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу — как хочет. Может ли в ре­зультате получиться число 0?

  14. В некотором государстве первоначально было 10 бан­ков. С момента перестройки общества все захотели быть бан­кирами. Но, по закону, открыть банк можно только путём деления уже существующего банка на 4 новых банка. Через 2 года министр финансов сообщил президенту, что в стране действует уже 2001 банк, после чего был немедленно уволен за некомпетентность. Что не понравилось президенту?

  15. Можно ли по правилам игры в домино выложить все 28 костей в одну цепочку так, чтобы сумма на её концах была нечётной? (Дубли кладём вдоль цепи, конечной считаем вто­рую половину кости.)

  16. Написанное на доске четырехзначное число можно заменить на другое, прибавив к двум его соседним цифрам по единице, если ни одна из его цифр не равна 9, либо, вычтя из соседних двух цифр по единице, если ни одна из них не равна 0. Моно ли с помощью таких операций из числа 1234 получить число 2002?

  17. В таблице т х п расставлены числа так, что сумма чисел в любой строке или столбце равна 1. Докажите, что т = п.

  18. По кругу расставлено 7 чисел: 4 единицы и 3 нуля. Ка­ждую секунду над числами проделывают следующую опера­цию: между соседними числами ставят нуль, если они различ­ны, и единицу, если они равны; после этого старые числа сти­рают. Могут ли через некоторое время все числа стать одина­ковыми?

  19. Числа 0, 1, 2, ..., 9 записаны по кругу. За один ход раз­решается прибавить к двум соседним числам одно и то же це­лое число. Можно ли за несколько ходов получить десять ну­лей?

  20. В вершинах куба записаны числа 2, 0, 0, 3, 1, 9, 5, 7. За один ход разрешается прибавить к числам, стоящим на концах одного ребра, одно и то же целое число. Можно ли за несколь­ко ходов получить нули во всех вершинах?

  21. У Ивана-царевича есть два волшебных меча: с помо­щью первого он может отрубить у Змея Горыныча 21 голову, а с помощью второго - 4 головы, но тогда у Змея Горыныча от­растает 1999 голов. Может ли Иван отрубить Змею Горынычу все головы, если в самом начале у него было 30 голов? (При­мечание: если у Змея Горыныча осталось голов 3 или 2 или 1, то никаким мечом рубить нельзя.)

  22. На плоскости лежат три шайбы. Хоккеист бьет по од­ной из них так, чтобы она прошла между двумя другими и ос­тановилась в некоторой точке. Можно ли все шайбы вернуть на свои места после 2003 ударов?

  23. Страницы книги пронумерованы подряд с первой до последней страницы. Хулиган Вася вырвал из разных мест книги 17 листов и сложил номера всех 34 вырванных страниц. У него получилось число 2002. Правильно ли Вася сосчитал?

  24. 101 лошадь разместили в 15 конюшнях. Почему хотя бы в одной конюшне будет обязательно нечётное число лоша­дей?

  25. 100 фишек стоят в ряд. Любые две фишки, располо­женные через одну, можно менять местами. Удастся ли распо­ложить фишки в обратном порядке?

  26. На чудо-дереве садовник вырастил 45 бананов и 50 апельсинов. Каждый день он срывает 2 плода и тут же на де­реве вырастает новый. Причем, если он срывает 2 одинаковых плода, то вырастает апельсин, а если — 2 разных, то выраста­ет банан. Каким окажется последний плод на дереве?

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

  28. В классе у каждого ученика не более трех врагов. До­кажите, что класс можно разбить на 2 группы так, что у каж­дого ученика в одной с ним группе будет не более одного вра­га, (Считается, что если А — враг В, то и В — враг А).

  29. Дана некоторая тройка чисел. С любыми двумя разрешается проделывать следующее: если эти числа равны а и в, то их можно заменить на и . Можно ли с помощью таких операций получить тройку из тройки ?

Ответы и указания к решению

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

2. Нет, так общее число клеток — 25 не делится на 2

3. Не всегда. При перестановке сохраняется чётность но­мера места. Поэтому, если самый высокий человек, например, стоит вторым, то он никогда не станет первым. Здесь число 2003 роли не играет.

4. Найдём число концов у всех мостов: 5 + 4 · 4 + 3 · 3 + 1 = 31.

31 — является числом нечётным. Так как число концов у всех мостов должно быть чётным, то такого расположения мостов быть не может.

5. Если число арбузов в соседних корзинах отличается на 1, то характер чётности числа арбузов в этих корзинах будет разным. Тогда чётность числа арбузов в корзинах бу­дет чередоваться, поэтому в половине корзин будет чётное число арбузов, а в половине нечётное. Тогда общее число арбузов в 8 корзинах с чётным числом арбузов и в 8 корзи­нах с нечётным числом арбузов будет чётным. По условию же всего арбузов — 55, а это нечётное число. Значит, раз­ложить нельзя.

6. Нет, так как если выпуклый многоугольник разрезается на параллелограммы, то его стороны обязательно разбиваются на пары параллельных сторон. Так как сторон 13, то у одной из сторон пары не будет.

7. Нет, так как в любом случае число перевёрнутых вверх дном стаканов будет числом нечётным.

8. Так как сумма 2002 чисел — число нечётное, то число нечётных слагаемых — нечётно. Тогда среди 2002 чисел есть хотя бы одно чётное число. А, значит, произведение 2002 чи­сел будет чётным числом.

9. Сумма всех записанных на доске чисел будет нечётной. При стирании 2 чисел могут быть следующие 3 варианта:

а) стираются 2 чётные числа, тогда модуль разности будет четным числом, а новая сумма будет числом нечётным;

б) стираются 2 нечётные числа, тогда модуль разности бу­дет чётным числом, а новая сумма будет числом нечётным;

в) стираются 1 чётное и 1 нечётное число, тогда модуль разности будет нечётным числом, а новая сумма будет снова числом нечётным.

Таким образом, в любом случае на доске останется нечёт­ное число. Так как нуль — число чётное, то оставшееся число нулем быть не может.

10. Рассмотрим 3 случая.

а) Среди 2003 целых чисел есть чётные и нечётные числа. Если количество нечётных чисел нечётно, то стираем любое из них. Если количество нечётных чисел четно, то из 2003 це­лых чисел хотя бы одно чётное. Его и стираем.

б) Пусть все 2003 числа — нечётные. Тогда стираем любое из них.

в) Пусть все 2003 числа — чётные. В этом случае стираем любое из них.

В случае, когда чисел 2002 и все они нечётные, оставшаяся сумма не может быть чётной. Поэтому для 2002 целых чисел это неверно.

11. Перемножая все 50 произведений, мы получим 1, так как в каждое произведение любое из чисел, вписанных в клет­ки таблицы, войдёт 2 раза (один раз в произведение по стро­кам, один раз - по столбцам). Тогда в число 50 сомножителей будет входить чётное число произведений с «-1» , а поэтому сумма чётного числа произведений с «1» и чётного числа про­изведений с

«-1» не будет равна 0. (25 — число нечётное, зна­чит, одинакового числа слагаемых не будет).

12. Заменяя все плюсы нулями, а минусы — единицами, заметим, что сумма двух стираемых чисел имеет тот же харак­тер чётности, что и число, записываемое вместо них. Так как сумма всех чисел была нечётной (13), то и последнее остав­шееся число будет нечётным, то есть единицей, и, значит, на доске останется минус.

13. От прибавления или вычитания единицы меняется ха­рактер чётности числа. Поэтому, если 25 раз менять характер чётности числа 10, то в результате получится нечётное число. Следовательно, число 0 получиться не может.

14. Заметим, что в результате превращения одного старого банка в четыре новых общее число банков увеличивается на 3. Таким образом, в любой момент времени число банков будет равно 10 + ЗnПервоначально остаток от деления количества банков на 3 был равен 1, а 2001 при делении на 3 даёт остаток 0. Значит, образоваться ровно 2001 банков в стране не могло.

15. В наборе домино клеток-половинок кости с одинако­вым количеством очков 8 штук, а в цепи они стоят подряд по 2 или 4. Значит, на концах может оказаться только разорван­ная пара. Поэтому сумма очков на концах будет чётной. Зна­чит, выложить цепь так, что сумма очков на концах была не­чётной, нельзя.

16. Пусть на доске написано число . Тогда рассматриваемые операции не изменяют число М = (d +b) – (a + c), так как они увеличивают (уменьшают) на единицу одно число из первой скобки, и одно число из второй скобки. Для числа 1234 М1 = (4+2) – (1+3) = 2, а для числа 2002 М2= (2+0) – (2+0) = 0. Поэтому требуемое невозможно.

17. Сумма чисел в таблице не зависит от способа ее под­счёта. С одной стороны, это количество строк, умноженное на 1, с другой — количество столбцов, умноженное на 1. То есть, т п. Здесь инвариант — сумма чисел в таблице, а преобра­зование — нахождение суммы этих чисел.

18. Комбинация из семи единиц раньше, чем семь нулей, получиться не может, так как для появления семи единиц пре­дыдущие цифры должны быть одинаковыми — все нули или все единицы. Если же получилось семь нулей, то на предыду­щей стадии нули и единицы должны были чередоваться, что невозможно, так как их разное количество.

19. Сумма чисел, записанных по кругу, равна 45. Прибав­ляя 2 одинаковых целых числа к соседним числам, мы харак­тер чётности не меняем: сумма по-прежнему остается нечёт­ной. Так как сумма 10 нулей — нуль — число чётное, то ука­занными преобразованиями получить 10 нулей нельзя.

20. Так как сумма данных чисел: число 27 — нечётное, а при прибавлении двух одинаковых целых чисел чётность суммы не меняется, то получить все нули во всех вершинах не получится (сумма восьми нулей — число чётное).

21. Змей Горыныч теряет либо 21 голову, либо приобрета­ет 1995 голов. Оба эти числа делятся нацело на 7, а в начале поединка остаток был 2. В случае же отсутствия голов у Змея Горыныча, остаток был бы 0. Значит, отрубить все головы Змею Горынычу Иван-царевич не сможет.

22. После каждого удара меняется ориентация обхода шайб А, В и С (по ходу часовой стрелки — против хода часо­вой стрелки). Инвариантом будет сохранение ориентации по­сле чётного числа ударов. Значит, после 2003 ударов шайбы не удастся вернуть на свои места.

23. На каждом из 17 листов сумма номеров двух страниц число нечётное, так как на одной странице номер чётный, а на другой — нечётный. Тогда сумма 17 нечётных чисел будет нечётной. Так как 2002 — число чётное, то Вася ошибся при подсчёте.

24. Докажем задачу методом от противного. Пусть в каж­дой конюшне находится чётное число лошадей, тогда сумма чётных чисел — число чётное. А по условию всего лошадей 101 — число нечётное. Таким образом, получили противоре­чие. Значит, хотя бы в одной конюшне будет нечётное число лошадей.

25. Так как при перестановке фишек чётность места фиш­ки сохраняется, то первую фишку никогда не сделать послед­ней (1 — число нечётное, а 100 — число чётное)

26. Рассмотрим несколько случаев:

1) Садовник сорвал 2 апельсина, тогда вырастает 1 апель­син и на дереве будет 45 бананов и 49 апельсинов.

2) Садовник сорвал 2 банана, в этом случае вырастает 1 апельсин и на дереве будет 43 банана и 51 апельсин.

3) Если же садовник срывает 2 разных плода: апельсин и банан, то на дереве вырастает банан и всего плодов будет: 45 бананов и 49 апельсинов.

Итак, можно заметить, что ниже и в каждом из трёх случа­ев неизменным остается одно, а именно: количество бананов — нечётное число. Значит, инвариантом будет нечётность числа бананов на дереве, а поэтому последним плодом ока­жется банан.

27. Занумеруем сектора последовательно числами 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 и присвоим каждой фишке номер сектора, в котором она находится. При передвижении какой-либо фишки в соседний сектор номер фишки меняется на единицу. Поэто­му чётность суммы номеров всех фишек при любых передви­жениях двух фишек не меняется. В первоначальном положе­нии сумма всех номеров фишек была равна 1 + 2 +... + 10 = 55 (нечетное число). Тогда как в случае, если все фиш­ки удалось собрать в одном секторе, то сумма номеров была бы чётной. Значит, собрать фишки в одном секторе не удастся.

28. Разобьем произвольным образом класс на 2 группы. Если в этом случае получилось, что в каждой группе у каж­дого ученика не более одного врага, то требование задачи выполнено. В противном случае, рассмотрим того ученика, пусть это будет А, у которого в одной с ним группе не менее 2 врагов. Значит, в другой группе у А будет не более одного врага. Переведём ученика А в другую группу (где у него вра­гов не более одного). Поступая аналогично так с каждым из учеников, у которого в одной с ним группе окажется 2 или 3 врага, мы, в конце концов, придём к искомому разбиению класса.

29. Нет. Так как при каждой операции сохраняется сумма квадратов чисел.

 


Категория: Математика | Добавил: Админ (18.10.2016)
Просмотров: | Рейтинг: 0.0/0


Другие задачи:
Всего комментариев: 0
avatar