Логическа задача за подреждане на домино върху шахматна дъска. Математически олимпиади и олимпиадни задачи
Дадена е шахматна дъска 8×8, от която са изрязани два диагонално противоположни ъгъла и 31 домино; всяко домино може да покрие две квадратчета на дъската. Възможно ли е цялата дъска да се павира с кости? Дайте обосновка на вашия отговор.
Решение
На пръв поглед изглежда, че това е възможно. Дъската е 8 × 8, следователно има 64 клетки, изключваме две, което означава, че остават 62. Изглежда, че трябва да се поберат 31 кости, нали?
Когато се опитаме да подредим домино на първия ред, имаме само 7 квадрата на наше разположение, една кост отива на втория ред. След това поставяме домино на втория ред и отново една плочка отива на третия ред.
Във всеки ред винаги ще има една кост, която трябва да бъде преместена на следващия ред, без значение колко оформления опитваме, никога няма да можем да подредим всички кости.
Шахматната дъска е разделена на 32 черни и 32 бели клетки. Като премахнем срещуположните ъгли (имайте предвид, че тези клетки са с един и същи цвят), остават 30 клетки от един цвят и 32 клетки от друг цвят. Да предположим, че сега имаме 30 черни и 32 бели квадрата.
Всеки зар, който ще поставим на дъската, ще заема една черна и една бяла клетка. Следователно 31 домино ще заемат 31 бели и 31 черни клетки. Но на нашата дъска има само 30 черни и 32 бели клетки. Поради това е невъзможно костите да се разложат.
Анализът е взет от превода на книгата на Г. Лъкман Макдауъл и е предназначен само за информационни цели.
Ако ви е харесала, препоръчваме ви да закупите книгата.
6. В кутия има 235 кибрита. Двама играчи ги вземат на свой ред. С един ход можете да вземете от 1 до 6 мача. Играчът печели
вземане на последния мач. Кой печели, когато се играе правилно?
62
7. Ъглов квадрат се изрязва от дъска 8 × 8. Възможно ли е да се постави дъската в 1×3 правоъгълници?
8. От 30 мача двама играчи вземат по свое усмотрение от 1
до 6 мача. Печели този, който вземе последната клечка.
9. Има три купчини камъни. Държавата е тройка от числа
(х
1
, х
2
, х
3
), където x i
- броят на камъните в i-тата купчина. Преместването е операция за прехвърляне от купчина на купчина на броя на камъните, равен на броя камъни в купчината, където се извършва прехвърлянето. От първоначалното състояние (11, 7, 6) вземете състоянието (8, 8, 8).
10. Разделете кръга на максималния брой части, като използвате четири прави линии.
11. Изрежете гръцкия кръст с две прави линии, така че
да образуват правоъгълник от получените части, едната страна на който е два пъти по-голяма от другата.
12. В 9 има 12-литров запас от течност и празни съдове
и 5л. Необходимо е да се измери точно 6 литра. Колко литра могат да бъдат измерени с такива съдове от резерв от 12 литра?
13. Определете броя на последователностите с дължина n от (0, 1, 2),
в който няма две последователни единици.
14. Възможно ли е да се покрие квадрат 10 × 10 с фигури от формата
15. Възможно ли е да се покрие квадрат 10 × 10 с фигури от формата
63
16. Възможно ли е да покриете квадрат 8×8 с изрязана ъглова клетка с фигури от формата
17. Възможно ли е да се покрият с фигури от формата на шахматна дъска 8 × 8, в която е изрязан квадрат:
18. Възможно ли е да поставите шахматна дъска с издълбана ъглова клетка с фигури от формата
19. Възможно ли е да се извърши преминаването на четири двойки рицари-оръженосци с помощта на лодка за двама души, ако оръженосецът не може да бъде на един бряг с нечий(и) рицар(и) в отсъствието на неговия господар?
20. Разработете алгоритъм за намиране на двете най-малки числа в неподредена последователност от n числа.
21. От 27 мача, лежащи на масата, двама играчи последователно вземат поне един и не повече от четири мача. Победител е този, който в края на играта има четен брой съвпадения. Разработете алгоритъм за играта на първия играч.
64
22. Двама участници в играта се редуват да наричат число от 1 до 10.
Извиквайки число, играчът го добавя към вече съществуващата сума от числа (извиквайки първото число, играчът го добавя към нула). Играчът, който вкара 100, печели.
Разработете алгоритъм за играта на първия играч.
23. Намерете минималния брой въпроси (възможни отговори:
"да", "не") скрито 5-цифрено число, ако сумата от първите три цифри е 17.
24. Намерете минималния брой въпроси (възможни отговори:
"да", "не") скрито 4-цифрено число, ако сумата от втората и четвъртата цифра е 7.
25. По колко начина могат да се обменят 100 рубли? монети в
5, 10, 20 и 50 рубли?
26. Изчислете рекурсивно броя на шестцифрените числа, чийто сбор от първите четири цифри е 26, а сборът от последните две е 14.
27. Изчислете рекурсивно броя на дяловете на числото 37 с пет члена, първият от които не надвишава 7, вторият
- 5, а третият и четвъртият вземат стойности от набора
{5, 6, 7, 8}.
28. Изчислете рекурсивно броя на седемцифрените числа, чийто сбор от първите четири е 21, а сборът от последните пет е 19.
29. Изчислете рекурсивно броя на дяловете на числото 27 с четири члена, първият от които не надвишава 7,
вторият е 8, а третият и четвъртият приемат стойности от набора (3, 5, 7).
30. Изчислете рекурсивно броя на петцифрените числа, чийто сбор от първите три цифри е 21, а сборът от последните три цифри е 12.
65
31. Изчислете рекурсивно броя на седемцифрените числа, в които сборът на първата и третата цифра е 12, а сборът на останалите пет е 19.
32. Изчислете рекурсивно
(2n − 2)(2n − 4) × . . . ×2
(n + 1)(n + 3) ×. . . × (n + 2n − 1)
a n−5
b
−(n+3)
33. Изчислете рекурсивно броя на седемцифрените числа, чийто сбор от първите четири цифри е 17, а сборът от последните три е 16.
34. Изчислете рекурсивно броя на дяловете на числото 17 по четири члена, първият от които не надвишава 4, вторият - 8, а третият и четвъртият приемат стойностите (3, 4, 8).
35. Изчислете рекурсивно броя на седемцифрените числа, чиято сума от квадратите на първите четири числа е 17, а сумата от квадратите на последните две е 16.
36. Изчислете рекурсивно броя на дяловете на числото 25 от четири члена, първият от които не надвишава 8,
второто е 3, а третото и четвъртото приемат стойности от набора (2, 5, 9).
37. Изчислете рекурсивно броя N поставени топове на дъската
N × N, така че топовете да са симетрични по отношение на двата диагонала и да не се атакуват един друг.
38. Изчислете рекурсивно броя на двоичните поредици от n елемента, в които липсват два съседни.
39. Дадена е решетка N × M:
66
М
н
А
б
Изчислете рекурсивно броя на пътищата от A до B. Пътят е последователност от движения по мрежата, водещи отляво надясно и отдолу нагоре.
40. Дадени са числата a
1
, . . . , a n
в определен ред. За да изчислите произведението a
1
·. . , a n
при запазване на реда на факторите, има много начини за поставяне на скоби между факторите. Изчислете рекурсивно броя на начините за поставяне на скоби.
41. Изчислете рекурсивно броя на 8-цифрените числа, чиято сума от първите пет цифри е 29, а сумата от последните три цифри е 21.
67
3
. методи за анализ на алгоритми
3.1. Алгоритъм класове
В предишните раздели разгледахме различни подходи, които могат да се използват при конструирането на алгоритми. За да се намери решение, за да се анализира ефективността на това решение, човек може да изложи различни предположения, да използва вече известни други алгоритми, да преформулира условието на проблема и т.н. Можете да потърсите някои подобни проблеми с известно решение и да използвате това решение, за да намерите алгоритъм за необходимия проблем.
Има обаче много конкретни проблеми, за които са намерени решения. Има още повече нерешени задачи или решени с някакви ограничения и условия. Търсенето на подобни проблеми сред целия набор от проблеми, оценяването на съществуващи решения според тяхната степен на „пригодност“ може да бъде труден, отнемащ време и не винаги разрешим проблем. Би било по-полезно и продуктивно да се опитаме да дефинираме класове проблеми, обединени от общ проблем, общи методи и подходи за решаване, и след това да потърсим класа, към който може да се припише нашият конкретен проблем, който трябва да бъде решен. Разбира се, не трябва да има твърде много такива класове, но от друга страна, не трябва да има твърде малко от тях, така че всеки нова задачадефинирайте свой собствен, нов клас, който след това е малко вероятно да се използва за решаване на други проблеми.
Като пример за проблем, принадлежащ към определен клас, разгледайте добре известния проблем с идентифицирането на фалшива монета.
Задача 3.1 (проблем за фалшива монета). Има n монети,
сред които може да има един фалшив. Фалшивата монета се различава от останалите по грамаж, а ние разполагаме с везна с две чаши. Изисква се да се определи фалшива монета за минималния брой претегляния или да се установи,
че няма фалшиви монети.
68
Решение. Проблемът с фалшивите монети беше разрешен в разд. 2.2,
но тогава се знаеше, че фалшивата монета непременно е по-лека. Сега нека се опитаме да решим този проблем за по-общ случай. Всяко решение на този проблем (не непременно оптимално)
може да се тълкува като последователност от претегляния. Ясно е обаче, че изборът на монети за претегляне на всяка стъпка зависи от това кои монети са използвани и резултатите от претеглянето в предишните стъпки. Ще изобразим последователността на претеглянията, както следва. Ние преномерираме монетите и ги дефинираме като набор S = (1, 2, . . . , n). Наборите от числа монети, претеглени в лявата и дясната част на везната, могат да бъдат означени с S
Л
и С
Р
съответно. Ясно е, че претеглянето има смисъл само ако мощностите на множествата S
Л
и С
Р
мач, т.е. Всяка везна има еднакъв брой монети. Претеглянето ще бъде обозначено със знака ":", след това всяко претегляне
(С
Л
) : (С
Р
) има три възможни изхода. Много монети
С
Л
може да бъде по-лек, по-тежък или със същото тегло като комплекта S
Р
. Тогава ще обозначим тези резултати от претеглянето като
"" или "=", съответно. Пример за теглене на четири монети е показан на фиг. 3.1. Овалите представляват претеглянията, квадратите представляват резултатите, указващи номера на фалшивата монета и дали е по-лека или по-тежка от останалите.
Случаят на липса на фалшива монета е обозначен с "0", задрасканите квадратчета съответстват на случаи, които не могат да се появят.
Ще оценим максималния брой претегляния, необходими за решаване на проблема, т.е. най-лошия случай. Както се вижда от фиг. 3.1, проблемът се решава с 3 претегляния в най-лошия случай. Имайте предвид, че дори и в най-добрия случай се нуждаем от поне 2
претегляне. Може ли да се постигне по-добър резултат?
На фиг. 3.1 представя друго решение на проблема с претеглянето на четири монети. На първата стъпка претегляме не няколко монети, а всички монети, като ги разделяме на два комплекта. В резултат на това постигнахме, че в най-добрия случай е необходимо само едно претегляне,
но в най-лошия случай броят на претеглянията отново е 3.
69
(1) : (2)
(1) : (3)
(1) : (4)
0 4 Т
4 л
3 Т
3 л
(1) : (4)
2 т
1 л
(1) : (4)
2 л
1 т
=
=
=
>
>
>
>
>
=
=
Ориз. 3.1. Решаване на проблема с фалшивите монети
Имайте предвид, че за разлика от първата опция за претегляне,
показано на фиг. 3.1, във втората версия ние не само дефинирахме схемата за претегляне, но също така въведохме нова концепция за кандидати за фалшиви монети. Наистина, разгледайте резултата от първото претегляне, (1, 2) : (3, 4). Нека (1, 2) L
= (1, 2) и S
Р
= (3, 4). Тогава
С
Л
Р
. От този резултат не е възможно да се прецени дали фалшивата монета е по-лека или по-тежка от всички останали,
и в какъв комплект е. Въпреки това може да се предположи
(и още по-точно - може да се твърди), че ако една фалшива монета принадлежи на множеството S
Л
, тогава фалшивата монета е по-лека от останалите, ние обозначаваме такъв комплект с буквата L. В нашия случай, ако монетите с номера 1 или 2 са фалшиви, те са по-леки от истинските. Ако фалшивите монети с цифри 3 или
4, то те са по-тежки от реалните, ще обозначим съответното множество с буквата Т. На фиг. 3.2 кандидатите за леки и тежки фалшификати са обозначени с маркировки по краищата на дървото.
Очевидно човек може да отговори на въпроса за оптималния брой претегляния, като продължи да сортира възможните схеми за избор на монети. Тъй като броят на монетите е ограничен, рано или късно такова изброяване може да бъде завършено. Засега нека се спрем на двете получени решения и да се опитаме да анализираме какво дадоха
70
(1.2) Л
(3.4) Т
(1.2) Т
(3.4) Л
(1,2) : (3,4)
(3) : (4)
4 Т
3 Т
(1) : (2)
1 л
=
=
>
>
>
=
0 2 л
(3) : (4)
3 л
4 л
(1) : (2)
2 т
=
>
>
=
1 т
Ориз. 3.2. Друго решение на проблема с фалшива монета към нас от гледна точка на общ подход към решаването на проблема.
Както е известно, всяка стратегия за претегляне на монети може да бъде описана с помощта на троично или троично дърво. С други думи, разглежданият проблем принадлежи към класа проблеми,
описани от троични дървета. Такава класификация на проблема позволява да се анализира не всяко конкретно решение, а всички решения като цяло, въз основа на известните свойства на дърветата.
Така итерацията приключи възможни начинипретеглянето всъщност е търсене в различни троични дървета, от които, разбира се, има експоненциално много. От друга страна, нека се опитаме да определим какво по принцип е възможно да се постигне при решаването на даден проблем, използвайки принадлежността му към този конкретен клас.
От фиг. 3.1 и 3.2 може да се види, че изобразявайки последователността от претегляния с помощта на дърво, ние приписваме всяко претегляне на връх на дърво, който не е лист (изобразен с помощта на овали), докато резултатите, включително невъзможните,
съответства на листата на дървото (показано с квадратчета). Всички възли на дървото могат да бъдат подредени по нива,
71
AT
а
=
=
>
AT
а
И
И
И
=
>
AT
а
И
И
И
=
>
AT
а
И
И
И
=
>
AT
а
И
И
И
=
>
AT
а
=
>
AT
а
=
>
AT
а
>
Да се
AT
Л
При
0
При
1
При
л
-
1
При
л
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
Ж
а =
л
Ориз.
3.3.
T
пролетно тегло дърво
72
тези. от разстоянието им от корена на дървото. Номерът на нивото е равен на броя на ръбовете, които трябва да преминат от корена, за да стигнат до върха. дадено ниво(фиг. 3.3). Ако дълбочината на дървото е нивото на най-отдалечения от корена лист, тогава тази стойност е равна на броя на претеглянията в най-лошия случай.
Колко възможни изхода има в нашия проблем? Всяка от n монети може да се окаже фалшива лека или фалшива тежка монета и може изобщо да няма фалшиви монети.
Така имаме 2n + 1 резултата. Това означава, че в дървото
съответстващ на схемата за претегляне, трябва да бъде най-малко
2n + 1 листа. Троично дърво с дълбочина l съдържа най-много,
от 3
тръгвам си. От това можем да оценим минималната възможна дълбочина на дървото
3
л
≥ 2n + 1,
и следователно
l ≥ log
3
(2n + 1).
(3.1)
Така при n = 4 минималният възможен брой претегляния е по-голям или равен на 2. Тук имаме предвид не минималния брой претегляния за тази схема - както на фиг. 3.2, а има случаи, когато решението на задачата е вече намерено след първото претегляне - оценяваме най-лошия вариант, т.е. максималния брой претегляния за дадена схема, с други думи, търсим минимум сред максималните дълбочини на всички дървета с най-малко 2n + 1 листа.
Въпреки това може да се покаже, че няма метод за претегляне, който да даде равенство в оценката (3.1).
ТЕОРЕМА 3.1
Броят на претеглянията в най-лошия случай за проблема с фалшивите монети се оценява като l > log
3
(2n + 1).
Доказателство. Както вече споменахме, за n монети има 2n + 1 възможни изхода. Всяко претегляне може да има три възможни резултата и всеки резултат има свой собствен
73
схема на по-нататъшни претегляния. В същото време схемата има свой собствен брой възможни резултати, като се вземе предвид резултатът от последното претегляне. Нека при първото претегляне |S
Л
| = |S
Р
| = k, т.е.
k монети се използват на една везна и k монети на друга,
където k ≤ n/2. Ако в същото време С
Л
Р
, след това монети от С
Л
обявяваме кандидати за леки фалшиви монети и монети от S
Р
- Кандидати за тежки фалшиви монети. По този начин,
с резултата от първото претегляне са възможни 2k резултата.
По същия начин за С
Л
>С
Р
Възможни са 2 хиляди други изхода. Следователно, за С
Л
=S
Р
останалите 2n + 1 − 4k резултата са възможни.
Ако е изпълнено равенството в (3.1), това означава, че троичното дърво е пълно и всичките му листа са на l-то ниво.
Но за това е необходимо след всяко претегляне възможните резултати да се разпределят равномерно по трите клона и равенството
2k = 2n + 1 − 4k,
което е невъзможно, тъй като 2k винаги е четно число и
2n + 1 − 4k винаги е нечетно.
В доказателството на теорема 3.1 беше използвана важна идея:
За да бъде тегловното дърво оптимално или поне възможно най-близко до оптималното, е необходимо резултатите да бъдат разпределени равномерно върху всички резултати от всяко претегляне.
По този начин получихме оценка за най-лошия брой претегляния в проблема с фалшивите монети, като свързахме този проблем с класа проблеми
описани от троични дървета. Сега разгледайте един леко модифициран проблем.
Проблем 3.2 (проблем за фалшива монета при наличие на стандарт). Има n монети, сред които може да има една фалшива и още една монета, за която със сигурност се знае, че е истинска. Изисква се да се определи фалшивата монета в минималния брой претегляния или да се установи, че няма фалшиви монети.
74
Решение. Тази задача се различава от предишната по наличието на допълнителна референтна монета, но се оказва, че тази допълнителна монета позволява да се конструират дървета с оптимално тегло, за които е изпълнено равенството в (3.1). Означаваме с n l
числото, за което е валидно равенството
3
л
= 2n l
+ 1.
(3.2)
При разглеждане на предишния проблем в теорема 3.1 получихме: за да бъде изпълнено равенство (3.1), тегловното дърво трябва да е пълно. Следователно, ако е възможно да се изгради такова оптимално дърво от l нива, тогава то ще определи схема от l тегла за n l
монети. Обърнете внимание, че следната връзка е вярна:
n l
= 3nl−1
+ 1.
(3.3)
Тъй като за n
0
= 0 в (3.2) получаваме равенството 3 0
= 2 0 + 1,
тогава от тук използвайки (3.3) можем да получим n
1
= 1,n
2
=
4, п
3
= 13 и т.н. Решение (3.2) е последователността
0, 1, 4, 13, 40, . . ..
Така, когато е изпълнено равенство (3.2), множеството от n
l монети са разделени на три равни части с n l−1
монети и все още е останала една монета. Нека разгледаме различни ситуации, които могат да възникнат по време на процеса на претегляне.
Схема 1. Нека в началото на претеглянето имаме n i
монети, където n i
принадлежи на последователността (3.3) за някои i. Нека поставим n i−1
монети, където n
аз
= 3n i−1
+ 1,
след това добавяме референтна монета към лявата част на везната и една от останалите n i−1
+ 1 монети. Означете претеглените множества, както преди, със S
Л
и С
Р
Сега нека в резултат на претеглянето S
Л
=S
Р
. Тъй като еталонната монета е участвала в претеглянето, очевидно е, че фалшивата монета, ако има такава, е сред неизползваните n
i−1
монети и проблемът се свежда до проблем с n i−1
монети. При което
75
В резултат на претеглянето все още имаме възможни 2n i−1
+ 1 =
3
i−1
резултати. Сега нека С
Л
Р
. Това означава, че фалшивата монета е или в комплекта S
Л
и същевременно е по-лек от останалите или в комплекта S
Р
и тогава е по-тежък от другите.
Освен това има n i−1
подозрителни леки монети и n i−1
+ 1 подозрително тежък и заедно това отново дава 2n i−1
+ 1 = 3
i−1
възможни резултати.
Накрая нека С
Л
>С
Р
. Тогава имаме n i−1
кандидати за тежки монети и n i−1
+1 кандидати за бели дробове и общо 2n i−1
+1 =
3
i−1
резултати. И така, с такава схема на първото претегляне, всъщност получаваме това 3
i първоначалните резултати бяха равномерно разпределени според резултатите от претеглянето. За да определите дали е възможно да настроите схемата за претегляне, така че след всяко претегляне резултатите да се разделят на равен брой части, разгледайте резултатите от претеглянето. Очевидно за С
Л
=S
Р
стигаме до същия проблем, само че с по-малка размерност и винаги можем да извършим претеглянето по схема 1 отново, но с по-малка стойност на i.
Схема 2. Нека сега S
Л
Р
. В този случай ние определяме стратегията за претегляне, както следва. Първоначалните данни са, че на някаква стъпка i в последователността от претегляния имаме 3
аз
= 2n i
+ 1 монети, сред които n i
леки фалшиви кандидати и n i
+ 1 кандидати за тежки, докато числото n i
е число от вида (3.3)
n i
= 3n i−1
+ 1.
Поставете върху всяка везна чаша n i−1
лесни кандидати и n
i−1
+1 тежък. Тъй като има само 2n i
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
монети и претеглете
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
монети, тогава все още има 2n i−1
+ 1 монети, сред които n i−1
+ 1
бели дробове и n i−1
тежък. Тъй като има еднакъв брой леки и тежки монети и на двете везни, тогава ако везните не са балансирани,
това дава n i−1
кандидати за леки монети (от купата, която се оказа по-лека) и n i−1
+ 1 кандидати за тежко (от купата, която се оказа
76
по-тежки). Това ни води до оригиналните данни на същата схема
(схеми 2), но за 3
i−1
= 2n i−1
+ 1 монети. Ако везните са уравновесени, това означава, че трябва да търсим фалшива монета сред непретеглените n i−1
+ 1 бели дробове и n i−1
тежки монети, което съответства на схема 3. Очевидно 2n i−1
+1 резултати, т.е. отново наборът от всички възможни резултати е разделен на три равни части.
Схема 3. Нека сега S
Л
>С
Р
. В този случай имаме 3
аз
=
2n i
+ 1 монети, сред които n i
+ 1 леки фалшиви кандидати и n i
кандидати в тежка категория. Всички аргументи са подобни на схема 2, с тази разлика, че при претегляне трябва да поставите n i−1
+ 1 лесни кандидати и n i−1
тежък. Ако везните не са балансирани, това отново ни дава модел 3 за 3
i−1
монети, в противен случай получаваме условията за претегляне, съответстващи на Схема 2. Отново във всички случаи наборът от възможни резултати се разделя на три равни части от 2n i−1
+ 1.
Така имаме три пъти
1 2
3
=
>
=
=
Ориз. 3.4. Преходи между схемите за претегляне в проблема с фалшивите монети в лично състояние, описан по-горе, и правилото за претегляне за всяко състояние. В зависимост от резултата от претеглянето преминаваме в друго състояние (или оставаме в същото състояние), но за по-малък брой монети. При всяко претегляне броят на възможните резултати се разпределя равномерно според резултатите от претеглянето. Схемата на преходите между състоянията е показана на фиг. 3.4. Пример за теглене на 27 монети е показан на фиг. 3.5.
77
Докажете, че шахът е 10х10 не може да бъде нарязан по линиите на мрежата на правоъгълници 1х4. (Решения според Д.Ю. Кузнецов.)
Решение 1 . Разделете дъската на квадратчета 2х2 и ги оцветете в шахматен ред (фиг. 1). Имайте предвид, че всеки правоъгълник 1x4 съдържа еднакво (2) черни и бели клетки, но с това оцветяване има 52 черни клетки и 48 бели клетки на дъската, т.е. не еднакво. Това означава, че няма да е възможно да нарежете дъска 10x10 на правоъгълници 1x4.
Решение 2 . Нека оцветим дъската с диагонално оцветяване в 4 цвята (фиг. 2). Обърнете внимание, че всеки правоъгълник съдържа по една клетка от всеки от четирите цвята, но с дадено оцветяване на дъската има 25 клетки от 1-ви и 3-ти цвят, 26 клетки от 2-ри и 24 клетки от 4-ти, т.е. не еднакво. Това означава, че няма да е възможно да нарежете дъска 10x10 на правоъгълници 1x4.
1. Изрежете долните десни и леви ъглови клетки от шахматната дъска. Възможно ли е да разрежете получената фигура на домино 1x2? И ако изрежете долния десен и горния ляв?
2. Възможно ли е дъска 6x6 да се нареже на домино, така че сред тях да има точно 11 хоризонтални? (Хоризонтално оцветяване в два цвята.)
3. Оцветете рисунката в четири цвята, така че съседните части да са боядисани в различни цветове. Може ли да се мине с три цвята? (Вижте Дейност 6: Оцветяване географска карта- 5-6 клас).
4. В квадрат 4x4 клетките на лявата половина са боядисани в черно, а останалите в бяло. В една операция е позволено да преоцветите всички клетки във всеки правоъгълник в противоположния цвят. Как да получите шахматно оцветяване от оригиналното оцветяване в три операции?
5. Няколко скакалци седят на една и съща права линия, а разстоянията между съседите са еднакви. Всяка минута един от тях скача до точка, симетрична на него спрямо друг скакалец. Може ли след известно време скакалецът Саша да се озове на мястото, където съседът му Лиоша седеше в началото?
6. а) Възможно ли е да се разреже шахматна дъска на фигури, състоящи се от 4 клетки във формата на буквата "Т"?
б) Възможно ли е да се нареже шахматна дъска 10x10 на такива фигури?
7. Възможно ли е да се раздели квадрат 8x8 с отрязан ъгъл на правоъгълници 1x3?
8. Може ли дъска 10x10 да бъде нарязана на парчета от четири клетки във формата на буквата "L"? (Хоризонтално оцветяване в два цвята.)
9. Дъска 8x8 се нарязва на домино 2x1. Може ли да има 15 вертикални и 17 хоризонтални домино?
10. Триъгълникът е разделен на триъгълници (25 части), както е показано на фигурата. Бръмбарът може да ходи в триъгълник, движейки се между съседни (отстрани) триъгълници. Какъв е максималният брой триъгълници, през които бръмбарът може да премине, ако е посетил всеки триъгълник не повече от веднъж?
11. Какъв е най-големият брой ромби, всеки от които е съставен от два равностранни триъгълника със страна 1, които могат да бъдат изрязани от равностранен триъгълник със страна 5 (виж фигурата от предишната задача).
12. Триъгълният замък е разделен на 100 еднакви триъгълни зали. В средата на всяка стена има врата. Колко стаи могат да бъдат посетени от човек, който не иска да посещава никъде повече от веднъж?
Глава 2 шахматна дъска
За подробно описание на шахматната математика, което предстои да започнем, е най-естествено да започнем с задачи по математиказа самата дъска, без все още да поставяте фигури върху нея. Именно на тази тема е посветена тази глава.
Нека първо да разгледаме няколко проблема за покриване на дъска с домино 2 × 1. Навсякъде се приема, че всяко домино покрива две полета от дъската, а всяко поле е покрито от половината от доминото. Да започнем със следващия стар проблем.
Може ли да се покрие с домино квадрат с размери 8×8, от който са изрязани противоположни ъглови клетки (фиг. 2а)?
Можем да използваме алгебрични разсъждения, но "шахматното" решение е едновременно по-просто и по-елегантно. Нека оцветим нашия пресечен квадрат в черно и бяло, превръщайки го в шахматна дъска без две ъглови полета a8 и h1 (фиг. 2b). За всяко покритие на дъската всяко домино покрива едно бяло и едно черно поле. Имаме две бели полета по-малко от черните (изрязаните полета са бели) и следователно необходимото покритие не съществува! Както виждаме, оцветяването на дъската не само улеснява шахматиста да се ориентира по време на играта, но също така служи като средство за решаване на математически задачи.
В разглежданата задача беше важно не ъгловите полета да са изрязани от дъската, а те да са с един и същи цвят. Ясно е, че както и да изрежете чифт едноцветни полета, няма да можете да покриете останалата част от дъската с домино. Така възниква следният проблем.
Да предположим сега, че на шахматната дъска са изрязани две полета с различни цветове. Винаги ли е възможно да покриете останалата част от дъската с 31 домино?
Оказва се, че винаги. Едно грандиозно доказателство е намерено от известния американски математик Р. Гомори. Нека начертаем на шахматната дъска границите между вертикалите и хоризонталите, както е показано на фиг. 3. В лабиринта между тези граници черни и бели полета следват едно друго, редувайки се като бутони от два цвята върху затворена нишка (пътят, по който може да се заобиколи този лабиринт, е затворен). Каквито и две полета с различни цветове да изрежем от дъската, нишката ще се скъса: на едно място, ако изрязаните полета са съседни, и на две места в противен случай. В този случай всяка част от нишката ще се състои от четен брой полета. Следователно тези фигури, а оттам и цялата дъска, могат да бъдат покрити с домино!
Ориз. 3. Лабиринт Gomory |
Любопитни идеи, свързани с бутони и конци, ще намерите в глава 11.
Да предположим, че някои полета са изрязани от шахматна дъска, така че да не могат да се поставят домино върху останалата част от нея. Лесно се проверява, че най-малкият брой изрязани полета с това свойство е 32 - това са всички полета от един и същи цвят (бели или черни).
Проблемите с шахматната дъска и доминото са само малка част от огромна поредица задачи от този вид. Американският математик С. Голомб създава цяла наука, която нарича полимипо, а книгата му на тази тема е преведена в много страни по света, включително и у нас. По принцип полиомино е просто свързана фигура, състояща се от квадрати. От гледна точка на шахматиста, простото свързване означава, че всички полета на полиомино могат да бъдат заобиколени с ход на топ. В зависимост от броя на квадратите 07, полиомино се предлагат в различни степени. Едно мономино съдържа едно квадратче, доминото две, тромино три, тетрамино четири, пентомино пет, хептомино шест квадрата и т.н. Ще се спрем на още няколко въпроса, свързани с обикновената шахматна дъска. Очевидно е невъзможно да се покрие dssk само с прави тромино, т.е. домино 3 × 1, тъй като 64 не се дели на 3. Възниква следният проблем.
Възможно ли е да се покрие шахматна дъска с 21 прави тромино и едно мономино? Ако е така, какви полета може да заема едно мономино?
Едно от необходимите dapo покрития на фиг. 4а. За да определим възможните подредби на мономино, начертаваме две системи от успоредни линии на дъската, както е показано на фиг. 4б.
Лесно е да се види, че за всяко покритие всяко тромино покрива точно едно поле, през което минава плътната линия, и точно едно, през което минава пунктираната линия. Тъй като броят на полетата, пресечени от плътни линии, е 22, както и броят на полетата, пресечени от пунктирани линии, и има 21 тромино, мономиното може да покрива само полета, пресечени от двете семейства линии. И има само четири такива квадрата: c3, c6, f3 и f6! Като завъртите дъската на 90, 180 и 270°, можете да получите подходящото покритие за всяко от тези четири полета.
Следващата задача е малко по-различна от обсъдените по-горе.
Възможно ли е да се покрие шахматна дъска с домино по такъв начин, че да е невъзможно да се начертае една граница между вертикали и хоризонтали, без да се пресичат домино?
Ако си представим, че дъската е стена, а доминото е тухла, тогава наличието на определената граница (шев) показва крехка зидария. С други думи, проблемът пита дали е възможно да се подредят „тухлите“ така, че „стената“ да не се срути. Правоъгълник, който може да бъде покрит по необходимия начин, се нарича "силен". "Силата" на шахматната дъска може да се види на фиг. 5. В общия случай Гарднър показва, че доминото може да се сгъне в "силен" правоъгълник, ако площта му е равномерна, а дължината и ширината му са по-големи от четири, като единственото изключение е квадрат 6 × 6.
По-долу често ще се занимаваме с правоъгълни шахматни дъски с един или друг размер. В този случай винаги се приема, че една m×n дъска има m вертикали и n хоризонтали (шах). Казваме, че дъската е "четна", ако броят на нейните полета е четен, и "нечетна" в противен случай. Където размерите на дъската не са посочени, имаме предвид стандартната шахматна дъска, за която m = n = 8.
Дъската 100x4 е покрита с домино. Докажете, че може да се разреже по една от границите между вертикали и хоризонтали, без да се засяга нито едно от доминото.
Всяка от зададените граници разделя дъската на две части, състоящи се от четен брой полета. Ние разделяме полетата на всяка част на два класа: покрити домино, разположени изцяло в тази част, и покрити домино, пресечени от границата. Тъй като броят на полетата на всяка част е четен (може би нула), както и броят на полетата от първи клас (всяко домино покрива две полета), броят на полетата от вторият клас е четен. А това означава, че броят на доминото, пресечени от границата, е четен. Има общо 102 разделителни граници (99 вертикални и 3 хоризонтални) и ако всяка от тях пресича домино, то в покритието участват поне 102 × 2 = 204 домино. Имаме само 200 от тях! Всъщност ние показахме, че правоъгълник 100x4 е "слаб".
Въпросът за възможността за покриване на произволна правоъгълна дъска с линейни k-мино (домино k × 1) се решава от следната теорема.
Една дъска m×n може да бъде покрита с линейни k-мино, ако и само ако поне едно от числата m или n се дели на k без остатък.
Ние илюстрираме теоремата със следния пример.
Възможно ли е да се покрие дъска 10x10 (на такава дъска се играят 100 квадратни пула) с прави тетрамино?
Едно право тетрамино е с размери 4x1, което означава, че по принцип 25 плочки могат да покрият всички полета на нашата дъска. От теоремата обаче следва, че това е невъзможно - 10 не се дели на 4.
Нека разгледаме още няколко задачи за шахматната дъска. При решението на следната задача viovb се използва неговото оцветяване.
Нека дъската се състои от нечетен брой полета. На всяко негово поле ще поставим по няколко фигура от шах. Възможно ли е да преместите всички тези фигури на съседни квадрати (вертикално или хоризонтално), така че нито една от тях да не се окаже на едно и също поле?
Задачата е непосилна. Наистина, ако посоченото разместване на фигурите съществуваше, тогава всяка "бяла" фигура (стояща на бяло поле) щеше да стане "черна" (попадна на черно поле), а всяка "черна" - "бяла".
Така дъската ще се състои от еднакъв брой бели и черни полета, а това противоречи на нейната "странност".
Популярни са задачите за рязане на шахматна дъска. Най-известният от тях е следният, собственост на С. Лойд.
Има четири коня на полетата a1, b2, c3, d4. Нарежете дъската на четири еднакви части (съвпадащи, когато са насложени), така че всяка от тях да има кон.
При проблеми с рязане винаги се приема, че срезовете се правят само по границите между вертикалите и хоризонталите на дъската. Решението на този проблем е показано на фиг. 6. От времето на Лойд се появиха много нови и по-трудни задачи по тази тема. По-специално, проблемите с разрязването на дъската на четири еднакви части бяха решени за различни позиции на рицарите (рицарите, разбира се, играят само символична роля тук). Все още има много нерешени проблеми по този въпрос. Например, все още не е известен броят на начините, по които една обикновена дъска (без парчета) може да бъде нарязана на две съвпадащи парчета.
Ориз. 6. Проблемът с четирите коня на Лойд |
Нека след няколко разфасовки на дъската, получените части могат да бъдат разместени, така че следващият разрез да може да изреже не една, а няколко части наведнъж. Колко разфасовки ще са необходими, за да се получат 64 отделни полета на дъската (1×1 квадратчета)?
Първо разрязваме дъската наполовина, след това поставяме двете половини една до друга и нарязваме дъската на четири еднакви части и т.н. Общо ще са необходими 6 разфасовки (2 e \u003d 64) и по-малък брой не може да се откаже .
Нека сега части от дъската могат да се режат само отделно. Колко разфасовки ще са необходими, за да се получат 64 полета в този случай?
По правило тази задача (особено ако е предложена след предишната) създава определени трудности. Очевидно това се дължи на някаква инерция на нашето мислене. В крайна сметка веднага става ясно, че ще са необходими 63 разфасовки! Наистина, всеки разрез увеличава броя на частите с една; в същото време в началния момент имаме една част (самата дъска), а в крайния момент - 64 (всички полета на дъската).
Ориз. 7. Три задачи на необичайна дъска |
В задачата на фиг. 7а, трябва да изпълните три задачи, една математическа и две чисто шахматни:
а) разрежете дъската на четири еднакви части;
б) матирайте черния цар по най-краткия път, когато белите се движат;
в) да матира черния цар по най-краткия път; докато черните се движат, верните играят кооперативно).
Решения: а) как се изрязва дъската, показана на фиг. 7b; б) когато белите се движат, мат се дава на 12-ия ход: 1-12. Be1-b4, Ke3-d3-c4, Be4-c2-b3, Kc4-c3, Bb4-d6, Bb3-d5, Kc3-c2, Bd6-c5, Bd5-c4, Bd6-b4мат (всички ходове на черния крал са принудителни и не се дават); в) при правилна игра след 1. ... Ke6-e7 матът е невъзможен, тъй като черният поп се крие на e8 - 2. Be1-b4+ Ke7-e8 и офицерът с тъмно поле е принуден да напусне диагонала a3 - e7 поради заплахата от застой. Въпреки това, ако черните играят кооперативно (помагайки на белите да матират), тогава целта се достига само с три хода:
1. … Ke6-d6
2. Ke3-d4 Ke6-e7
3. Be1-b4+ Ke7-e6
4. Мат Be4-d5.Редица полета на нашата дъска не се използват по време на чифтосване, но ако бяха изключени, нямаше да има проблем с изрязването на дъската.
Ориз. 8. Парадокс с разрязване на шахматната дъска: а) 8×8 = 64; б) 13×5 = 65 |
Помислете сега за един добре известен парадокс, свързан с изрязването на шахматната дъска. Разрязваме дъската на четири части, както е показано на фиг. 8, а (в този случай за нас е неизгодно да оцветяваме полетата му), а от получените части ще добавим правоъгълник (фиг. 8, б). Площта на дъската е 64, а площта на получения правоъгълник е 65. Така при разрязването на дъската отнякъде се появи едно допълнително поле!
Разрешението на парадокса е, че чертежите ни не са съвсем точни (умишлено начертахме дебели линии, за да скрием неточностите). При внимателно изграждане на чертежа на фиг. 8b вместо диагонала на правоъгълника ще се появи леко удължена фигура с форма на диамант със страни, които изглеждат почти слети. Площта на тази фигура просто ще бъде равна на "допълнителната" единица.
Известният популяризатор на математиката в началото на века Е. Игнатиев излезе с „метода на шахматната дъска“, който позволява извеждането на различни формули. Даваме два прости примера по тази тема.
Нека намерим сумата на първите n естествени числа, използвайки "метода на шахматната дъска". За да направите това, на дъската (n + 1) × n (на фиг. 9, a n = 8) оцветяваме всички полета на първия вертикал, всички полета на втория вертикал (с изключение на горния), трета вертикална (с изключение на двете горни) и т.н. г., накрая - долна поле n-товертикален. В резултат на това белите и черните полета на нашата дъска ще бъдат равни, а именно 1 + 2 + ... + n. Тъй като цялата дъска се състои от n (n + 1) полета, получаваме
2 (1 + 2 + … + n) = n (n + 1),
откъдето следва известната формула за сумата от аритметична прогресия:
1 + 2 + … + n = n(n + 1)/2.
Сега нека докажем следната формула:
8(1 + 2 + ... + n) + 1 = (2n + 1)².
За да направите това, вземете дъска (2n + 1) × (2n + 1) и оцветете редица нейни полета с черно, както е показано на фиг. 9, 6 (за случай n = 5). Очевидно всяка черна част съдържа (1 + 2 + ... + n) полета. Без да вземаме предвид централното поле, тук имаме четири еднакви бели и черни части. Необходимата формула следва от факта, че нашата дъска съдържа (2n + 1)² полета и се състои от централно поле и осем еднакви части (четири бели и четири черни - фиг. 9b).
При разгадаването на парадокса, както и при запознаването с „метода на шахматната дъска“, самата дъска може безопасно да бъде заменена с лист карирана хартия или маса. Има огромен брой проблеми с такива обекти, но тяхното подробно разглеждане би ни отдалечило твърде много от шаха.
В заключение на главата представяме едно старо доказателство на шахматната дъска... на Питагоровата теорема. Начертайте квадрат на дъската, както е показано на фиг. 10, а. Дъската е разделена на този квадрат и четири еднакви правоъгълни триъгълника. На фиг. 10, 6 виждаме същите четири триъгълника, както и два квадрата. И така, триъгълниците и в двата случая заемат една и съща площ. Следователно останалите части на дъската без триъгълници заемат същата площ, на фиг. 10,а - един квадрат, а на фиг. 10б - две. Тъй като големият квадрат е построен върху хипотенузата на правоъгълен триъгълник, а малките квадрати са върху неговите крака, то "Питагоровите панталони са равни във всички посоки"!
Разбира се, строго погледнато, нашите разсъждения не доказват Питагоровата теорема (изследван е само конкретен случай), а само я илюстрират. Но такова доказателство минава без използване на шахматна дъска - за всеки правоъгълен триъгълник можете да изберете квадрат, който се разбива по подобен начин.
Именно това решение е дадено в книгата на Т. Саати "Методи за целочислена оптимизация и свързани с тях екстремални проблеми" (М., "Мир", 1973 г.).
С. Голомб. Полиомино. М., Мир, 1974.
Доказано е от А. Сойфер в статията „Карирани дъски и полимипо” („Квант”, 1972, № 11); там са дадени и редица нови полиомино задачи.
Е. Игнатиев. В областта на изобретателността или аритметиката за всеки. Книга. 1 - 3. М. - Ст., Госиздат, 1923.
В този урок ще говорим за страниците за оцветяване и как те помагат за решаването на проблеми. Обмислете нестандартни проблеми с рязане и облицовка и начини за тяхното разрешаване.
Обобщение на урока "Рязане. Теселиране. Оцветяване."
Страници за оцветяване. рязане. Теселации.
Много учени обичат да решават проблеми от древни времена. Решения на много прости проблеми с рязане са намерени от древните гърци и китайци, но първият систематичен трактат по тази тема е написан от Абул-Веф, известният персийски астроном от 10 век, който е живял в Багдад. Геометрите сериозно се занимават с решаването на проблемите с разрязването на фигури на най-малък брой части и след това съставянето на една или друга нова фигура от тях едва в началото на 20 век. Един от основателите на този завладяващ клон на геометрията е известният съставител на пъзели Хенри Е. Дудени. Особено голям брой съществуващи фигури, които са били рекорди, са счупени от експерт в Австралийското патентно ведомство Хари Линдгрен. Той е водещ производител на фигури.
Днес любителите на пъзелите обичат да решават проблеми с рязане, преди всичко защото няма универсален метод за решаване на такива проблеми и всеки, който се заеме с тяхното решение, може напълно да демонстрира своята изобретателност, интуиция и способност за творческо мислене. Тъй като тук не се изискват задълбочени познания по геометрия, аматьорите понякога дори могат да надминат професионалните математици.
За да се докаже, че е възможно да се реши проблемът с разрязването на фигура на части, достатъчно е да се предостави някакъв метод на рязане. Намирането на всички решения, тоест всички начини на рязане, е малко по-трудно. И да се докаже, че рязането е невъзможно, вече е доста трудно. В някои случаи оцветяването на фигурата ни помага да направим това.
Задача 1:Взехме квадрат от карирана хартия с размери 8 × 8, отрязахме две клетки от него (долната лява и горната дясна). Възможно ли е да покриете напълно получената фигура с "домино" - 1 × 2 правоъгълника?
Задача 2.Възможно ли е да се подреди шахматна дъска с тридесет и две домино, така че 17 от тях да са хоризонтално и 15 вертикално?
Задача 3:Възможно ли е да изрежете квадрат от карирана хартия по размер
4×4 за един пиедестал, един квадрат, една колона и един зигзаг?
Задача 4:Възможно ли е да очертаете квадрат 8 × 8, като използвате 15 правоъгълника 1 × 4 и един ъгъл на изглед?
Задача 5:Възможно ли е да оформите правоъгълник 6×10 с правоъгълници 1×4?
Задача 6:Възможно ли е да сгънете квадрат 6 × 6, като използвате 11 правоъгълника 1 × 3 и един изгледен ъгъл?
Задача 7:На всяка клетка на дъската 5 × 5 има бръмбар. В даден момент всички бръмбари излитат и кацат върху съседни клетки отстрани. Докажете, че ще има поне един празна клетка.
Задача 8:Изрежете ъглова клетка от дъска 8×8. Могат ли останалите да бъдат нарязани на правоъгълници 3×1?
Задача 9:Фигурата камила се движи по шахматната дъска с ход като (1, 3). Възможно ли е да преместите „камилата“ от произволно поле в съседното?
Задача 10:Може ли дъска 10 × 10 да бъде покрита с фигури от формата ?
Задача 11:Дадена е дъска 12 × 12. В долния ляв ъгъл има 9 пула, образуващи квадрат 3 × 3. С един ход можете да изберете няколко пула и да пренаредите единия от тях симетрично спрямо другия (без да напускате дъската) . Възможно ли е да преместите тези пулове в няколко хода, така че да образуват квадрат 3 × 3 в долния десен ъгъл?
Задача 12:Във всяка клетка на квадрат 9 × 9 има бръмбар. По команда всеки бръмбар лети до една от диагонално съседните клетки. Докажете, че тогава поне 9 клетки ще бъдат свободни.
Задача 13:Замъкът има формата на правилен триъгълник, разделен на 25 малки зали с еднаква форма. Във всяка стена между залите е направена врата. Пътешественикът се разхожда из замъка, без да посещава някоя от залите повече от веднъж. Намерете най-големия брой зали, които може да посети. 
Задача 14:Какъв е максималният брой ромби, които могат да бъдат нарязани на равностранен триъгълник, разделен на 36 равностранни триъгълника?
Задача 15.Има 16 плочки 1x3 и една плочка 1x1 в квадрат 7x7. Докажете, че плочката 1×1 или лежи в центъра, или е в съседство с границите на квадрата.
Задача 16.В долния ляв ъгъл на шахматна дъска 8 × 8 са поставени девет жетона под формата на квадрат 3 × 3. Чип може да скочи до свободно поле през близък чип, тоест може да се отрази симетрично спрямо центъра си (можете да скочите вертикално, хоризонтално и диагонално). Възможно ли е за определен брой такива ходове да поставите всички чипове отново под формата на квадрат 3 × 3, но в различен ъгъл.
