# 9eB1 comments on Open thread, March 13 - March 19, 2017

• You can come ar­bi­trar­ily close by choos­ing any tiling shape and mak­ing it as small as nec­es­sary.

• No, be­cause the de­gree of failure of the tiling is judged against the area of the cov­er­ing shape.

• This is one of the more con­fus­ing prob­lem state­ments, but I think I un­der­stand. So if we choose a reg­u­lar hexagon with height = 0.5, as in this link, the scor­ing for this solu­tion would be ((area of tri­an­gle—area of hexagon) + (area of square − 3 * area of hexagon)) /​ area of hexagon?

edit: Gur orfg fby­hgvba V pb­hyq pbzr hc jvgu jnf whfg gur n ev­tug gev­natyr gung’f unys gur nern bs gur rd­hvyn­greny gev­natyr. Lbh pna svg 4 va gur fdhner naq gjb va gur gev­natyr, naq gur fp­ber vf cb­vag fvk. V bayl gevrq n un­aqshy bs erthyne gvy­vatf gub­htu.

• I can beat your solu­tion and get a score of 0.433....

Gnxr gur pbire­vat funcr gb or gur jubyr fdhner naq pbz­cyr­gryl snvy gb pbire gur gev­natyr.

:-P

EDIT: Va snpg, jul abg trg n ernyyl tbbq fp­ber ol gnx­vat n pbz­cyr­gryl tvt­nagvp funcr gung qbrfa’g pbire nalgu­vat.

• Yes, well … If the shape is gi­gan­tic and there­fore doesn’t cover any­thing … this is a cun­ning solu­tion, but in a sense triv­ial.

A non-triv­ial solu­tion would be (even) bet­ter. ;)

• Okay, here’s a non-triv­ial an­swer. I be­lieve I can get ar­bi­trar­ily close to a score of 1/​sqrt(3) = 0.57735… .

Pick any nat­u­ral num­ber n, and let x = sqrt(3)/​2. Us­ing the the­ory of con­tinued frac­tions one can find nat­u­ral num­bers p and q such that q > n and x < p/​q < x + 1/​(4sqrt(3)q^2). Now let our cov­er­ing shape be a right an­gled tri­an­gle with sides 1/​(2p) and x/​p. The area is x/​(4p^2). Clearly 2p^2 such tri­an­gles can cover the equilat­eral tri­an­gle ex­actly.

Now con­sider how many we can fit in the square. By us­ing two of our cov­er­ing tri­an­gle we can make a rec­t­an­gle of sides 1/​(2p) and x/​p. By ar­rang­ing such rec­t­an­gles in a 2p by q grid we can perfectly tile a big rec­t­an­gle with sides 1 and qx/​p. Since x < p/​q we have qx/​p < 1, so this rec­t­an­gle fits into the square.

The re­main­ing area is 1 - qx/​p, and since p/​q < x + 1/​(4sqrt(3)q^2) we have that this area is less than 1/​(4sqrt(3)pq). Com­par­ing this to the area of our cov­er­ing tri­an­gle we find that our score is at most (p/​q)(1/​x)(1/​sqrt(3)) which is less than (x + 1/​(4sqrt(3)q^2))(1/​x)(1/​sqrt(3)) which is less than (1+1/​(4sqrt(3)xn^2))(1/​sqrt(3)). Since n was ar­bi­trary this can come ar­bi­trar­ily close to a score of 1/​sqrt(3).

EDIT: I made a pic­ture of the tiling of the square when p=13, q=15. The un­cov­ered area is the tiny red line at the top. The score is 0.57756… .

• I will pub­lish my solu­tion next Mon­day.

• I’m in­ter­ested to see your solu­tion.

• I will pre­sent my (com­puter gen­er­ated) solu­tions ASAP. Cur­rently they are still evolv­ing.

• Liter­ally evolv­ing? are you run­ning a ge­netic al­gorithm?

• It is ev­ery­thing I can do. Digi­tal evolu­tion.

I wouldn’t call that ge­netic al­gorithm, there are some differ­ences. For ex­am­ple, I evolve code, which fur­ther evolves some code, which evolves a prob­lem solu­tions of a prob­lem. May be sev­eral lay­ers be­tween the first code and the fi­nal solu­tion.

• I can im­prove my score to (620sqrt(3)-973)/​191 = 0.528… us­ing this ar­range­ment.

EDIT: This ar­range­ment does even bet­ter with a score of (19328sqrt(3)-30613)/​6143 = 0.466… . Note that there is a tiny cor­ner cut off each trapez­ium.

• In­ter­est­ing. We will see where this is go­ing to go.

• Any luck? I’d be in­ter­ested in see­ing some of the com­puter solu­tions even if their scores didn’t beat mine.

By the way I can now im­prove my score to 14sqrt(3)-24 = 0.249… . My cov­er­ing shape is a 14 by 17 right-an­gled tri­an­gle. This clearly tiles the square perfectly and you can also fit 24 of them into the equilat­eral tri­an­gle. To see this first di­vide the equilat­eral tri­an­gle ex­actly into 24 right-an­gled tri­an­gles of sides 14 and 1/​(4sqrt(3)), and then note that 17 < 1/​(4sqrt(3)). There’s no point in draw­ing a pic­ture since you can barely see the gaps.

• The cheaty solu­tion at the end de­pends on what seems to me an un­in­tended in­ter­pre­ta­tion of the ques­tion (though, given that the same per­son wrote the ques­tion and the pro­gram that found the solu­tion, maybe my idea of what’s in­tended is wrong). I took “tile both poly­gons” to mean “tile poly­gon 1 AND tile poly­gon 2″, not “tile the union of poly­gons 1 and 2”.

• It is a solu­tion similar to the one with the big shape which doesn’t cover any­thing, but the re­main­der is ar­bi­trar­ily minis­cule rel­a­tive to the shape.

We called it “a triv­ial solu­tion”, as I call this solu­tion triv­ial, but maybe less triv­ial, since it ac­tu­ally cov­ers all and it wasn’t ex­plic­itly for­bid­den, not to peo­ple, not to the com­puter.

Now, I told my chitin’ comp, don’t do that, each in­stance of the shape should cover ei­ther the tri­an­gle, ei­ther the square!

We will see.

• I must say, that this solu­tions of yours is quite im­pres­sive. Quite im­pres­sive in­deed.

• I promise you scores and images of solu­tions, what­ever they will be. Calcu­la­tions are un­der way right now and they should be available soon.

• Okay, sounds ex­cit­ing!

• The score point is not 6 at your solu­tion.

• They means point six, i.e. 0.6. In fact their score is 0.6188....

• True.

As I also see now, my prob­lem for­mu­la­tions are a prob­lem be­fore the prob­lem it­self.

• That’s okay since the ac­tual prob­lems are in­ter­est­ing.

• Thanks. The goal is a prob­lem childishly easy to un­der­stand and dev­il­ishly difficult to solve.