The Best Fit Jigsaw

Computer Science Level 5

We wish to design a jigsaw puzzle with square pieces, whose length/width ratio is as close as possible to 2 \sqrt 2 .

For a small puzzle, we could make the puzzle 17 × 12 17\times12 , because ∣ ( 17 12 ) 2 − 2 ∣ = 1 144 \left|\left(\dfrac{17}{12}\right)^2 - 2\right| = \dfrac{1}{144} is very small. Let us call a ℓ × w \ell\times w puzzle good if the difference ∣ ( ℓ w ) 2 − 2 ∣ \left|\left(\dfrac \ell w\right)^2 - 2\right| is less than that same expression for any puzzle with fewer pieces.

How many pieces is the largest good puzzle with less than 10000 pieces?


The answer is 6930.

View wiki
Arjen Vreugdenhil by Arjen Vreugdenhil , 44, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Arjen Vreugdenhil
Feb 11, 2016 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
int best_num = 1, best_den = 1, N = best_num*best_den;
int best_difn = 1, best_difd = 1;

int num0 = 1;
for (int den = 1; N < 10000; den++) {

    for (int num = num0; ; num++) {

        int dn = num*num - 2*den*den; int dd = den*den;

        if (Math.abs((long)dn*best_difd) < Math.abs((long)dd*best_difn)) {
            N = num*den;

            System.out.print(num); System.out.print(" x ");
            System.out.print(den); System.out.print(" = ");
            System.out.println(N);


            best_num = num;
            best_den = den;

            best_difn = dn;
            best_difd = dd;

        }

        if (dn < 0) num0 = num; else break;
    }
}

Output: 

1
2
3
4
5
6
7
8
 
3 x 2 = 6
4 x 3 = 12
7 x 5 = 35
17 x 12 = 204
24 x 17 = 408
41 x 29 = 1189
99 x 70 = 6930
140 x 99 = 13860

The second-last line shows that the solution is 6930 \boxed{6930} . The dimensions are 99x70; then ( 99 70 ) 2 − 2 = 9801 − 9800 4900 = 1 4900 , \left(\frac{99}{70}\right)^2 - 2 = \frac{9801 - 9800}{4900} = \frac{1}{4900}, so that 99 : 70 99:70 is very close to 2 \sqrt 2 .

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Explanation:

The variables num and den represent the length and width. (After all, we are studying the value of the fraction num/den .) 

1
 
for (int num = num0; ; num++)

For any given width of the puzzle ( den ) we must try two length ( num ): one with a ratio just below 2 \sqrt 2 , and one with a ratio just above 2 \sqrt 2 ; you never know which one will give the better approximation! In my approach, the variable num0 remembers the greatest length that resulted in a ratio less than 2 \sqrt 2 ; it is the starting point for the search when we increase the width. The search continues until we have checked a ratio above 2 \sqrt 2 . When that happens, the break; statement in line 27 is executed, and we move on to the next width. 

1
 
int dn = num*num - 2*den*den; int dd = den*den;

This calculates the fraction d n / d d = ( n u m / d e n ) 2 − 2 dn/dd = (num/den)^2 - 2 . Of course I could have simply calculated this as a floating-point variable, but integers are way cooler (and potentially more precise). 

1
 
if (Math.abs((long)dn*best_difd) < Math.abs((long)dd*best_difn))

This is the same as checking whether ∣ d n / d d ∣ < ∣ b e s t _ d n / b e s t _ d d ∣ |dn/dd| < |best\_dn/best\_dd| , in other words, if there is any improvement compared to an earlier puzzle.

Arjen Vreugdenhil - 5 years, 4 months ago
Abdelhamid Saadi
Mar 26, 2016

My solution in python 3 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
from fractions import Fraction
from math import sqrt

def f(n):
    return min(abs(Fraction(n**2, k**4)- 2) for k in range(1, int(sqrt(n))+2) if n%k == 0)

def solve():
    "The Best Fit Jigsaw"
    minx = Fraction(2,1)
    for k in range(1, 10000):
        if f(k) < minx:
            minx, mink = f(k), k
    return mink

print(solve())

