You can come arbitrarily close by choosing any tiling shape and making it as small as necessary.
No, because the degree of failure of the tiling is judged against the area of the covering shape.
This is one of the more confusing problem statements, but I think I understand. So if we choose a regular hexagon with height = 0.5, as in this link, the scoring for this solution would be ((area of triangle—area of hexagon) + (area of square − 3 * area of hexagon)) / area of hexagon?
edit: The best solution I could come up with was just the a right triangle that’s half the area of the equilateral triangle. You can fit 4 in the square and two in the triangle, and the score is point six. I only tried a handful of regular tilings though.
I can beat your solution and get a score of 0.433....
Take the covering shape to be the whole square and completely fail to cover the triangle.
EDIT: In fact, why not get a really good score by taking a completely gigantic shape that doesn’t cover anything.
Yes, well … If the shape is gigantic and therefore doesn’t cover anything … this is a cunning solution, but in a sense trivial.
A non-trivial solution would be (even) better. ;)
Okay, here’s a non-trivial answer. I believe I can get arbitrarily close to a score of 1/sqrt(3) = 0.57735… .
Pick any natural number n, and let x = sqrt(3)/2. Using the theory of continued fractions one can find natural numbers p and q such that q > n and x < p/q < x + 1/(4sqrt(3)q^2). Now let our covering shape be a right angled triangle with sides 1/(2p) and x/p. The area is x/(4p^2). Clearly 2p^2 such triangles can cover the equilateral triangle exactly.
Now consider how many we can fit in the square. By using two of our covering triangle we can make a rectangle of sides 1/(2p) and x/p. By arranging such rectangles in a 2p by q grid we can perfectly tile a big rectangle with sides 1 and qx/p. Since x < p/q we have qx/p < 1, so this rectangle fits into the square.
The remaining 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). Comparing this to the area of our covering triangle 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 arbitrary this can come arbitrarily close to a score of 1/sqrt(3).
EDIT: I made a picture of the tiling of the square when p=13, q=15. The uncovered area is the tiny red line at the top. The score is 0.57756… .
I will publish my solution next Monday.
I’m interested to see your solution.
I will present my (computer generated) solutions ASAP. Currently they are still evolving.
Literally evolving? are you running a genetic algorithm?
It is everything I can do. Digital evolution.
I wouldn’t call that genetic algorithm, there are some differences. For example, I evolve code, which further evolves some code, which evolves a problem solutions of a problem. May be several layers between the first code and the final solution.
I can improve my score to (620sqrt(3)-973)/191 = 0.528… using this arrangement.
EDIT: This arrangement does even better with a score of (19328sqrt(3)-30613)/6143 = 0.466… . Note that there is a tiny corner cut off each trapezium.
Interesting. We will see where this is going to go.
Any luck? I’d be interested in seeing some of the computer solutions even if their scores didn’t beat mine.
By the way I can now improve my score to 14sqrt(3)-24 = 0.249… . My covering shape is a 1⁄4 by 1⁄7 right-angled triangle. This clearly tiles the square perfectly and you can also fit 24 of them into the equilateral triangle. To see this first divide the equilateral triangle exactly into 24 right-angled triangles of sides 1⁄4 and 1/(4sqrt(3)), and then note that 1⁄7 < 1/(4sqrt(3)). There’s no point in drawing a picture since you can barely see the gaps.
The cheaty solution at the end depends on what seems to me an unintended interpretation of the question (though, given that the same person wrote the question and the program that found the solution, maybe my idea of what’s intended is wrong). I took “tile both polygons” to mean “tile polygon 1 AND tile polygon 2″, not “tile the union of polygons 1 and 2”.
It is a solution similar to the one with the big shape which doesn’t cover anything, but the remainder is arbitrarily miniscule relative to the shape.
We called it “a trivial solution”, as I call this solution trivial, but maybe less trivial, since it actually covers all and it wasn’t explicitly forbidden, not to people, not to the computer.
Now, I told my chitin’ comp, don’t do that, each instance of the shape should cover either the triangle, either the square!
We will see.
I must say, that this solutions of yours is quite impressive. Quite impressive indeed.
I promise you scores and images of solutions, whatever they will be. Calculations are under way right now and they should be available soon.
Okay, sounds exciting!
The score point is not 6 at your solution.
They means point six, i.e. 0.6. In fact their score is 0.6188....
As I also see now, my problem formulations are a problem before the problem itself.
That’s okay since the actual problems are interesting.
Thanks. The goal is a problem childishly easy to understand and devilishly difficult to solve.
“Quick! Fetch me a five-year-old devil!”
isn’t that any five year old?