2
Minimalna ilość kolorów zapobiegająca równobocznemu jednokolorowemu podtrószkowi
W Bundeswettberweb Infomatik 2010/2011 pojawił się interesujący problem: Dla stałej znajdź minimalne i mapę , tak że nie ma potrójnego z .nnnkkkφ:{(i,j)|i≤j≤n}→{1,…,k}φ:{(i,j)|i≤j≤n}→{1,…,k}\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}(i,j),(i+l,j),(i+l,j+l)(i,j),(i+l,j),(i+l,j+l)(i,j),(i+l,j),(i+l,j+l)φ(i,j)=φ(i+l,j)=φ(i+l,j+l)φ(i,j)=φ(i+l,j)=φ(i+l,j+l)\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l) Mianowicie szukamy minimalnej ilości kolorów dla trójkąta, tak aby nie było równomiernego podtekstu równobocznego (poniższy rysunek pokazuje nieprawidłowe zabarwienie, ponieważ podświetlone wierzchołki tworzą …