```

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Ville Karlsson
Mar 5, 2016

It is possible to partially guess the correct solution, needless to say this is rather handwavy and should not be really considered as a solution but as motivation. Consider the Pell's equation x 2 − 2 y 2 = 1 x^2-2y^2=1 and note that since x y = 1 y 2 + 2 \frac{x}{y}=\sqrt[]{\frac{1}{y^2}+2} we have x y ≈ 2 \frac{x}{y}\approx\sqrt[]{2} when y is even somewhat large. Now lets consider natural number solutions to these equations. The solutions can be generated recursively by x k + 1 = x 1 x k + 2 y 1 y k x_{k+1}=x_{1}x_{k}+2y_{1}y_{k} y k + 1 = x 1 y k + y 1 x k y_{k+1}=x_{1}y_{k}+y_{1}x_{k} Where ( x 1 , y 1 ) = ( 3 , 2 ) (x_{1},y_{1})=(3,2) is the fundamental solution. Largest solution so that x n y n < 10000 x_{n}y_{n}<10000 is x n = 99 , y n = 70 x_{n}=99, y_{n}=70 which "happens" to be the right solution, as may be intuitive.

Note also that we can easily generate pretty good solutions for jigsaws far greater than 10000 pieces without any difficulty, If I recall correctly it is actually provable that there is no better approximation x y t o : 2 \frac{x}{y} to: \sqrt[]{2} where y ≤ y k y\leq y_{k} than the k:th solution to pell's equation, but I am not sure. Next solutions are ( 577 , 408 ) (577,408) and ( 3363 , 2378 ) (3363, 2378)

0 Helpful 0 Interesting 0 Brilliant 0 Confused

The solutions you find this way all have x n / y n > 2 x_n/y_n > \sqrt 2 , but the problem clearly allows for solutions with x n / y n < 2 x_n/y_n < \sqrt 2 as well.

So, apart from your solutions x y x y ( x / y ) 2 x 2 − 2 y 2 3 2 6 2.25 1 17 12 204 2.006944 1 99 70 6 930 2.000204 1 577 408 235 416 2.000006 1 3363 2378 ⋮ > 2 1 \begin{array}{rr|rlr} x & y & xy & (x/y)^2 & x^2-2y^2 \\ \hline 3 & 2 & 6 & 2.25 & 1 \\ 17 & 12 & 204 & 2.006944 & 1 \\ 99 & 70 & 6\:930 & 2.000204 & 1 \\ 577 & 408 & 235\:416 & 2.000006 & 1 \\ 3363 & 2378 & \vdots & >2 & 1\\ \hline \end{array}

there are also

x y x y ( x / y ) 2 x 2 − 2 y 2 4 3 12 1.777778 − 2 7 5 35 1.96 − 1 24 17 408 1.99308 − 2 41 29 1 189 1.998811 − 1 140 99 13 860 1.999796 − 2 ⋮ < 2 \begin{array}{rr|rlr} x & y & xy & (x/y)^2 & x^2-2y^2 \\ \hline 4 & 3 & 12 & 1.777778 & -2 \\ 7 & 5 & 35 & 1.96 & -1 \\ 24 & 17 & 408 & 1.99308 & -2 \\ 41 & 29 & 1\:189 & 1.998811 & -1 \\ 140 & 99 & 13\:860 & 1.999796 & -2 \\ & & \vdots & <2 \\ \hline \end{array}

Arjen Vreugdenhil - 5 years, 3 months ago

Log in to reply

Gah! I missed that completely! Here is how to Intuit Your other solutions, we consider x 2 − 2 y 2 = − 1 x^2-2y^2=-1 now the recursion formula is x k + 1 = 3 x k + 4 y k x_{k+1}=3x_{k}+4y_{k} and y k + 1 = 2 x k + 3 y k y_{k+1}=2x_{k}+3y_{k} with fundamental solution ( x 1 , y 1 ) = ( 1 , 1 ) (x_{1},y_{1})=(1,1) . The rest of the solutions are tweaked from the orginal solutions as ( x n , y n ) → ( 2 y n , x n ) (x_{n},y_{n})\to(2y_{n},x_{n}) for if x y > ≈ 2 \frac{x}{y}>\approx\sqrt[]{2} then 2 y x < ≈ 2 \frac{2y}{x}<\approx\sqrt[]{2} where > ≈ >\approx denotes slightly greater and < ≈ <\approx denotes slightly lesser

Ville Karlsson - 5 years, 3 months ago

Log in to reply

That seems about right... Now the questions I have are

  • Can you prove that all solutions are of this kind?

  • Why are there many solutions with x 2 − 2 y 2 = − 2 x^2 - 2y^2 = -2 but not with x 2 − 2 y 2 = 2 x^2 - 2y^2 = 2 ?

As for the last question, we could try the "tweak" with your second recursion formula, and get e.g. ( 7 , 5 ) ↦ ( 10 , 7 ) (7, 5)\mapsto(10,7) and 1 0 2 − 2 ⋅ 7 2 = 2 10^2 - 2\cdot 7^2 = 2 . This is not a good solution because it is no improvement over ( 7 , 5 ) (7,5) -- but why this lack of symmetry?

Arjen Vreugdenhil - 5 years, 3 months ago
Brian Riccardi
Feb 15, 2016

My solution is a little bit ugly. Let $f_n$ be the best ratio with at most $n$ pieces and $g_n$ be the best ratio with exactly $n$ pieces, then: f 1 = 1 , f n = m i n { g n , f n − 1 } g n = min ⁡ l × w = n { ∣ ( l w ) 2 − 2 ∣ } Now we just compute the greater $n$ which verify $g_n < f_n-1$ \textbf{My solution is a little bit ugly.} \\ \text{Let \$f\_n\$ be the best ratio with at most \$n\$ pieces and \$g\_n\$ be the best ratio} \\ \text{with exactly \$n\$ pieces, then:} \\ f_1=1, f_n=min\{g_n, f_{n-1}\} \\ g_n=\displaystyle\min_{l \times w = n}\Big\{ \Big| \Big( \frac{l}{w} \Big)^2 - 2 \Big| \Big\} \\ \text{Now we just compute the greater \$n\$ which verify \$g\_n < f\_{n-1}\$}

To speedup the computation I used Dynamic Programming. \text{To speedup the computation I used Dynamic Programming.} 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <bits/stdc++.h>
using namespace std;

long double memg[10005], memf[10005];

long double abs_(long double x)
{
    if(x<0) return -x;
    return x;
}

long double g(int n)
{
    if(memg[n]!=-1.0) return memg[n];
    long double best=abs_((long double)n*n-2);
    long double N=n;
    for(long double l=1.0; l<=n; l+=1){
        int L=(int)l;
        if(n%L == 0)
            best=min(best, abs_( ((l*l)/N)*((l*l)/N)-2.0 ));
    }
    return memg[n]=best;
}

long double f(int n)
{
    if(n==1) return 1;
    if(memf[n]!=-1.0) return memf[n];
    return memf[n]=min(g(n),f(n-1));
}

int main()
{
    for(int n=0; n<10005; ++n)
        memg[n]=memf[n]=-1.0;
    int sol=1;
    for(int n=2; n<=9999; ++n){
        if(g(n)<f(n-1)) sol=n;
    }
    cout << sol << "\n";

    return 0;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...