Теорема Кавасаки
Теорема Кавасаки или теорема Кавасаки-Джастина — это теорема математическая складывания бумаги , которая описывает узоры складок с одной вершиной , которую можно сложить, образуя плоскую фигуру. Он утверждает, что шаблон является складным в том и только в том случае, если поочередное сложение и вычитание углов последовательных складок вокруг вершины дает попеременную сумму, равную нулю. Шаблоны складок с более чем одной вершиной не подчиняются такому простому критерию, и их NP-трудно сложить.
Теорема названа в честь одного из ее первооткрывателей, Тошиказу Кавасаки . Однако несколько других также внесли свой вклад в его открытие, и его иногда называют теоремой Кавасаки-Джюстина или теоремой Хусими в честь других авторов, Жака Жюстена и Коди Хусими . [ 1 ]
Заявление
[ редактировать ]с одной вершиной Узор сгиба состоит из набора лучей или складок, нарисованных на плоском листе бумаги, исходящих из одной и той же точки внутри листа. (Эта точка называется вершиной узора.) Каждая складка должна быть сложена, но в узоре не указано, должны ли складки быть горными складками или складками долины . Цель — определить, можно ли сложить бумагу так, чтобы каждая складка была загнута, в других местах не возникло никаких складок и весь сложенный лист бумаги лежал ровно. [ 2 ]
Чтобы сложить ровно, количество складок должно быть четным. Это следует, например, из теоремы Маекавы , которая утверждает, что число складок горы в плоскоскладчатой вершине отличается от количества складок долины ровно в два раза. [ 3 ] Поэтому предположим, что рисунок складок состоит из четного числа 2 n складок , и пусть α 1 , α 2 , ⋯, α 2 n — последовательные углы между складками вокруг вершины в порядке по часовой стрелке, начиная с любого из углы. Тогда теорема Кавасаки утверждает, что рисунок складки можно сложить ровно тогда и только тогда, когда попеременная сумма и разность углов в сумме равна нулю:
- α 1 - α 2 + α 3 - ⋯ + α 2 n - 1 - α 2 n знак равно 0
Эквивалентный способ формулировки того же условия состоит в том, что если углы разделены на два чередующихся подмножества, то сумма углов в любом из двух подмножеств равна точно 180 градусов. [ 4 ] Однако эта эквивалентная форма применима только к узору складок на плоском листе бумаги, тогда как форма попеременной суммы условия остается справедливой для узоров складок на конических листах бумаги с ненулевым дефектом в вершине. [ 2 ]
Локальная и глобальная плоская складность
[ редактировать ]Теорема Кавасаки, примененная к каждой вершине произвольного узора складок, определяет, является ли узор складок локально складным , то есть часть узора складок рядом с вершиной может быть сложена плоско. Однако существуют узоры складок, которые локально складываются в плоскую форму, но не имеют глобальной плоской складки, которая работает сразу для всего рисунка складок. [ 3 ] Том Халл ( 1994 ) предположил, что глобальную плоскую складчатость можно проверить, проверив теорему Кавасаки в каждой вершине узора складок, а затем также проверив двудольность связанного неориентированного графа, с узором складок. [ 5 ] Однако эта гипотеза была опровергнута Берном и Хейсом (1996) , которые показали, что условия Халла недостаточны. Более убедительно Берн и Хейс показали, что проблема проверки глобальной плоской сворачиваемости является NP-полной . [ 6 ]
Доказательство
[ редактировать ]Чтобы показать, что условие Кавасаки обязательно выполняется для любой плоско сложенной фигуры, достаточно заметить, что при каждом сгибе ориентация бумаги меняется на обратную. Таким образом, если первая складка в сложенной плоской фигуре расположена в плоскости, параллельной оси x , следующая складка должна быть повернута от нее на угол α 1 , последующая складка на угол α 1 − α 2 (поскольку второй угол имеет обратную ориентацию по отношению к первому) и т. д. Чтобы бумага снова встретилась сама с собой под конечным углом, должно выполняться условие Кавасаки. [ 3 ] [ 4 ] [ 7 ] [ 8 ]
Чтобы показать, что это условие также является достаточным условием, нужно описать, как сложить заданный рисунок складок так, чтобы он сложился ровно. То есть надо показать, как выбрать, делать складки горой или долиной и в каком порядке следует располагать лоскуты бумаги друг на друге. Один из способов сделать это — выбрать число i такое, что частичная знакопеременная сумма
- α 1 - α 2 + α 3 - ⋯ + α 2 я - 1 - α 2 я
как можно меньше. Либо i = 0 , и частичная сумма является пустой суммой , которая также равна нулю, либо для некоторого ненулевого выбора i частичная сумма отрицательна. Затем сложите выкройку гармошкой, начиная с угла α 2 i + 1 и чередуя складки горы и долины, располагая каждый угловой клин бумаги ниже предыдущих складок. На каждом этапе до последней складки складка гармошкой этого типа никогда не будет самопересекаться. Выбор i гарантирует, что первый клин будет торчать слева от всех остальных сложенных листов бумаги, позволяя последнему клину снова соединиться с ним. [ 5 ]
Альтернативное доказательство достаточности можно использовать, чтобы показать, что существует много различных плоских складок. Рассмотрим наименьший угол α i и две складки по обе стороны от него. Сложите одну из этих двух складок горой, а другую — долиной, произвольно выбирая, какую складку использовать для какой складки. Затем приклейте получившийся лоскут бумаги на оставшуюся часть шаблона складок. Результатом этого склеивания будет образец сгиба с двумя складками меньше на коническом листе бумаги, который по-прежнему удовлетворяет условию Кавасаки. Следовательно, по математической индукции повторение этого процесса в конечном итоге приведет к плоскому складыванию. Базовым случаем индукции является конус только с двумя складками и двумя клиньями с равными углами, которые, очевидно, можно сложить плоско, используя горную складку для обеих складок. Есть два способа выбрать, какие складки использовать на каждом этапе этого метода, и каждый шаг устраняет две складки. Следовательно, любой рисунок складки с 2 n складками, удовлетворяющий условию Кавасаки, имеет по крайней мере 2 н различные варианты сгиба гор и долин, которые все приводят к действительным плоским складкам. [ 9 ]
История
[ редактировать ]В конце 1970-х годов Коди Хусими и Дэвид А. Хаффман независимо друг от друга заметили, что сложенные плоско сложенные фигуры с четырьмя складками имеют противоположные углы, добавляющие к π , частному случаю теоремы Кавасаки. [ 10 ] [ 11 ] Хаффман включил результат в статью 1976 года о изогнутых складках. [ 12 ] и Хусими опубликовал теорему о четырех складках в книге по геометрии оригами вместе со своей женой Мицуэ Хусими. [ 13 ] Тот же результат был опубликован еще раньше, в паре статей С. Мураты 1966 года, которые также включали случай шести складок и общий случай теоремы Маекавы . [ 14 ]
Тот факт, что узоры складок с произвольным количеством складок обязательно имеют чередующиеся суммы углов, прибавляемые к π, был открыт Кавасаки, Стюартом Робертсоном и Жаком Джастином (опять же, независимо друг от друга) в конце 1970-х и начале 1980-х годов. [ 6 ] [ 10 ] [ 15 ] [ 16 ] [ 17 ] [ 18 ] Из-за вклада Джастина в эту проблему теорему Кавасаки также назвали теоремой Кавасаки – Джастина. [ 19 ] Тот факт, что это условие является достаточным, то есть что узоры складок с четным числом углов, поочередно суммирующиеся до π , всегда могут быть сложены в плоскую форму, возможно, был впервые установлен Халлом (1994) . [ 5 ]
Сам Кавасаки назвал результат теоремой Хусими в честь Коди Хусими, и некоторые другие авторы также следовали этой терминологии. [ 7 ] [ 20 ] Название «теорема Кавасаки» было впервые дано этому результату в книге «Оригами для знатока» Кунихико Касахара и Тоши Такахама (Japan Publications, 1987). [ 3 ]
Халл (2003) считает нижнюю границу 2 н о количестве различных плоских складок рисунка складок, отвечающих условиям теоремы, к независимой работе Азумы в начале 1990-х годов, [ 21 ] Джастин, [ 17 ] и Юинс и Халл. [ 9 ]
Хотя теорема Кавасаки полностью описывает модели сворачивания, имеющие плоскосвернутые состояния, она не описывает процесс сворачивания, необходимый для достижения этого состояния. Для некоторых (многовершинных) схем складывания необходимо изогнуть или согнуть бумагу, преобразуя ее из плоского листа в плоско сложенное состояние, вместо того, чтобы оставлять остальную часть бумаги плоской и изменять только двугранные углы на каждом из них. складывать. Для жесткого оригами (типа складывания, при котором поверхность остается плоской, за исключением складок, подходящей для шарнирных панелей из жесткого материала, а не из гибкой бумаги) условие теоремы Кавасаки оказывается достаточным для перемещения рисунка сгиба с одной вершиной. из развернутого состояния в плоско сложенное. [ 22 ]
Ссылки
[ редактировать ]- ↑ Имя «Ясудзи Хусими», появляющееся в Кавасаки (2005) и иногда связанное с этой теоремой, представляет собой неправильное прочтение кандзи «康治» в имени Коди Хусими.
- ^ Перейти обратно: а б Халл, Том (2002), «Комбинаторика плоских складок: обзор» , Оригами 3 : Третья международная встреча по науке, математике и образованию оригами , AK Peters, стр. 29–38, arXiv : 1307.1065 , Bibcode : 2013arXiv1307.1065H , ISBN 978-1-56881-181-9 .
- ^ Перейти обратно: а б с д Халл, Том , Массачусетс 323A Комбинаторная геометрия!: Заметки о плоском складывании , получено 12 апреля 2011 г.
- ^ Перейти обратно: а б Альсина, Клауди; Нельсен, Роджер (2010), Очаровательные доказательства: путешествие в элегантную математику , Dolciani Mathematical Expositions, vol. 42, Математическая ассоциация Америки , с. 57, ISBN 978-0-88385-348-1 .
- ^ Перейти обратно: а б с Халл, Том (1994), «О математике плоского оригами» (PDF) , Numerical Congress , 100 : 215–224 .
- ^ Перейти обратно: а б Берн, Маршалл; Хейс, Барри (1996), «Сложность плоского оригами», Учеб. 7-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '96) , стр. 175–183, ISBN 9780898713664 .
- ^ Перейти обратно: а б Кавасаки, Тошикадзу (2005), Розы, оригами и математика , Japan Publications Trading, стр. 139, ISBN 978-4-88996-184-3 .
- ^ Демейн, Эрик (осень 2010 г.), «15 сентября: Шаблоны сгиба с одной вершиной» , Примечания к курсу 6.849: Алгоритмы геометрического складывания: связи, оригами, многогранники , Массачусетский технологический институт , получено 13 апреля 2011 г.
- ^ Перейти обратно: а б Халл, Томас (2003), «Подсчет соотнесения гор и долин для плоских складок» (PDF) , Ars Combinatoria , 67 : 175–187, MR 1973236 .
- ^ Перейти обратно: а б Халл, Том (осень 2010 г.), «Пересмотр и расширение теорем Маекавы и Кавасаки» , гостевая лекция, 6.849 , Массачусетский технологический институт .
- ^ Вертхайм, Маргарет (22 июня 2004 г.), «Конусы, кривые, ракушки, башни: он оживил бумажный прыжок» , New York Times .
- ^ Хаффман, Дэвид А. (1976), «Искривление и складки: учебник для начинающих», IEEE Transactions on Computers , C-25 (10): 1010–1019, doi : 10.1109/TC.1976.1674542 , S2CID 17965418 .
- ^ Хусими, К .; Хусими, М. (1979), Геометрия оригами (на японском языке), Токио: Нихон Хёронша . 2-е изд., 1984 г., ISBN 978-4535781399 .
- ^ Мурата, С. (1966), «Теория бумажной скульптуры, I», Бюллетень Младшего художественного колледжа (на японском языке), 4 : 61–66 ; Мурата, С. (1966), «Теория бумажной скульптуры, II», Бюллетень Младшего художественного колледжа (на японском языке), 5 : 29–37 .
- ^ Робертсон, С.А. (1977), «Изометрическое сворачивание римановых многообразий», Труды Эдинбургского королевского общества , Раздел A: Математика, 79 (3–4): 275–284, doi : 10.1017/s0308210500019788 , MR 0487893 , S2CID 122398261 .
- ^ Джастин Дж. (июнь 1986 г.), «Математика оригами, часть 9», British Origami : 30 . Цитируется в заметках Халла MA 323A.
- ^ Перейти обратно: а б Джастин, Дж. (1994), «На пути к математической теории оригами», 2-й Межд. Встреча науки оригами , Оцу, Япония.
{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) . Цитируется Берном и Хейсом (1996) . - ^ Кавасаки Т. (1989), «О связи между горными складками и складками долины плоского оригами», в Хузита, Х. (редактор), « Наука и технология оригами» , стр. 229–237 . Цитируется Берном и Хейсом (1996) .
- ^ О'Рурк, Джозеф (2011), «4.5 Теорема Кавасаки – Джастина», Как ее сложить: математика связей, оригами и многогранников , Cambridge University Press, стр. 66–68 .
- ^ Кайно, К. (2007), «Четырехмерная геометрия и складной правильный тетраэдр», Фудзита, Сигэдзи; Обата, Цунэхиро; Судзуки, Акира (ред.), Статистическая и физика конденсированного состояния: за горизонтом , Nova Publishers, стр. 101–112 [102], ISBN 978-1-60021-758-6 .
- ^ Азума, Х. (1994), «Некоторые математические наблюдения о плоских складках», 2nd Int. Встреча науки оригами , Оцу, Япония.
{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) . Цитируется Халлом (2003). - ^ Авель, Закари; Кантарелла, Джейсон; Демейн, Эрик Д .; Эппштейн, Дэвид ; Халл, Томас С .; Ку, Джейсон С.; Ланг, Роберт Дж .; Тачи, Томохиро (2016), «Жесткие вершины оригами: условия и принудительные множества», Журнал вычислительной геометрии , 7 (1): 171–184, doi : 10.20382/jocg.v7i1a9 , MR 3491092 , S2CID 1977 .