Студопедия — Решение. Доказательство максимальности: Разобьём доску на 16 квадратиков, в каждом может быть не более одного короля.
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Решение. Доказательство максимальности: Разобьём доску на 16 квадратиков, в каждом может быть не более одного короля.






Ответ: 16 королей.

Доказательство максимальности: Разобьём доску на 16 квадратиков, в каждом может быть не более одного короля.

 

 


 

V.Раскраски

1. Свойства раскрасок

Раскраска «решает» задачу, если она:

Инвариантна, т.е. при любом движении замощающей фигуры сохраняется некоторое свойство. Например, количество чёрных клеток постоянно или количество белых клеток нечётно

 

Виды и модификации раскрасок

Основные виды:

Шахматная

Диагональная

Галетная

 

 

Подвиды:

Крупная

 

Многоцветная


 

 

Способы прийти к противоречию

Доказать, что клетчатую доску 10´10 нельзя разрезать по линиям сетки на прямоугольники 1´4.

По количеству

                   
                   
                   
                   
                   
                   
                   
                   
                   
                   

 

Решение. Разделим доску на квадраты 2´2 и раскрасим их в шахматном порядке. Заметим, что любой прямоугольник 1´4 содержит поровну (по 2) чёрных и белых клеток, но при данной раскраске на доске ______ чёрных клетки и ___ белых, т.е. не поровну. Значит, разрезать доску 10´10 на тетрамино 1´4 не удастся.

 

По делимости без уравнения

Решение. Применим вертикальную полосатую раскраску доски в два цвета. Тогда любая вертикальная тетрамино содержит кратное 4 (0 или 4) количество чёрных клеток, а любая горизонтальная – 2 чёрные клетки. А так как общее количество чёрных клеток – 50, т.е. при делении на 4 даёт остаток 2, то общее число горизонтальных прямоугольников равно нечётному числу. Рассуждая аналогично для горизонтальной полосатой раскраски, мы докажем, что общее число вертикальных прямоугольников также равно нечётному числу, но тогда в сумме у нас должно быть чётное количество всех прямоугольников, что не может равняться нужному нам числу 25. Т.е. вывод прежний – разрезать не удастся.

 

По делимости с уравнением

Решение;

Каждая мегадоминошка может занимать либо 1, либо 3 чёрных клетки

Пусть первых будет x штук, тогда вторых штук

Тогда всего чёрных клеток будет:

Значит,

 

Это уравнение не имеет решений в целых числах, значит замостить нельзя

 


 

 

Раскраски для тетрамино

I-тетрамино: тельняшка вертикальная и горизонтальная (по чётности)

T-тетрамино: тельняшка (уравнение, делимость на 3)

L-тетрамино:

Z-тетрамино:

Мигрирующие жуки

Задача: На каждой клетке доски 5 × 5 сидит жук. В некоторый момент времени все жуки взлетают и приземляются на соседние по стороне клетки. Докажите, что при этом обязательно окажется хотя бы одна пустая клетка?

Решение: Раскрасим доску шахматной раскраской.

 

Обходы

Задача 1. Фигура «верблюд» ходит по шахматной доске ходом типа (1, 3). Можно ли пройти ходом «верблюда» с произвольного поля на соседнее?

Решение: Ход верблюда, на которой он стоит, поэтому на соседнюю клетку перейти он не сможет.

 

Задача 2. Шахматный король обошёл всю доску 8*8, побывав на каждой клетке по одному разу, вернувшись последним ходом в исходную клетку. Докажите, что он сделал чётное число диагональных ходов.

Решение: При каждом недиагональном ходе меняется цвет поля, на котором стоит король; при диагональном — не меняется. Поскольку король обошёл всю доску и вернулся обратно, то цвет поля менялся с белого на чёрный столько же раз, сколько с чёрного на белый, значит недиагональных ходов король сделал чётное число. Число диагональных ходов равно 64 минус число недиагональных ходов — чётное число.

 

Задача 2.3: Замок имеет форму правильного треугольника, разделенного на 25 маленьких залов той же формы. В каждой стене между залами проделана дверь. Путник ходит по замку, не посещая более одного раза ни один из залов. Найти наибольшее число залов, которое ему удастся посетить.

Решение:

Ответ: 21 зал.

Доказательство максимальности: Раскрасим треугольник в шахматном порядке. Залов одного цвета (например чёрного) – 15, а другого цвета (белого) – 10. Заметим, что в чёрном зале путник может находиться с самого начала, или попасть в него из белого, поэтому он побывает не более, чем в 11 чёрных залах. Таким образом, не менее 4 чёрных залов останутся непосещёнными.

 

 

[s1]Хэхэй

 







Дата добавления: 2015-08-30; просмотров: 1726. Нарушение авторских прав; Мы поможем в написании вашей работы!



Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Тема: Кинематика поступательного и вращательного движения. 1. Твердое тело начинает вращаться вокруг оси Z с угловой скоростью, проекция которой изменяется со временем 1. Твердое тело начинает вращаться вокруг оси Z с угловой скоростью...

Условия приобретения статуса индивидуального предпринимателя. В соответствии с п. 1 ст. 23 ГК РФ гражданин вправе заниматься предпринимательской деятельностью без образования юридического лица с момента государственной регистрации в качестве индивидуального предпринимателя. Каковы же условия такой регистрации и...

Седалищно-прямокишечная ямка Седалищно-прямокишечная (анальная) ямка, fossa ischiorectalis (ischioanalis) – это парное углубление в области промежности, находящееся по бокам от конечного отдела прямой кишки и седалищных бугров, заполненное жировой клетчаткой, сосудами, нервами и...

Билет №7 (1 вопрос) Язык как средство общения и форма существования национальной культуры. Русский литературный язык как нормированная и обработанная форма общенародного языка Важнейшая функция языка - коммуникативная функция, т.е. функция общения Язык представлен в двух своих разновидностях...

Патристика и схоластика как этап в средневековой философии Основной задачей теологии является толкование Священного писания, доказательство существования Бога и формулировка догматов Церкви...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия