کاشی کاری

نوع مقاله : ترجمه

نویسندگان

1 دانشگاه کاشان، دانشکده علوم ریاضی

2 دانشگاه فسا

چکیده

در این مقاله، مسئلۀ کاشی کاریِ یک ناحیه از صفحه را مطرح و پیشرفت هایی را که در زمینۀ حل این مسئلۀ صورت گرفته است، مرور می کنیم. از جمله، به این پرسش ها پاسخ می دهیم که آیا کاشی کاریِ یک ناحیه امکان پذیر است یا نه و اگر هست، به چند طریق. همچنین برخی نتایج دربارۀ کاشی کاری یک ناحیۀ کراندار با تعداد بی شمار کاشی را نیز بیان می کنیم.

کلیدواژه‌ها

موضوعات


‎Beauquier‎, ‎D.‎,   ‎Nivat‎, ‎M.‎,   ‎R\'{e}mila‎, ‎E.‎,   ‎Robson‎, ‎E.‎, ‎Tiling figures of the plane with two bars.‎, Comput‎. ‎Geom.           ‎, 5            (1995)‎, ‎1--25‎.
نویسندگان، کاشی‌کاری یک ناحیه توسط مستطیل‌های افقی
 ‎$n\times 1$‎ و عمودی ‎$1\times m$‎
  را بررسی می‌کنند. نتیجهٔ اصلی آنها این است که برای
  ‎$n\geq 2$‎ و ‎$m>2$‎،   این سؤال که آیا  چنین کاشی‌کاری‌ای موجود است، یک
  مسألهٔ ‎$NP$-‎کامل است. آنها  همچنین چندین حالت خاص از این مسأله را بررسی می‌کنند‎.‎
 
 
‎Brooks‎, ‎R.‎, ‎Smith‎,  ‎C.‎, ‎Stone‎,  ‎A.‎,  ‎Tutte‎, ‎W.‎, ‎The dissection of rectangles into squares‎. Duke Math‎. ‎J., 7 (1940)‎, ‎312–340‎.
  نویسندگان به هر کاشی‌کاری کامل از یک مستطیل، یک گراف معین و جریان الکتریکی گذرا از آن را نسبت می‌دهند و نشان می‌دهند که چگونه خواص کاشی‌کاری در شبکهٔ الکتریکی بازتاب می‌یابد. آنها از این دیدگاه در اثبات چندین نتیجه در مورد کاشی‌کاری کامل استفاده می‌کنند و روش‌های جدیدی نیز برای ساختن آنها ارائه می‌دهند
 
 
 ‎Conway‎, ‎J.‎, ‎Lagarias‎, ‎J.‎, ‎Tiling with polyominoes and combinatorial group theory‎, J‎. ‎Combin‎. ‎Theory Ser‎. ‎A           ‎, 53            (1990)‎, ‎183--208‎. نویسندگان وجود کاشی‌کاری با یک مجموعه‌ای متناهی از کاشی‌ها را برای یک ناحیه در یک مشبکهٔ منظم در ‎$\mathbb{R}^2$‎ مطالعه می‌کنند. آنها با بررسی راه‌هایی که مرزهای کاشی‌ها چنان با هم جفت شوند که مرز ناحیهٔ مورد بررسی به‌دست آید، یک شرط لازم برای وجود کاشی‌کاری از منظر نظریهٔ ترکیبیاتی گروه‌ها ارائه می‌دهند‎.           ‎
 
‎de Bruijn‎, ‎N.‎, ‎Filling boxes with bricks‎,  Amer‎. ‎Math‎. ‎Monthly           ‎,           76 (1969)‎, ‎37--40‎.
نویسنده به مطالعهٔ مسئلهٔ کاشی‌کاری یک جعبهٔ ‎$n$-‎بعدی با ابعاد صحیح ‎$A_1\times \cdots\times A_n$‎ توسط آجرهای با ابعاد صحیح ‎$a_1\times \cdots\times a_n$‎ می‌پردازد. نویسنده ثابت می‌کند که برای اینکه یک چنین کاشی‌کاری‌ای موجود باشد،  هر ‎$a_i$‎ باید دست‌کم یکی از ‎$A_1$‎، ‎$A_2$‎، ‎$\ldots$‎ ، ‎$A_n$‎ را عاد کند. یک جعبه ‎         مضربی           ‎ از یک آجر نامیده می‌شود اگر بتوان آن را به روش بدیهی کاشی‌کاری کرد. ثابت شده که اگر ‎$a_1|a_2$‎، ‎$a_2|a_3$‎، ‎$\ldots$‎ و ‎$a_{n-1}|a_n$‎، آن‌گاه با این آجر تنها می‌توان جعبه‌هایی را کاشی‌کاری کرد که مضرب آن هستند.  ثابت شده است که عکس این حکم نیز درست است‎.
 
  ‎Duijvestijn‎, ‎A.‎, ‎Simple perfect squared square of lowest order‎, J‎. ‎Combin‎. ‎Theory Ser‎. ‎B           ‎,           25            (1978)‎, ‎240--243‎.  یک کاشی‌کاری کامل یکتا برای یک مربع با کمترین تعداد ممکن مربع‌ها، ‎21‎، ارائه شده است‎.          
 
‎Elkies‎, ‎N.‎,   ‎Kuperberg‎, ‎G.‎, ‎Larsen M.‎, ‎Propp‎, ‎J.‎, ‎Alternating sign matrices and domino tilings (I and II)‎,             J‎. ‎Algebraic Combin.           ‎,           1            (1992)‎, ‎111--132‎, ‎219--234‎.
 نشان داده شده است که لوزی اَزتک از مرتبهٔ ‎$n$‎ دارای
 ‎$2^{\frac{n(n-1)}{2}}$‎تا کاشی‌کاری با استفاده از دومینو‌ها است. چهار اثبات برای این حکم  ارائه شده است؛ از جمله استفاده از رابطهٔ این مسئله با ماتریس‌های علامت-متناوب، مثلث‌های یکنوا و نظریهٔ نمایش ‎$GL(n)$‎.  همچنین ارتباط آن با مدل مربع-یخ لی‌یب هم توضیح داده شده است‎.          
 
 
  ‎Fisher‎, ‎M.‎,  ‎Temperley‎, ‎H.‎, ‎Dimer problem in statistical mechanics—an exact result‎,  Philosophical Magazine           ‎,           6            (1961)‎, ‎1061--1063‎.
 
  فرمولی برای تعداد کاشی‌کاری‌های یک مستطیل با استفاده از دومینو‌ها از منظر مکانیک آماری ارائه شده است. ‎          
 
 
  ‎Freiling C.‎,  ‎Rinne‎,  ‎D.‎, ‎Tiling a square with similar rectangles‎, Math‎. ‎Res‎. ‎Lett. ‎, 1 (1994)‎, ‎547--558‎.
  نویسندگان ثابت می‌کنند که یک مربع را می‌توان با کاشی‌های متشابه با کاشی ‎$1\times u$‎ کاشی‌کاری کرد اگر و تنها اگر ‎$u$‎ ریشهٔ یک چندجمله‌ای با ضرایب صحیح باشد به‌طوری که قسمت حقیقی همهٔ ریشه‌های این چندجمله‌ای، مثبت باشند.
 
 ‎Gr\"{u}nbaum‎, ‎B.‎,  ‎Shephard‎, ‎G.‎, Tilings and patterns. W‎. ‎H‎. ‎Freeman and Company‎, ‎New York‎, ‎1987‎.
 این کتاب گزارشی مفصل از مفاهیم گوناگون کاشی‌کاری با تکیه بر کاشی‌کاری صفحه توسط  مجموعه‌ای متناهی از کاشی‌ها، ارائه می‌دهد. برای مثال، نویسندگان انواع متعدد الگوهای کاشی‌کاری صفحه را دسته‌بندی می‌کنند. سایر موضوع‌های مورد بحث شامل کاشی‌کاری کامل مستطیل‌ها و کاشی‌کاری‌های نامتناوب صفحه است‎.          
 
 
