какое наименьшее число коней может побить все поля шахматной доски

Какое наименьшее число коней может побить все поля шахматной доски

Решение олимпиадных задач

Принцип узких мест

Где тонко, там и рвется.

Решать нестандартную задачу — все равно, что идти через дикий лес. Можно, конечно, вы­бирать дорогу наугад, но, тогда скорее всего бу­ дешь попадать то в непроходимую чащу, то в болото. Придется ходить туда-сюда, но даже если повезет и пройдешь куда надо, то зря потратишь много времени и сил. Гораздо легче идти, если есть хоть какой-то ориентир. Скажем, забрался на горку и увидел, что надо обязательно перей­ти реку, а брод только во-о-о-н там. Это, конеч­ но, уменьшает свободу выбора пути, но зато из­ бавляет от ненужных блужданий.

Вот и в задачах, где строят и исследуют кон­ струкции, зацепкой к решению часто служит та часть конструкции, где свобода выбора — наи­меньшая. Именно это мы и назовем узким мес­ том. Ясно, что от узкого места быстрее дойти до противоречия или легче построить заметный кусок возможной конструкции.

Давайте посмотрим, где можно выявить уз­ кие места и использовать их для решения за­ дач. Наряду с интуицией на помощь приходят известные приемы решения задач: соображения непрерывности, принцип крайнего, раскраска, принцип Дирихле, аналогия, инвариант, мини­ мальный контрпример. Чтобы подчеркнуть особенности каждого из приемов для поиска уз­ких мест, мы сгруппируем задачи по небольшим главам.

Изложение ведется в основном путем разбора задач, называемых примерами. А вот упражне­ ния и задачи остаются читателю для самостоя­ тельного решения.

Ищи главное препятствие

Кто нам мешает, тот нам и поможет.

К/ф «Кавказская пленница»

Самая главная идея: поглядеть на задачу «сверху». Если удастся понять, где нам будет всего труднее, то начать нужно именно с попыт­ ки преодоления этой трудности.

Пример 1. Можно ли разрезать какой-нибудь прямоугольник на равнобедренные треугольни­ ки с углом 40° при основании?

Анализ и решение. Узким местом, очевидно, будет угол прямоугольника. Его надо сложить из углов треугольников. Однако есть только углы в 40° (при основании) и 100° (при вершине тре­ угольника). Из них прямой угол не сложишь. Значит, и весь прямоугольник на такие тре­угольники разрезать нельзя.

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

Пример 2. Несколько ученых переехали из страны А в страну В. Мог ли в результате сред­ ний IQ (коэффициент интеллекта) в обеих стра­ нах увеличиться?

Анализ и решение. На первый взгляд — нет, ведь «если в одно месте прибыло, то в другом должно убыть». Но это касается только суммы, среднее ведет себя хитрее. Узкое место: понять, как оно себя ведет. Достаточно, впрочем, заме­ тить, что повысить средний IQ в стране В мож­ но, принимая ученых с IQ выше среднего. И наоборот, чтобы повысить средний IQ в стра­ не А, надо избавляться от людей с IQ ниже сред­ него! Такое возможно, если средний IQ вА выше среднего и В: организуем переезд ученых с IQ из зазора между средними.

Попробуйте ответить на более хитрый вопрос.

Задача 1. Возможно ли повышение IQ в обе­ их странах, если там нет ни одного человека, чей IQ попадал бы в зазор между средними IQ в этих странах?

Если конструкций много, то полезно поис­кать общее узкое место. Это может сработать не только при доказательстве невозможности, но и при построении способа. Классический при­ мер: для противодействия всем планам вторже­ния — взрываем все мосты!

Пример 3. На бесконечном листе клетчатой бумаги играют двое, ходят по очереди. Своим ходом можно выбрать любую незакрашенную сторону клетки и покрасить ее в любой цвет (чис­ ло цветов неограниченно). Первый выиграет, если после его хода образуется замкнутая лома­ ная, где все звенья окрашены в разные цвета. Может ли второй ему помешать?

Задача 2. Верно ли, что любой треугольник можно разрезать на 1000 частей, из которых можно сложить квадрат?

Задача 3. На бесконечной клетчатой доске двое играют в крестики-нолики по обычным правилам: выигрывает тот, кто первым выстро­ит 5 своих знаков в ряд по вертикали или гори­зонтали (ряд по диагонали не считается). Дока­жите, что второй может гарантировать себе как минимум ничью.

Засада на переправе (непрерывность обычная и дискретная)

Сколь ни вдоль, а поперек изволь.

Если объекты или ситуации задачи можно разделить на две категории («два берега») и если путь начинается на одном берегу, а заканчива­ется на другом, то неизбежно придется переправ­ляться. Часто именно это оказывается узким местом. Надо только убедиться, что не удастся переправиться, не замочив ног. В частности, если некоторая величина принимает целочисленные значения, изменяется на каждом шаге не более чем на 1 и в процессе меняет знак, то она обяза­тельно проходит через 0. Такая величина назы­вается дискретной, а прием решения — диск­ретной непрерывностью. Здесь положительные значения — один берег, отрицательные — дру­гой, значение 0 — речка. Решение задачи этим методом сводится к нахождению подходящей дискретной величины (подходящей в том смыс­ле, что прохождение через 0 дает то, что требу­ется) и проверке, что путь проходит через точки обоих берегов.

Анализ. Процесс очевиден: выход журнала. Берега тоже: один — номера журнала, меньшие года выхода, другой — большие. За дискретную величину естественно взять разность номера журнала и года выхода: разность 0 доказывает утверждение. Ясно, что разность меняется на 1 в моменты выхода журнала или смены года. Ясно также, что сейчас она отрицательна, а лет через 1000 с хвостиком станет положительной. Зна­чит, момент равенства года и номера все-таки наступит.

В предыдущем примере у нас изначально были две величины, и естественно было делить на бе­рега так: на одном первая больше, на другом — вторая. Чаще, однако, такие величины прихо­дится вводить самим: в этом и состоит искусст­во! Разумеется, если величина нецелочисленная, но изменяется непрерывно между двумя значе­ниями, она обязана принять и все промежуточ­ные значения.

Пример 5. В противоположных углах квад­ратного пруда со стороной 100 м сидели два гуся. Поплавав по пруду, они оказались в двух дру­гих противоположных углах. Докажите, что в некоторый момент расстояние между кончика­ми их клювов было ровно 110 м.

Анализ. Естественно разделить все располо­жения пары гусей на два «берега»: когда рас­стояние между ними больше 100 м и когда мень­ше. Начальное расстояние — это примерно диа­гональ квадрата, оно явно больше 110 м. Прав­да, и конечное расстояние больше 110 м. Одна­ко переплывая в другие углы, гусям придется приблизиться друг к другу. Попробуем поймать момент, когда они будут ближе 110 м друг к другу. Узкое место — ширина пруда (от сторо­ны до стороны): когда гуси напротив друг дру­га, расстояние между ними не больше ширины.

Решение. Пусть гуси изначально сидели в уг­лах А и С квадрата АВС.О, а в конце концов ока­зались в углах В та О соответственно. Вначале один гусь был ближе к стороне ВС, а в конце — другой. Значит, был момент, когда расстояния до ВС были одинаковы. В этот момент отрезок, соединяющий их носы, был параллелен стороне ВС, его длина была меньше ВС и меньше 110 м. А в начальный момент расстояние это было боль­ше 110 м. По непрерывности между этими моментами был момент, когда расстояние было равно 110 м.

В предыдущем примере нам самим пришлось «строить берега». Бывает и наоборот: «берега» есть, а процесса нет. Тогда его надо организо­вать, причем так, чтобы «на переправе» был до­стигнут нужный эффект.

Пример 6. Плоскость раскрашена в два цве­та. Докажите, что найдутся точки разного цве­та на расстоянии 1.

Анализ. Берега очевидны: цвета. Организуем процесс перехода с одного берега на другой. Можно пройти между точками разного цвета по прямой или по непрерывной кривой, цвет сме­нится, но как обеспечить расстояние 1? Идея: будем идти шагами длины 1.

Решение. Выберем две точки А и В разного цвета и пройдем из А в В шагами длины 1. Это можно сделать, например, идя от А к В по пря­мой с шагом 1. Если же для последнего шага останется отрезок СВ, короче 1, то построим равнобедренный треугольник СОВ со сторонами СО = ВВ = 1 и сделаем вместо шага С В два шага: СО и ОБ. Проследим за цветом точек, по кото­рым шагаем. На каком-то шаге цвет сменится? Начало и конец шага и дадут искомые точки.

