1

Suppose that there is $S$, a finite set of unit squares. So, $S$ is chosen from a larger grid of unit squares. The unit squares of $S$ are tiled with isoceles right triangles. Each of these triangles has a hypotenuse of $2$. There are $3$ conditions that these triangles meet: none of the triangles overlap each other, none extend past the finite set $S$, and all of $S$ is covered fully by the triangles. Also, the hypotenuse of each triangle lies along any grid line. Also, the vertices of the trianlgles lie at the corners of the squares. Can someone help me prove that the number of triangles there are, have to be of a multiplicity of $4$?

enter image description here

I draw a directed graph. For each unit square we use a vertex. Now start at any vertex and create a Hamiltonian directed cycle, where A->B if one half-square of A and one half-square of B create a hypotenuse-2 triangle.

We obtain a polygon that is the Hamiltonian directed cycle. If a side of the polygon is between two turns in opposite directions, it has even length, otherwise it has odd length.

Now for each 270º corner, substitute it by three 90º corners, this will add 4 units to the total perimeter so the total perimeter modulo 4 hasn't changed. Now we have a (maybe self-intersecting and non-convex) polygon where all the corners are 90º. All the sides measure an odd integer. Now it is trivial that the perimeter is a multiple of 4, because the polygon is equivalent to a rectangle with all sides odd.

mathwhizz
  • 11

1 Answers1

0

Here are the major steps. You can look at them one at a time.

Step 1

Follow the chain of shorter sides of the triangles, since each triangle's shorter side must be shared with another triangle. The chains must be finite and don't overlap. [You already did something similar.]

Step 2

The chain of shorter sides must alternate in direction and form a closed polygon with every angle being 90 or 270 degrees.

Step 3

The polygon has the same number of sides of each direction. And the number of sides of each direction is even.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • So from this can we assume a multiplicty of 4? – mathwhizz Jan 19 '15 at 16:30
  • @mathwhizz: If you prove that the number of triangles in each chain is a multiple of 4 you are done. Can you see why that follows from the above? – user21820 Jan 19 '15 at 16:31
  • I'm sorry, I don't really know how I can prove that each chain is of multiplicity 4. – mathwhizz Jan 19 '15 at 16:33
  • @mathwhizz: Do you understand Step 3? The alternation in direction implies that the number of edges in one direction is the same as the number of edges in the other direction. The fact that it is closed means that for each direction you need an even number of edges, because it's equivalent to starting somewhere and going left/right finitely many times and end at the start. – user21820 Jan 19 '15 at 16:38
  • Wait, so what was the problem in my proof that I posted earlier? – mathwhizz Jan 19 '15 at 16:39
  • @mathwhizz: I didn't get past the first part because I didn't understand how you define direction. – user21820 Jan 19 '15 at 16:39
  • Can you take another look at it please – mathwhizz Jan 19 '15 at 16:41
  • @mathwhizz: Okay I just managed to figure out what you were doing. Don't say "directed" since it's undirected edges. Check that each vertex belongs to at most one finite cycle (which corresponds to my Step 2). You also have to explain precisely what you meant with your replacement step. I managed to guess but it's hard to guess. After that you still are not done as it isn't obvious that the result is "equivalent to a rectangle". It is not since it can self-intersect. There is however some other reason why its number of edges must be a multiple of 4. – user21820 Jan 19 '15 at 16:49
  • @mathwhizz: Once fixed, your solution will indeed be correct, but I think I would prefer my solution because I don't have to do any replacement operations. – user21820 Jan 19 '15 at 16:50
  • So what is the other reason? And so if I use what you wrote, I should be all right? – mathwhizz Jan 19 '15 at 16:54
  • @mathwhizz: Just think a bit. Walk along the perimeter of your polygon and see how many times you turn. Since you've converted it to only right turns or only left turns, it should be obvious. If you used what I wrote and filled in the details it would be correct. The correspondence is that your even/odd length of polygon edge corresponds to the alternating edges in my polygon. When the turns are the same, my polygon has an even number of edges in-between, just like your polygon has an even length edge in-between. But in my polygon it is just easier to get the answer directly after that. – user21820 Jan 19 '15 at 16:58
  • So there would be 4 turns. But how do I write that. I can't just say that can I? – mathwhizz Jan 19 '15 at 17:01
  • @mathwhizz: There may not be 4 turns. There may be 8 or 12 or ... If you start facing north, which direction do you end facing? How many turns is possible then? – user21820 Jan 19 '15 at 17:02
  • Any multiple of 4! – mathwhizz Jan 19 '15 at 17:07
  • @mathwhizz: Right, it must be a multiple of 4. I think it can be any positive multiple except 0, but all we need is that it is not a non-multiple of 4. Then your proof is complete. Note that what you write depends on how much you have to say to convince your audience that you know the complete reasoning. It's kind of cumbersome to give full details of why you need multiple of 4 to get back to facing the starting direction... – user21820 Jan 19 '15 at 17:08
  • So, how do I compile all of this into one big proof? – mathwhizz Jan 19 '15 at 17:09
  • @mathwhizz: For your solution, write what you wrote without the mis-terminology but add all the details that you ever think your audience may ask you about, especially the points I have queried you about. For my solution, you would similarly have to write enough extra details to convince your reader that the proof is watertight. – user21820 Jan 19 '15 at 17:13
  • Can you give me an example. I am not clear on this yet. – mathwhizz Jan 19 '15 at 17:47