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