Monday, October 23, 2017

Diophantine Desmos

It may happen that you have a real valued function, but only want to find those points where both the input and output are integers.

For example, consider y = sqrt(x). Suppose you had a graph of sqrt(x) and wanted to show which values of x give an integer result for y, i.e. which values of x are perfect squares:

y = sqrt(x) with only integer solutions shown

I recently learned how you can find and display integer solutions for certain types of equations in Desmos, and thought I would write a post about how to do this. 

When we care only about the integer solutions of an equation, we refer to it as a Diophantine equation. In general, Diophantine equations can take many forms - the technique described here can be used in a limited class of problems where you can express your Diophantine equation as a function k = f(n), where f takes integers n as inputs and want to know which outputs k are also integers (k > 0).

step 1 - define your real valued function
Let's see how to apply this method using sqrt(x). First, plotting the real-valued f(x) = sqrt(x) function, and creating a list of points by evaluating it for a range of integers, shows there are many points on the graph where we put in an integer, and get out a non-integer.

What we do next is to use some of the functions built into Desmos to create an integer detector function, that we can apply to the outputs of f(x).

step 2 - create the integer detector function
We'd like to build a function that can tell if a given input is an integer or not, and then use this to find out when we have an integer value for f(n). 

We would like to create an indicator function for integers that behaves like this:

To do this, we can make use of some built in functions in Desmos - the ceiling and floor functions. 

The function ceil rounds a decimal value up to the nearest integer, and floor rounds it down to the nearest integer.  Consequently, floor(x) <= ceil(x), with equality only if  x is an integer. Note also that for x > 0,  ceil(x) != 0, and floor(x)/ceil(x) <= 1, with equality only if x is an integer. The function floor(x)/ceil(x) is almost what we want - it is equal to 1 only when x is an integer. To get a function that is zero when x is not an integer, we take the floor again:

By composing t and f, we obtain a function tf which tells us when the values of f are integers. Plotting t(f(x)) for a range of integer inputs shows us which values of f give integer results.

points in red show values for (x, tf(x)), ponts
in blue show values for (x, f(x)). 

The final step is to integrate tf into our graph so that we can plot the integer solutions to y=f(x).

step 3 - taking advantage of undefined
Desmos handles undefined points gracefully - it just will not plot them. Consequently, if we create a function g, which is identical to f where f takes on integer solutions, but is undefined when it does not, we can get Desmos to plot exactly the points we want and no others.

To create g, we can combine f with our indicator function t:

Plotting points using this new function shows only those which correspond to integer solutions for f(x).

integer solutions to y = sqrt(x), graph here

Another example - Pythagorean triples
We encounter another example of Diophantine equations when trying to find Pythagorean triples. A Pythagorean triple is an integer solution to the equation a^2 + b^2 = c^2.

At first it might look like we can’t apply the method developed above to the problem of finding Pythagorean triples - there seem to be too many variables in play. However, we can explore the problem within certain ranges by taking advantage of other features that Desmos provides.

We can first define our function as a two variable function, and then use partial evaluation to obtain a new single variable function, parameterized by a slider p.

This allows us to explore Pythagorean triples where one of the legs of the triangle is fixed (determined by the value p). Using the method described above, we can find triples involving p as one of the legs.

some triples found by Desmos, 
where p=24 (graph here)

For example, with p = 24, Desmos finds the triples (24, 7, 25), (24, 18, 30), and others shown in the image above.

Some older Desmos-related posts:
- Brain and Propeller Fractals in Desmos
- Polygonal Number Diagrams using Desmos
- Spirals in Desmos
- Spirolaterals in Desmos

Tuesday, October 3, 2017

a Truchet puzzle mystery

I thought it would be fun to create a page of Truchet puzzles, and while doing this I noticed something that surprised me: even though they were randomly generated, all puzzles of the same size had the exact same level of complexity.

a single puzzle piece
that can be rotated into 4 positions

In these puzzles, Truchet tiles like the one above are used to create a specific pattern. All the pieces are the same - it is just a question of rotating them correctly to make the pattern you are aiming for.

a Truchet puzzle: can you make this pattern
using only Truchet tiles?