‎Hall‎, ‎P.‎, ‎On representatives of subsets‎, J‎. ‎London Math‎. ‎Soc. ‎,           10 (1935)‎, ‎26--30‎.
 برای هر
 ‎$m$‎تا
  زیرمجموعهٔ ‎$T_1$‎، ‎$\ldots$‎، ‎$T_m$‎ از مجموعهٔ ‎$S$‎، هال یک دستگاه کامل نشانگرهای متمایز را   مجموعه‌ای از ‎$m$‎ عضو متمایز  ‎$a_1,\ldots‎, ‎a_m\in S$‎ تعریف می‌کند به‌طوری که برای هر ‎$i$‎، ‎$a_i\in T_i$‎. او ثابت می‌کند که  چنین دستگاهی موجود است اگر و تنها اگر برای هر ‎$k=1,2,\ldots‎, ‎m$‎، اجتماع
هر ‎$k$‎تا  از این مجموعه‌ها شامل دست‌کم ‎$k$‎ عضو باشد‎.‎
 
 
‎Jockusch‎, ‎W.‎,   ‎Propp‎, ‎J.‎,   ‎Shor‎, ‎P.‎, ‎Random domino tilings and the Arctic Circle theorem‎, ‎preprint‎, ‎1995‎, ‎arXiv:math‎. ‎CO/9801068‎.
 
 در کاشی‌کاری لوزی اَزتک با استفاده از دومینوها، لوزی به پنج ناحیه افراز می‌شود: چهار ناحیهٔ بیرونی نزدیک به گوشه‌ها که کاشی‌ها به‌صورت مرتب کنار هم قرار می‌گیرند و یک ناحیهٔ مرکزی که در آن، کاشی‌ها هیچ الگوی از پیش تعیین‌شده‌ای را دنبال نمی‌کنند. نویسندگان قضیهٔ قطب شمال را ثابت می‌کنند: در یک کاشی‌کاری تصادفی از یک لوزی اَزتک بزرگ، ناحیهٔ مرکزی بسیار شبیه به یک دایرهٔ کامل محاط در لوزی است‎.          
 
 
  ‎Kasteleyn‎, ‎P.‎, ‎The statistics of dimers on a lattice I‎. ‎The number of dimer arrangements on a quadratic lattice‎, Physica   ‎, 27            (1961)‎, ‎1209--1225‎.
  نویسنده فرمول‌های دقیق و  مجانبی برای تعداد کاشی‌کاری‌های یک مستطیلِ دارای لبه یا با شرایط مرزی متناوب را توسط دومینو‌ها ثابت می‌کند. سپس به بحث دربارۀ پیوند بین این مسأله و مدل آیزینگ برای مکانیک آماری می‌پردازد‎.          
 
 
‎Klarner‎,  ‎D.‎, ‎Packing a rectangle with congruent n-ominoes‎,  J‎. ‎Combin‎. ‎Theory ‎, 7 (1969)‎, ‎107--115‎.
 نویسنده به بررسی مسألهٔ کاشی‌کاری یک مستطیل با تعدادی فرد نسخه از یک پلیومینوی خاص می‌پردازد. او همچنین مستطیل‌هایی را که با نسخه‌هایی از یک مستطیل ‎$a\times b$‎ قابل کاشی‌کاری است و نیز  مستطیل‌هایی را که با نسخه‌هایی از یک اکتامینو قابل کاشی‌کاری است، مشخص می‌کند‎.          
 
 
‎Laczkovich‎, ‎M.‎, ‎Szekeres‎, ‎G.‎, ‎Tilings of the square with similar rectangles‎,             Discrete Comput‎. ‎Geom. ‎, 13            (1995)‎, ‎569--572‎.
نویسندگان ثابت می‌کنند که یک مربع را می‌توان با مستطیل‌های متشابه با یک مستطیل ‎$1\times u$‎ کاشی‌کاری کرد اگر و تنها اگر ‎$u$‎ ریشهٔ یک چندجمله‌ای با ضرایب صحیح باشد و قسمت حقیقی همهٔ ریشه‌های این چندجمله‌ای، مثبت باشد‎.          
 
 
  ‎Pak‎, ‎I.‎, ‎Tile invariants‎: ‎New horizons‎,             Theoret‎. ‎Comput‎. ‎Sci.           ‎, 303            (2003)‎, ‎303--331‎.   برای یک مجموعهٔ متناهی از کاشی‌ها نظیر ‎$T$‎، گروه ناورداها ‎$G(T)$‎، از روابط خطی تشکیل شده است که باید بین تعداد هر نوع کاشی در کاشی‌کاری‌های متفاوت از یک ناحیه برقرار باشد. این مقاله  آنچه را در مورد ‎$G(T)$‎ می‌دانیم،  دوره می‌کند. ثابت  می‌شود که این ناورداها، از استدلال‌های رنگ‌آمیزی کلاسیک قوی‌تر هستند
