Problem E: Combinatorial Topology
It was long believed that a 2-dimensional place can not be filled with a finite
set of polygons in aperiodic way. British mathematician, Sir Roger Penrose,
developed an aperiodic tiling over the years and
established a theory of what is known today as quasicrystals.
平面を非周期的な有限個の多角形で埋めることは出来ないと、長い間信じられてきた。
イギリス人数学者のロジャー・ペンローズは非周期充填を発見し、現在は準結晶として知られているものに関する理論を公表した。
The classic Penrose tiles consist of two rhombi with angles 36 and 72 degrees,
see Figure 1. The edges of the rhombi are all of equal unit length, 1. These
can fill the entire place without holes and overlaps (see Figure 2). Example:
the bold line boundary in Figure 1 is filled with 20 thin tiles and 20 thick
tiles.
古典的なペンローズ・タイルは図1のように「鋭角72度の菱形」と「鋭角36度の菱形」で構成されている。
菱形の辺の長さは全て1である。
Given a boundary (set of adjacent vertices counter-clock-wise oriented), how
many thin tiles (36 degrees) and how many thick tiles (72 degrees) do you need
to fill it (without any holes and intersections)?
2-dimensional 二次元
finite 有限
finite set 有限の要素をもつ集合
aperiodic 非周期的な
quasicrystals 準結晶
Penrose tiles ペンローズ・タイル
めも
平面充填
とりあえず平面にパズルのように当てはめていけば一意に定まる気がする。
隣り合う辺の角度から不可能かどうかを最初に判定する
ついでに辺の長さが整数じゃない場合も明らかに不可能
後は貪欲にタイルを敷き、埋まらなくなったら終了
多角形をタイルを敷く度に再構成するイメージ