Зная, что узким местом конструкции являет­ся переправа, будем доказывать ее неизбеж­ность — при доказательстве невозможности. Наоборот, при построении примера нужно так строить берега, чтоб они не соприкасались и пе­реправ не возникало.

Пример 7. Можно ли расставить в таблице 8×8 числа от 1 до 64 так, чтобы ни в какой паре клеток с общей стороной или вершиной сумма не делилась: а) на 3; б) на 4?

Анализ. Ясно, что можно заменить все числа на остатки по соответствующему модулю. То есть в (а) можно расставлять О, 1 и 2 (причем единиц на одну больше, чем нулей или двоек), а в (б) — О, 1, 2 и 3 (всех поровну).

Решение, а) Надо избегать ставить нули ря­дом, их придется разбросать изолированными «озерками», окруженными единицами и двой­ками. Можно ли избежать соприкосновения еди­ницы и двойки? Нет: «берег единиц» сомкнется с «берегом двоек», так как «речку» из нулей между ними построить нельзя.

б) Нельзя ставить нули рядом с нулями и двойки рядом с двойками. Расположим их изо­лированными «озерками». Остаются единицы и тройки. Можно ли их отделить друг от друга? Да, ибо теперь мы можем построить «речку», чередуя нули и двойки.

Задача 4. На доске 4×4 расставляются 16 шахматных коней четырех мастей — воро­ные, соловые, гнедые и каурые. Существует ли такая расстановка коней, в которой вороные не бьют соловых, соловые — гнедых, гнедые — каурых, а каурые — вороных?

Задача 5. Найдутся ли 1000 последователь­ных натуральных чисел, среди которых ровно 5 простых чисел?

Задача 6. Есть несколько кусков сыра разно­го веса и разной цены за килограмм. Докажите, что можно разрезать не более двух кусков так, что после этого можно будет разложить все кус­ки на кучки одинакового веса и одинаковой сто­имости.

Узкие места — в первую очередь (принцип крайнего)

Век свободы не видать.

Принцип крайнего советует обратить внима­ние в первую очередь на объекты «с краю», где край понимается в геометрическом или арифме­тическом (максимум, минимум) смысле. Узкое место является крайним в том смысле, что там степень свободы — наименьшая. Оно вполне может в геометрическом или каком-то другом естественном смысле оказаться посередине. В этом случае бездумное применение принципа крайнего к успеху не приведет. Более подробно см. в [6].

Подсчет узких мест (раскраска и принцип Дирихле)

Каждому пассажиру — по мягкому месту.

Сколько пассажиров может перевезти поезд — зависит от числа мест. А как быстро пассажиры смогут высадиться — зависит от числа дверей. Точно так же и в задаче можно получить иско­мую оценку, выделив узкие места и подсчитав их количество.

Пример 8. Дан правильный треугольник. Каким наименьшим числом меньших правиль­ных треугольников его можно покрыть?

Анализ. Накрыв почти весь треугольник чуть меньшим, мы быстро обнаружим, что оставшу­юся узенькую полоску или даже просто сторону исходного треугольникам одним меньшим тре­угольником накрыть нельзя. Итак, стороны — узкое место, но для подсчета они не годятся: ведь можно накрывать стороны и по частям. Заметим, однако, что мы не можем накрыть оба конца стороны (то есть две вершины) одновре­менно. Вот оно — узкое место!

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

В примере выше вершины уже сами по себе стояли особняком. Если таких явно выделенных объектов нет, бывает удобно самим выделить часть из группы однородных объектов — напри­мер, покрасить часть клеток доски.

Пример 9. Докажите, что 11 коней не могут побить все оставшиеся поля шахматной доски.

Анализ и решение. Изучим сперва произволь­ный треугольник с вершинами в узлах сетки. Длины его сторон по теореме Пифагора имеют вид Но тогда площадь S = Источник

Математика. Решение нестандартных математических задач. Примеры.

Приемы решения нестандартных математических задач: непрерывность, принцип крайнего, раскраска, принцип Дирихле, аналогия, инвариант, минимальный контрпример.

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