‎.          
 
‎Paulhus‎, ‎M.‎, ‎An algorithm for packing squares‎,             J‎. ‎Combin‎. ‎Theory Ser‎. ‎A           ‎,           82            (1998)‎, ‎147--157‎. ‎\begin{persian           ‎
              نویسنده الگوریتمی برای جاسازیِ یک مجموعهٔ نامتناهی از مستطیل‌هایی که پی‌در‌پی کوچک می‌شوند ولی   مجموع مساحت‌های آنها عدد ثابت  ‎$A$‎  است،
 در یک ناحیهٔ   مستطیلی با مساحت کمی بیش از ‎$A$‎ ارائه می‌کند. او الگوریتم خود را برای سه مسألهٔ معروف از این نوع به‌کار می‌برد و یک بسته‌بندی بسیار چفت به‌دست می‌آورد‎.
          
  ‎Propp‎, ‎J.‎, ‎Lattice structure for orientations of graphs‎, ‎preprint‎, ‎1994‎, ‎arXiv‎: ‎math/0209005‎. ‎
               در این مقاله، ثابت می‌شود که می‌توان به مجموعهٔ همهٔ جهت‌های یک گراف که تفاضل شار آنها حول همۀ مدارها یکسان است، یک ساختار مشبکهٔ توزیع‌پذیر نسبت داد. این موضوع، ساختار مشابه مربوط به ماتریس‌های علامت-متناوب و جورسازی‌ها را تعمیم می‌دهد
‎.          
 
 
‎Stein‎, ‎S.‎,  ‎Szab\'{o           ‎, ‎S.‎,             Algebra and tiling‎. ‎Homomorphisms in the service of geometry,            Mathematical Association of America‎, ‎Washington‎, ‎DC‎, ‎1994.
 
             این کتاب به بحث دربارۀ حل چند مسألهٔ کاشی‌کاری با استفاده از ابزارهای جبر پیشرفته می‌پردازد. دو نمونه از این مسائل عبارت‌اند از: یک مربع را نمی‌توان با مثلث‌های ‎$30^\circ-60^\circ-90^\circ$‎ کاشی‌کاری کرد. همچنین  مربعی را که   مساحت آن یک عدد صحیحی فرد است،  نمی‌توان با مثلث‌هایی با مساحت واحد، کاشی‌کاری کرد. ‎          
 
 
  ‎Thurston‎, ‎W.‎, ‎Conway’s tiling groups‎,             Amer‎. ‎Math‎. ‎Monthly           ‎,           97            (1990)‎, ‎757–773‎. ‎\begin{persian           ‎
               نویسنده به معرفی روش کانوی برای مطالعهٔ  مسائل کاشی‌کاری می‌پردازد. در برخی موارد می‌توان یال‌های کاشی‌ها را با اعضای یک گروه برچسب‌گذاری کرد به‌طوری ‌که یک ناحیه قابل کاشی‌کاری است اگر و تنها اگر حاصل‌ضرب برچسب‌های ظاهرشده روی مرز ناحیه، برابر با عضو همانی گروه شود. همچنین ایدهٔ           تابع ارتفاع            که کاشی‌کاری را به یک شکل سه‌بُعدی ارتقا می‌دهد، معرفی شده است. این روش‌ها در کاشی‌کاری با دومینوها، لوزی‌ها و تریبون‌ها به‌کار گرفته شده است‎.          
 
 
  ‎Wagon‎, ‎S.‎, ‎Fourteen proofs of a result about tiling a rectangle‎, Amer‎. ‎Math‎. ‎Monthly           ‎,           94            (1987)‎, ‎601–617‎. ‎
 
 
  نویسنده ‎14‎ اثبات برای این قضیه زیر ارائه می‌کند:          اگر یک مستطیل را بتوان  با مستطیل‌هایی که دست‌کم یک ضلع آنها عدد صحیح است،  کاشی‌کاری کرد، آن‌گاه مستطیل کاشی‌کاری‌شده نیز دست‌کم یک ضلع صحیح دارد