Shapes made of concave and canvex curves combination problem

Question

I have been working on this particular problem for a considerable amount of time. The problem is as follows:

[[ Image of problem ]]

In the $7$-by-$7$ grid above, one can draw a simple closed curve using nothing but quarter-circle segments. Two examples are shown above: one enclosing a region of $4-\pi$ (in blue), and one enclosing a region of area $6$ (in red).

It can be shown that there are $36$ ways to enclose a region of area exactly $4-\pi$. How many ways can one draw a curve enclosing a region of area exactly $32$?

Note that a simple curve is not allowed to self-intersect.

I have drawn an image to visualize what a shape would look like.

[[ A red dot shows that the curve is convex and a green dot shows that the curve is concave. ]]

Based on the example image I know from the red figure: we have $4$ concave and $4$ convex curves. When $4$ concave curves are together we get an astroid shape which has the area $4-\pi$. When we have $4$ convex curves together we get a circle with area $\pi$. Because the red figure has an area of $6$, with $2$ empty boxes in the middle. We can see that what we have left is the area of an astroid + area of circle $= 4-\pi+\pi = 4$.

This tells use that the area of convex + concave curve is $1$.

We will always occupy $22$ boxes with a curve and we need to have $11$ concave curves and $11$ convex curves. We will also always have $21$ empty boxes inside the shape and $6$ empty boxes outside of the shape, in order to get the desired area of $32$.

At this point I just need to find out all of the combinations of shapes that I can make, this is the part that I am stumped on. The only approach I have thought of was to think about each box as a binary value (either concave or convex). Then try to find all of the combinations by reflecting and rotating the different shapes.

Answer 1

Here's an approach to calculate the number of solutions. It is inspired partly by Lourrran's comment to the question, which suggests initially drawing the curves as diagonals and then working out the number of ways to draw the entire perimeter using quarter circles.

The first of the three images above is the shape from the question redrawn with straight edges that are the diagonals of the grid. It is divided into $16$ sub-squares oriented diagonally with respect to the underlying $7$-by-$7$ grid. Assuming that a small square of the underlying grid has area $1$, it is easily shown that each of the sub-squares of the shape has area $2$ and so the total area of the shape is $32$, as required.

The second and third images above show the maximum area that can be enclosed by drawing diagonals in the grid. There are two images because there are two distinct ways to orient this. Note that each of these shapes contains $18$ of the diagonal sub-squares.

With the above in mind, proceed as follows:

1. For one orientation, work out the number of shapes that can be drawn by removing $2$ of the $18$ sub-squares in a way that creates a simple perimeter.
2. For each of the shapes identified in step $1$, work out how long its perimeter is. Calculate the number of possible ways to draw the perimeter using quarter circles as suggested by Lourrran: if the perimeter is $2n$ diagonals long there are $^{2n}C_{n}$ ways to draw the perimeter. Add all these values together.
3. As there are two possible orientations, double the total from step $2$ to get the final total.

This may seem long-winded, but there are short-cuts to be found in steps $1$ and $2$ that make the calculation fairly straightforward.

Answer 2

I just realised there could be 100s of it. Because after every box we fill with a concave or a convex we get 2 choices and 3 possible boxes so that the lines stay connected, meaning 6 possibilities for every 22 boxes. (6x22=132) But some of the boxes will be at the edges so we will only get 1 possible box and 2 choices. If we consider this, then in every arrangement 18 maximum boxes will be at the edges i.e. 6x4 + 18x2 = 60 possibilities)

---

Then there are 6 extra boxes left each time after completing the figure. These 6 can be put into the 4 corners of the 7x7 square with many possibilities. Considering that every time 2 or more single boxes will be left at the corners because they will be.. it will be around 24 more possibilities? But some of this will be included in the above formation of the figure part. Like an overlapping set. So for the safe side I will not be including these possibilities in my answer. And also the orientation factor will be included in this.

So we can safely say that there will be >60 possibilities. For the exact number of posibility we will have to draw each one or include some missing factor in my calculations. Let me knoe if there is something.

Wow it took me more than AN HOUR AND HALF to come to the inference :)
Nice Question!