27
$\begingroup$

You are given a grid. Some of the cells in the grid are labelled with positive numbers. You must partition the grid into triangles.

  • There must be a triangle for each labelled cell
  • Each cell must be completely contained within its triangle
  • The vertices of each triangle must be intersection points of the grid
  • Every triangle has one (or more) edges that are either horizontal or vertical
  • The cell's label specifies the area of its triangle

Here is an example to illustrate the problem.

Image of 6x6 problem and its solution

Observe that the restriction that every triangle must have a horizontal or vertical edge means that it is easy to work out its area. For example the triangle labelled 6 has base length 3 and height 4. So its area is $\frac{1}{2}(3 \times 4) = 6$ as required.

Here are two problems to solve, an easy one for practise and one that requires a little more effort. Both problems have a unique solution. Two 10x10 instances of the puzzle

You can of course solve it any way you like, but I find it easiest to print out the pictures and then draw lines on them using a ruler. There is no need to use a computer - they're not that hard! It would be nice for an answer to specify some of the steps used to find the solution.

I came up this idea myself. I find the restriction on valid triangles gives a nice balance between having too many options and too few options when partitioning the grid. I'm not aware of anyone else having already used the idea, but it wouldn't surprise me if it were not original. But the instances of the problem used here must be original.

$\endgroup$
9
  • 5
    $\begingroup$ Interesting puzzle. I've recreated the practise grid in Penpa if anyone else is interested. Use "free" edges to draw the triangles. $\endgroup$
    – fljx
    Commented May 9 at 14:11
  • 4
    $\begingroup$ Here is the link for the other puzzle. And nice puzzling idea indeed! $\endgroup$
    – ACB
    Commented May 9 at 16:19
  • $\begingroup$ This was a really fun and different puzzle, thank you for sharing! $\endgroup$ Commented May 10 at 23:08
  • 2
    $\begingroup$ @dewiMorgan It makes life much easier for the solver since they don't have to spend time thinking of other triangles, and working out their areas. (I put the rule in to make the area computation easy.). But since most triangles with no axis aligned edge won't have integer area they won't be permitted anyway. But most triangles is not all triangles. Thanks to magic of Pythagorean triplets there are triangles like {(3,0),(8,10),(0,4)} which has area 25 but no axis-aligned edge. I think it would be possible to build a problem in which I triangle like that one provides an alternate solution. $\endgroup$
    – user23087
    Commented May 11 at 4:11
  • 1
    $\begingroup$ @sarsaparilla I do. I used a C++ program to generate potential instances of the puzzle by starting from a random valid tiling. The program filters out tilings with too few triangles or non-unique solutions. It then computes (purely subjective) ratings of beauty and difficulty. Out of around 10,000,000 instances it selected the 10,000 that were most beautiful and then gave me the beautiful ones it thought were easiest and hardest, which are the ones I posted. So, ahem, I could post more instances of the puzzle every day. But I don't think that would be popular! $\endgroup$
    – user23087
    Commented May 16 at 13:06

3 Answers 3

7
$\begingroup$

Here is the solved ‘hard problem’:

enter image description here

Long story short I started with the pair of 20s in the bottom and found that only these pair of triangles work as a configuration: enter image description here

This then forces this since the 3 triangle has to be positioned this way to enable a 12 triangle to be formed… enter image description here

Which then forces this

The 5 has only one way to be formed… enter image description here Leading to this: enter image description here

The three triangle has two options but one of which doesn’t allow the 5 triangle so it forces it to be like so: enter image description here enter image description here After that there is only one way to complete the grid.

