Степени двойки - раздел Образование, Мартин Гарднер «КОГДА ТЫ БЫЛА РЫБКОЙ, ГОЛОВАСТИКОМ – Я…» Рассмотрим Доску Второго Порядка. Ее Можно Покрыть, Какую Бы Клетку Мы Ни Уда...
Рассмотрим доску второго порядка. Ее можно покрыть, какую бы клетку мы ни удалили (см. рис. 2, слева). На рис. 2, справа, показано, как можно покрыть доску 4‑го порядка. Вырезанная клетка неизбежно оказывается в квадрате 2×2, в каком‑то из его четырех углов. Остальная часть доски покрывается благодаря приему, который Соломон Голомб окрестил rep‑tile («рептилия»): элемент покрытия (tile) как бы воспроизводит увеличенную копию (replica) самого себя. Левый верхний квадрат 2×2 можно поворачивать, чтобы недостающая клетка оказывалась в четырех разных местах, и весь квадрат 4‑го порядка можно при этом поворачивать так, чтобы эта клетка попадала на любое из его шестнадцати полей.
Рис. 2. Порядки 2 и 4
А 1953 году Голомб, «отец» полимино (он придумал для них название и первым начал изучать их), вывел индуктивное доказательство, продемонстрировав, что все доски со сторонами, отвечающими прогрессии 2, 4, 8, 16…) можно покрыть с помощью тримино, когда отсутствует произвольная клетка доски. Впервые доказательство было опубликовано в 1938 году[73]. Позже его повторил Э.Б. Эскотт (см. статью в журнале «Open Court»[74]). С тех пор математики включают это доказательство в свои книги, часто без ссылки на Голомба. Роджер Нельсен приводит Голомбово доказательство в виде единственной диаграммы, без всяких словесных пояснений[75]. Знаменитое доказательство Голомба начинается с рассмотрения квадрата 2×2 (рис. 3, слева). Этот квадрат затем помещается в угол квадрата 4–го порядка (рис. 3, в центре). А уже этот квадрат 4×4 располагается в углу квадрата 8‑го порядка (рис. 3, справа), после чего рядом с углом зачерненного квадрата 4‑го порядка укладывают одно тримино. Мы уже знаем, что зачерненный квадрат можно покрыть при отсутствии в нем любой клетки, и мы знаем, что три незачерненных области (примыкающих к нашему одиночному тримино) можно покрыть с помощью тримино, так как в каждой из них отсутствует одна клетка (угловая). Поворачивая доску[76], можно добиться того, чтобы любая клетка в зачерненном квадрате приходилась на любое место доски 8‑го порядка.
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Степени двойки
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Энн Коултер бросает вызов Дарвину
Энн Коултер заработала целое состояние, сочиняя книги, смертельно оскорбляющие либералов, а также защищая свои ультраконсервативные взгляды в телевизионных ток‑шоу и гастро
Исаак Ньютон и его безбрежный океан истины
Профессиональный путь Ньютона впечатляет по двум причинам: благодаря его ошеломительным открытиям в области математики и физики – и столь же ошеломляющей глупости его теологии. М
Выстрелы в яблочко и знаменитые промахи
Почти десять лет я вел раздел загадок в «Isaac Asimov's Science Fiction Magazine» («Азимовском научно‑фантастическом журнале»). Данная глава – перепечатка моей колонки за д
Почему я не сторонник паранормального
Когда выдающийся ученый Карл Саган на заседании Американской ассоциации содействия развитию науки атаковал дикие, невежественные воззрения Иммануила Великовского, ему учинили раз
Новое мышление», «Единство» и Элла Уилер‑Уилкокс
В наши дни Эллу Уилер‑Уилкокс практически забыли, если не считать нескольких стихотворных строк, которые часто цитируют, не зная имени автора. А ведь при жизни эта женщина
Была ли предсказана гибель «Титаника»?
Покойный Йен Стивенсон (он умер в 2006 году) горячо верил в парапсихологические силы и реинкарнацию, а потому был убежден, что морская повесть Моргана Робертсона «Тщета, или Круш
Дракула готовит мартини
Эта глава открывается классической головоломкой; далее показано, как на ее основе проделать два таинственных карточных фокуса. В наше время существует обширнейшая литература по м
Постскриптум
Сотни математических карточных фокусов используют, по сути, тот же принцип. Вот хороший пример, можете испробовать его на приятелях.
Перед тем как показать трюк, разделите стандартную коло
Ряд Фибоначчи
Классический ряд Фибоначчи начинается так: 1, 1, 2, 3, 5, 8, 13, 21… Каждый член последовательности (кроме первых двух) – сумма двух предыдущих. Обобщенный случай ряда Фиб
Порядки 5 и 7
Далее нас ждет доска 5‑го порядка, поскольку 5 – следующее число в последовательности (1), для которого мы пока не вывели доказательства. Если убрать центральную клетку, полученную фигуру мож
Выше 7‑го порядка
Индуктивное доказательство Голомба применимо к бесконечному числу рядов, чьи элементы удваиваются. В частности, после того как мы успешно покрыли доску 7×7, можно понять, как покрываются доск
ПОЛНЫЙ И УНИВЕРСАЛЬНЫЙ РЕЗУЛЬТАТ
Занимаясь разбиением этих фигур, я подобрался (но пока недостаточно близко) к тому, чтобы вывести индуктивное доказательство того, что все дефицитные квадраты покрываемы, за исключением квадрата 5&
Ay, мистер Херш, вы «здесь»?
Рубен Херш принадлежит к небольшой группе математиков, убежденных, что математика реальна лишь в контексте человеческой цивилизации. А я – бесстыжий платоник и предпочитаю иной я
Взрыв Оракула Бреддиджа
Когда предсказание само является частью предсказываемого события, могут возникать всякого рода логические парадоксы. Я несколько раз писал о таком явлении. Текст этой главы был в
Казнь Филберта‑Фальсификатора
Логический парадокс, представленный в этой главе, называли «парадоксом неожиданного допроса»: так его именовал Д.Дж. О'Коннор, впервые описавший его в своей статье «Практические
Лэнгдон Смит
Эволюция
I
Когда ты была рыбкой, головастиком – я,
там, в палеозойской мгле,
мы, рядом поплыв сквозь суровый отлив,
Постскриптум
Насколько я знаю, моя дань памяти Смиту осталась единственной статьей, когда‑либо написанной о нем или о его поэме. Я планировал выпустить целый цикл очерков об «авторах одного стихотворения»
Занимательный случай Фрэнка Типлера
Трудно поверить, что Фрэнк Дженнингс Типлер действительно существует. Это весьма уважаемый физик, он работает в Университете Тулейна[112]и является автором многи
Комический номер: падение Ричарда Робертса
Я родом из Талсы[114], я там вырос, и меня долго зачаровывали и забавляли ужимки Оурала Робертса и его милого сыночка‑певчего по имени Ричард. Как и многие
Почему я не атеист
В наши дни активно раскупается масса книг, рьяно защищающих атеизм; этот список возглавляет «Бог как иллюзия» Ричарда Докинза. Поэтому я поддался искушению и решил было написать
Социализм» – бранное слово?
Уже давно я с большим удовольствием пишу письма в редакции, хоть и знаю, что из них мало что опубликуют. Вот почему я обрадовался, когда одна утренняя газета оклахомского городка
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов