Tardos Jakab megoldása. A legkisebb megfelelő $k$ a 2013. Nem lehet 2013-nál kisebb, mivel létezik olyan kolumbiai alakzat, amelyet nem lehet 2013-nál kevesebb egyenessel jól felbontani.
Vegyünk egy szabályos 4027-szöget. A sokszög csúcsait színezzük felváltva kékre és pirosra úgy, hogy egy helyen két szomszédos csúcs kék színű legyen. Ekkor a 4027-szög csúcsai egy kolumbiai alakzatot alkotnak. A 4027-szögnek pontosan 4026 olyan oldala van, amelyeket egy piros és egy kék pont határol. Ha ezt az alakzatot egyenesekkel jól felbontjuk, minden ilyen oldalt el kell metszenie legalább egy egyenesnek. Ha a 4026 oldal közül lenne egy, amelyet egy egyenes sem metsz el, akkor az ezt határoló két különböző színű csúcs egy tartományba esne. Mivel a szabályos 4027-szög konvex alakzat, minden egyenes legfeljebb kétszer metszheti; ahhoz, hogy 4026 helyen el legyen metszve, legalább 2013 egyenes kell.
Igaz, hogy 2013 egyenes minden kolumbiai alakzat jó felbontásához elég.
Lemma. Bármely két pontot el lehet választani az alakzat többi pontjától két egyenes felhasználásával. Legyen a két pont $A$ és $B$. Legyen az $AB$ egyeneshez legközelebbi pont ($A$-n és $B$-n kívül) $C$. Ha $C$ és $AB$ távolsága $x$ (ahol $x$ pozitív, mivel az $AB$ egyenes nem tartalmazhat harmadik pontot), akkor a két $AB$-vel párhuzamos, tőle $x/2$ távolságra lévő egyenest behúzva valóban elválasztottuk $A$-t és $B$-t az alakzat többi pontjáról.
Ha egy kolumbiai alakzat konvex burka tartalmaz piros pontot, a következőképpen lehet 2013 egyenessel jól felbontani:
A konvex burokban lévő piros pontot elválasztjuk az alakzat többi pontjától egy egyenessel. A maradék 2012 piros pontot 1006 párba állítjuk, majd a párokat elválasztjuk az alakzat többi pontjától, a lemma szerint, 2012 egyenes felhasználásával. Így egy 2013 egyenesből álló jó felbontást alkottunk.
Ha egy kolumbiai alakzat konvex burka nem tartalmaz piros pontot, a következőképpen lehet 2013 egyenessel jól felbontani:
A konvex burok két szomszédos kék pontját egy egyenessel leválaszthatjuk. A maradék 2012 kék pontot 1006 párba állítjuk, majd a párokat elválasztjuk az alakzat többi pontjától, a lemma szerint, 2012 egyenessel. Így ismét egy 2013 egyenesből álló jó felbontást alkottunk, tehát minden kolumbiai alakzatot jól fel lehet bontani 2013 egyenessel.
A legkisebb megfelelő tulajdonságú $k$ valóban a 2013.