$\endgroup$
5
  • $\begingroup$ I found this easier than the practice one. $\endgroup$
    – PDT
    Commented May 9 at 17:11
  • $\begingroup$ Well done - this is the answer. I'm sure there are many different ways of doing it. I started in upper right corner and tried to figure out how much of the edge each successive triangle had to claim. $\endgroup$
    – user23087
    Commented May 9 at 18:18
  • $\begingroup$ @PDT your second to last image shows the alternative (impossible) choice for the 3 triangle... $\endgroup$ Commented May 16 at 9:11
  • $\begingroup$ @sarsaparilla yes that was meant to be… I wanted to show how the alternative doesn’t work… $\endgroup$
    – PDT
    Commented May 16 at 9:42
  • $\begingroup$ @PDT Ok I misread $\endgroup$ Commented May 16 at 10:06
8
$\begingroup$

Solution to the Practise problem:

enter image description here

And how to get there:

First, some observations:
Every triangle has (at least) one horizontal or vertical edge, and all the vertices must be on grid-points, so that edge has integer length.
If we call that edge the base of the triangle, its perpendicular height (to the vertex not on that edge) is also an integer.

So for each area there are a very limited number of options for base and height because they must be factors of 2*area.

No triangle can be 1-by-anything, because it would not contain any whole squares.
Prime area triangles can only be 2-by-P.
So area 2 triangles can only be 2-by-2, and must be a right triangle to include a whole square.

Adjacent numbers must have a horizontal/vertical edge between them.

  • Start by drawing edges between adjacent numbers, and completing all the forced area-2 triangles.
  • The 5 in the top-left corner must be 2-by-5, and nearby numbers on the edges mean there is only one possibility.
  • The other 5 on the left edge (R6C1) has a few possibilities, but must have a vertical 5-long edge on the left of the grid.
  • Area 15 triangles must be 5-by-6 or 3-by-10 (2-by-15 doesn't fit the grid). So the 15 on the bottom edge can only be 3-by-10, and must use all of the bottom edge. There are two ways it can fit without hitting other numbers, but only one of them avoids the left-edge 5. And that gives us two edges of that 5 triangle which can now be completed:
    enter image description here

  • The 15 near the right (R7C9) must also be 3-by-10, and the only way to fit a horizontal/vertical edge is by using the entire right-hand edge of the grid. And the diagonally adjacent 6 gives us only one way to fit this triangle.
  • The remaining 2 is now forced. And with it, the nearby 4: enter image description here

  • The 3 in R7C3 must be 2-by-3, and is sitting on a 2-long horizontal. There is only one way to complete it without hitting any numbers.
    And that also forces the other 3's which must use up the space around it. That gives us two edges and a corner around the 5 in R5C7, forcing it to extend to the top-right corner: enter image description here

  • Finally the last 15 must be 5-by-6, so must reach all the way into the apex on the left edge, and we are done.

    $\endgroup$
    8
    $\begingroup$

    Solution for the Practise Problem

    enter image description here

    I started

    with the simpler triangles (smaller numbers) and from there worked my way up. 2 for example must be a 2x2 triangle, 3 must be a 2x3 triangle, 5 must be a 2x5 triangle etc.. And since the whole grid needs to be partioned, meaning each of the vertices (except the 5 in left top corner) must be a vertex of some other triangle/triangles, it didn't require too much work to work out the rest.

    $\endgroup$
    6
    • 1
      $\begingroup$ +1 for using a "c" in the word practice. lol jk $\endgroup$
      – JLee
      Commented May 9 at 15:48
    • $\begingroup$ @JLee it has been edited, you can take back your upvote now :P $\endgroup$
      – ACB
      Commented May 9 at 16:23
    • $\begingroup$ lol. i am surprised he edited it. looks strange, but not nearly as strange as "maths" @ACB $\endgroup$
      – JLee
      Commented May 9 at 16:28
    • $\begingroup$ @JLee I couldn't think of a natural way to work "maths" or "colour" into the question. But I did manage "labelled". $\endgroup$
      – user23087
      Commented May 9 at 16:41
    • $\begingroup$ @JLee haha I actually thought it was a spelling mistake from my side $\endgroup$ Commented May 9 at 16:46

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

    Not the answer you're looking for? Browse other questions tagged or ask your own question.