We can make these Truchet puzzles a bit more interesting if we have a specific starting arrangement, and add the restriction of using the smallest number of moves (clockwise rotations of individual tiles) to get from the starting arrangement to the target arrangement.

how many clockwise rotations of tiles will it take to transform
the square on the left to the one on the right?

On this page, you can try out some puzzles like this. Because you are only allowed to rotate pieces clockwise, you may have to rotate a given tile 0, 1, 2 or 3 times in order to get it into the desired position.

Please give it a try:

When setting up this puzzle page, I used a restricted set of arrangements for both the starting and target arrangements. For the starting arrangement, I have all the Truchet tiles in the same position. Let's call this  type of arrangement a uniform Truchet square. There will be 4 different uniform Truchet squares of a given size; here is one for n = 6:

a uniform Truchet square: all tiles
are in the same position

Because I like the way they look, I chose the target arrangements to always have 4-fold rotational symmetry. An important choice as it turns out. These Truchet squares have sides of even length, and can be divided up into 4 quadrants - as we move around the quadrants in a clockwise direction, the pattern in each quadrant is a 90 degree rotation of the pattern in the preceding quadrant.

you can make Truchet squares with 4-fold rotational
symmetry - they tend to look nice.

With these restrictions, I found that:
  • All 2x2 puzzles are solvable in 6 moves.
  • All 4x4 puzzles are solvable in 24 moves.
  • All 6x6 puzzles are solvable in 54 moves.
Mysteriously, no matter what pattern was chosen for the target, all puzzles of the same size required the same number of moves to solve. 

symmetric puzzles of the same size always
have the same number of required moves

In general, it turns out that for any Truchet square T with side length n and 4-fold rotational symmetry, T will always be 6*(n/2)^2 rotations away from any uniform Truchet square.

This was more puzzling than the original puzzles: how could my randomly generated puzzles all require the same number of moves to solve?

To understand why this is the case, we can find a way to count all the rotations required to transform a uniform Truchet square into one that has four-fold rotational symmetry, and see that this does not depend on a particular choice of either the starting arrangement or the target. This turns out to be easier than you might expect.
Let U be a uniform Truchet square of side length n, and T be a Truchet square with 4-fold rotational symmetry, also of side length n. We'll count how many rotations it takes to transform U into T
Let t1 be a tile in the first quadrant of U. If we consider its image under rotation into the other quadrants, we have a set of 4 tiles, t1, t2, t3, and t4. One of these will be aligned with the corresponding tile in T (since the tiles in T that lie in the same positions as t1, t2, t3, and t4 are rotated through all 4 positions, while the tiles of U are all in the same position). It will require 0 moves for this tile be put into the same position as the corresponding tile of T. As we move around the quadrants to the other images of our selected tile, they will all be in the same position (U is uniform), but the corresponding tiles of T will be rotated. The corresponding tiles of T will be 1, 2, and 3 rotations ahead from the tiles of U. So each tile in the first quadrant will, along with its images under rotation, contribute 0+1+2+3 = 6 rotations to the overall number of rotations required to transform U into T. There are (n/2)^2 tiles in the first quadrant, hence the total number of rotations required to transform U into T will be 6*(n/2)^2.
for a given n, it always takes the same number of moves
 to transform a uniform Truchet square U into another
one, T, if T has 4-fold rotational symmetry

The reason for all the puzzles requiring the same number of moves is the 4-fold symmetry of the target (and the uniformity of the starting arrangement). If we allowed non-symmetrical target arrangements, or varied the starting arrangements used, the number of rotations required to transform our starting arrangement into the target arrangement could lie anywhere between 0 and 3n^2.

a 24 x 24 Truchet square with 4-fold rotational
symmetry - starting from a uniform square, how
many moves would be required to re-create it? 

Why do the Truchet squares with rotational symmetry seem particularly nice? The human brain loves symmetry, but in the case of Truchet squares, it seems particularly appropriate to be drawn to arrangements like these. Individual Truchet tiles lack rotational symmetry - this lack of symmetry is what gives them their expressive power. By arranging them into a square pattern that does have rotational symmetry, we are overcoming the asymmetry of the original tile, appealing maybe to our need to unify opposites, or to express a sense of dialectical tension.

Some earlier posts on Truchet tiles:
truchet en plus
truchet tiles