Анализ и решение. Ломаных бесконечно много, и зада- ча второго «испортить все» кажется нереальной, тем более, что любое звено можно обойти. Однако ложка дегтя портит бочку меда. Присмотримся: нет ли у всех ломаных общего свойства, которое можно было бы объявить узким местом? Ну, поворачивать они все должны, чтобы замкнуться. Ага, повороты могут быть разные, но среди них обязательно найдется поворот в виде буквы Г (речь, конечно, идет о паре соседних звеньев: одно выходит из общей вершины вправо, другое — вниз. А еще бывают L-повороты и два по- ворота, для которых букв нет, а именно, пары вверх-влево и вниз-влево). Вот вам и узкое место! Испортим все Г-повороты: разобьем все звенья на Г-пары, и как только первый закрасит одну половинку пары, второй должен покрасить вторую половинку в тот же цвет.

Указания. Попробуйте, воспользовавшись результатом и раскраской из предыдущего примера, построить требуе- мую расстановку из 12 коней. При этом надо обязательно побить все покрашенные поля, одновременно стараясь побить максимум из еще не побитых полей. Практично расставлять коней тройками и использовать симметрию: тогда достаточно убедиться, что побиты поля одного из угловых квадратов 4 × 4. Не стоит только пытаться по- бить весь угловой квадрат стоящими в нем конями, можно и нужно принять «помощь извне».

Источник

Какое наименьшее количество коней могут бить все белые клетки шахматной доски?

Какое наименьшее количество коней могут бить все белые клетки шахматной доски.

7, но думаю теперь как это доказать).

32 ШАХМАТНЫХ КОНЯ РАССТАВИЛИ ТАК ЧТОБЫ КАЖДЫЙ КОНЬ РУБИЛ ДВОИХ КОНЕЙ?

32 ШАХМАТНЫХ КОНЯ РАССТАВИЛИ ТАК ЧТОБЫ КАЖДЫЙ КОНЬ РУБИЛ ДВОИХ КОНЕЙ.

Лучше сделать фотографию или конь = 1, черные клетки = 2, край доски = 3.

На шахматной доске стоят 16 пешек?

На шахматной доске стоят 16 пешек.

Какое наименьшее количество ходов конём понадобится, что бы побить все пешки?

На шахматной доске стоят 16 пешек?

На шахматной доске стоят 16 пешек.

Шахматный конь начинает свой маршрут из левого нижнего угла доски а заканчивает в верхнем левом может ли он побываь в каждом клетке?

Шахматный конь начинает свой маршрут из левого нижнего угла доски а заканчивает в верхнем левом может ли он побываь в каждом клетке.

Двое по очереди ставят коней в клетки шахматной доски так, чтобы кони не били друг друга?

Двое по очереди ставят коней в клетки шахматной доски так, чтобы кони не били друг друга.

Проигрывает тот кто не сможет сделать ход.

Какую часть составляют клетки первой горизонтали на шахматной доске?

Какую часть составляют клетки первой горизонтали на шахматной доске.

Какое наименьшее число ладей могут побить всю шахматную доску?

Какое наименьшее число ладей могут побить всю шахматную доску?

Каждая ладья бьёт только одну вертикаль и только одну горизонталь.

Какое наименьшее количество слонов нужно расставить на доске 8×88×8 так, чтобы они били все клетки доски?

Какое наименьшее количество слонов нужно расставить на доске 8×88×8 так, чтобы они били все клетки доски?

(Клетка на которой стоит слон тоже считается побитой им).

Сколькими способами можно поставить 3 пешки на белые клетки шахматной доски?

Сколькими способами можно поставить 3 пешки на белые клетки шахматной доски?

Не глядя на шахматную доску, выбирают две клетки?

Не глядя на шахматную доску, выбирают две клетки.

Какое из событий будет равновероятным что клетки будут : а)черной и белой б)обе белые в)обе черные.

Т. к. Высота парты 47 см, а высота письменного стола на 15 см выше, то получаем такой пример 47 + 15 = 62 Ответ : 62.

47 + 15 = 62(см. ) Ответ : высота пис. Стола 62 см.

54, 6 * 5 = 273км расстояние которое прошел 1 поезд 273 + 20, 8 = 293, 8км расстояние которое прошел 2 поезд 293, 8 : 5 = 58, 76км / ч скорость второго поезда Ответ 58, 76 км / ч.

12000 м / мин, 200 м / сек.

Источник