Can you tile an equilateral triangular tile with a triple N set of triominos

[The_Doctor]

Homework Statement

A tri-omino is an equilateral triangular tile with lines dividing the triangular face into four equilateral triangles decorated with blanks or pips. There are (N+3)(N+2)(N+1)/6 tri-ominos in a Triple N set. Is it possible to tile a triangular region without gaps or overlaps using a complete Triple N set of tri-ominos if N > 1?

Homework Equations

Pell's equation

The Attempt at a Solution

Given any number of triominoes and an equilateral triangular tile of any size, how many triominoes are needed to tile that tile? Well all equilateral triangles are similar, so let us say each triomino has a side length of n. This means the tile will have a side length of kn, due to similarity where k is arbitrary. Because we can only use whole triominoes, not fractions of them, k must be an integer. The area of each triomino is (√3/4)*n² and the area of the tile will be (√3/4)*(kn)². To work out how many triominoes are needed to tile the tile, we divide the tile's area by the area of each triomino. Once divided we get k^2. Thus k^2 triominoes are needed to tile an equilateral triangular tile of length kn. So we need to find out when (N+3)(N+2)(N+1)/6 is a perfect square.

(N+1)(N+2)(N+3)/6 must be in the form $\frac{x^22y^23z^2}{6}$. Here is the proof: N+1, N+2 and N+3 are consecutive numbers, and thus one and only one will be divisible by 3. Secondly, because they are consecutive, N+1, N+2 and N+3 will not share any prime factors except for 2, when N+1 and N+3 is even. Because there is a 6 as the denominator, which is 2*3, (N+1)(N+2)(N+3) must have an odd power of 2 when represented in prime factors. Since only a maximum of 2 of the 3 consecutive numbers will be even and thus have 2 as its prime factors, only 1 of the three consecutive numbers can have an odd power of 2 in its prime factors. And because none of three consecutive numbers share prime factors other than 2, we can say that (N+1)(N+2)(N+3)/6 must be in the form $\frac{x^22y^23z^2}{6}$ and can only be in that form in order for (N+1)(N+2)(N+3)/6 to be a perfect square.

Now we don't know which of the three consecutive numbers, x^2, 2y^2 and 3z^2 will equal. So $x^2-3z^2= \pm 1,\pm 2$. However,
$0^2\equiv 0\pmod{3} \\ 1^2\equiv 1\pmod{3} \\ 2^2\equiv 1\pmod{3}$
Therefore, $x^2-3z^2=1,-2$

Let's say that x^2=N+2 and 3z^2=N+1. Then x^2-3z^2=1. This gives us a Diophantine equation; specifically Pell's equation. The minimal solution to this is x=7, z=4. The solutions to this equation must also fit this equation: x^2-2y^2=-1, a negative Pell equation. Long story short, x=7 works and gives y=5. So we have 3*4^2*7^2*2*5^2/6=(4*7*5)^2

I quickly typed up a program to brute-force answers, and it only came up with N=1,47. Are these the only solutions? And how would you go about proving it?

But my method of finding the solutions is pretty bad. Is there a more logical way of finding out if there are possibilities? E.g. I just guessed if x^2=N+2, and it gave me the right answers, but is there a way of deducing it logically?

 

[Joffan]

There are (N+3)(N+2)(N+1)/6 tri-ominos in a Triple N set.

... only if you ignore handedness. But that's part of the givens, so we won't attack that too fiercely...

Is it possible to tile a triangular region without gaps or overlaps using a complete Triple N set of tri-ominos if N > 1?

N=1 is interesting too - the number of tiles is good but the task of aligning the numbered edges fails.

The Attempt at a Solution

Given any number of triominoes and an equilateral triangular tile of any size, how many triominoes are needed to tile that tile?

Similar figure areas scale as the square of their linear dimensions - but you got there anyway.

(N+1)(N+2)(N+3)/6 must be in the form $\frac{x^22y^23z^2}{6}$. Here is the proof: N+1, N+2 and N+3 are consecutive numbers, and thus one and only one will be divisible by 3. Secondly, because they are consecutive, N+1, N+2 and N+3 will not share any prime factors except for 2, when N+1 and N+3 is even. Because there is a 6 as the denominator, which is 2*3, (N+1)(N+2)(N+3) must have an odd power of 2 when represented in prime factors. Since only a maximum of 2 of the 3 consecutive numbers will be even and thus have 2 as its prime factors, only 1 of the three consecutive numbers can have an odd power of 2 in its prime factors. And because none of three consecutive numbers share prime factors other than 2, we can say that (N+1)(N+2)(N+3)/6 must be in the form $\frac{x^22y^23z^2}{6}$ and can only be in that form in order for (N+1)(N+2)(N+3)/6 to be a perfect square.

Nice. You should perhaps also note that at most one of N+1, N+2, N+3 is a perfect square to get your result. You also know that only z can possibly be divisible by 3, incidentally - not x or y.

Now we don't know which of the three consecutive numbers, x^2, 2y^2 and 3z^2 will equal.

You can tie this down a bit more by considering the numbers mod 6. This still gives three possible orderings for the components, and since you already have an example of each case (N=0,1,47) it seems unlikely that much further elimination can be done. My brute force testing of squares agrees with your brute force, up to N ~ 2^31, incidentally.

So, anyway... you have a candidate set that has the right number of tiles to make a larger triangle... but does that answer the question?

 

[The_Doctor]

... only if you ignore handedness. But that's part of the givens, so we won't attack that too fiercely...

Pardon my ignorance, but what is handedness?

You can tie this down a bit more by considering the numbers mod 6. This still gives three possible orderings for the components, and since you already have an example of each case (N=0,1,47) it seems unlikely that much further elimination can be done. My brute force testing of squares agrees with your brute force, up to N ~ 2^31, incidentally.

Hmm, yeah, I didn't consider using mod 6. It certainly does seem unlikely that further elimination can be done. There are 2 things I would like to ask though, which are: can you simultaneously solve Diophantine equations? For if you could, you could solve the 3 pairs of Diophantine equations.

On the other hand, is it necessary to use Diophantine equation? I can't see any other way of solving this question, but maybe there is. Can you see any other way of solving it?

 

[Joffan]

Pardon my ignorance, but what is handedness?

A tile with three dissimilar numbers on it has two different forms; for example 0-1-2 and 0-2-1 are distinct. The formula given implies that only one of these is present in the set.

There are 2 things I would like to ask though, which are: can you simultaneously solve Diophantine equations? For if you could, you could solve the 3 pairs of Diophantine equations.

On the other hand, is it necessary to use Diophantine equation? I can't see any other way of solving this question, but maybe there is. Can you see any other way of solving it?

I think any Diophantine equation with three variables in it is tough. Unfortunately I don't really know whether what you suggest is feasible. No simpler way of approaching the problem occurs to me for now, and the presence of the N=47 solution does suggest that something like this is required.

There is one further step I would take, but it is ambiguous in the question as to whether the matching edges rule is to be used when forming the larger figure. If it is used, N=47 is not a viable solution - do you see why?

 

[The_Doctor]

A tile with three dissimilar numbers on it has two different forms; for example 0-1-2 and 0-2-1 are distinct. The formula given implies that only one of these is present in the set.

Hmm, yeah. I understand what you mean. The formula isn't concerned with order.

I think any Diophantine equation with three variables in it is tough. Unfortunately I don't really know whether what you suggest is feasible. No simpler way of approaching the problem occurs to me for now, and the presence of the N=47 solution does suggest that something like this is required.

I think if you approach the problem algebraically, you'll end up having to use Diophantine equations, because there is a solution, and there could be more. Although the question only asks if it is possible, so maybe there is no way of proving 47 is the only answer, or maybe there are infinitely many solutions but they are really large.

And also, this question just came from some practice questions for this very hard maths competition. But I'm in high school (secondary level of education), and this competition is only meant for students in high school, so I'm not sure if they'd expect us to know Diophantine equations and how to solve them.

There is one further step I would take, but it is ambiguous in the question as to whether the matching edges rule is to be used when forming the larger figure. If it is used, N=47 is not a viable solution - do you see why?

This was actually pretty interesting, as interesting if not more than the original question. Basically I thought of it like this: if N=47, you have 19600 tri-ominoes. Each tri-omino has 3 equilateral triangles with numbers, so you have a total of 19600*3 numbers. So we know the tile can be tiled with a triple 47 set, the question is can we arrange 19600*3 numbers on the outer triangles on each tri-omino in the tile, such that each smaller triangle of each tri-omino that has an adjacent side with another triangle have the same number. Basically, I drew up a diagram of some tri-omnioes, and if we concentrate on each point of each tri-omino, we notice that each point that isn't on the side of the tile has 6 smaller triangles of 6 tri-ominoes around it, which share sides and create a hexagon around the point. Similarly, on the side, each side point has 3 smaller triangles of 3 tri-omnioes. There will also be 3 corner points of the tile which don't share any sides.

There are k+1 points on each side of the tile. If N=47, then √(48*49*50/3)=k=140. Using the formula for triangular numbers, you get 141*142/2=10011 points. 3 of these will be corner points. On each side, there are (k+1-2) non-corner points. Thus in total, there are (140+1-2)*3=417 side points. The rest must be "centre points", which is 9591. Around each "centre point", there are 6 adjacent triangles of 6 tri-ominoes, and 3 around each side point. To double check we are correct, 9591*6+417*3+3=19600*3. Each number between 0 and 47 will appear an equally often in the 19600*3 numbers. So every number between 0 and 47 will appear 19600*3/48=1225 times. These 1225 numbers of each number need to be placed around each point so each point shares numbers, however 1225 isn't divisible by 3, thus you will have leftovers when placing them around the side and "centre points", and there are only 3 corner points, so it will be impossible to make sure each tri-omino has matching sides.

Hopefully I'm right :D.

 

[Joffan]

Your matching edges argument works fine. I didn't get into the actual numbers, just used a mod-3 argument once I noticed that all non-corner junctions required 3 or 6 copies of the same number gathered together. Combining this with the total copies of each number, which is #tiles*3/#numbers = (N+2)(N+3)/2, this puts a mod-3 restriction on N for N>2 (when we have used up the corners), which N=47 fails.

 

[The_Doctor]

Your matching edges argument works fine. I didn't get into the actual numbers, just used a mod-3 argument once I noticed that all non-corner junctions required 3 or 6 copies of the same number gathered together. Combining this with the total copies of each number, which is #tiles*3/#numbers = (N+2)(N+3)/2, this puts a mod-3 restriction on N for N>2 (when we have used up the corners), which N=47 fails.

Haha yeah. Much simpler.

Well thanks anyway for all your help, and the extra question was very interesting as well. If you do find a way of solving both Diophantine equations or a method of solving the problem without Diophantine equations, be sure to post!