show/hide this revision's text 4 Fix the code so that Markdown sees it as one block

The upper bound is <3.95.

I hope the code below will show correctly...

It proves that assuming a sum >=3.95 in the central AxB rectangle of the grid ({-B,-B+A,-2A,-A,0,A,2A,B-A,B}+{0,A}) x ({-2B,-B-A,-B,-B+A,-2A,-A,0,A,2A,B-A,B,B+A,2B}+{0,B}) leads to a contradiction in a finite number of steps. 3.95 is NOT best possible for this grid, but 3.94 does not lead to a contradiction. It will be easy to refine the number, but more worthwhile is probably to search a larger grid (which starts to get slow in awk.)

awk 'BEGIN {

 A=1;
 # pick B large enough to ensure that there
 # are no accidental squares in the grid below
 B=1000;

 # setting up the grid
 x[0]=-B;       x[1]=-B+A;
 x[1]=-B+A;     x[2]=-B+2*A;
 x[3]=-2*A;     x[4]=-A;
 x[4]=-A;       x[5]=0;
 x[5]=0;        x[6]=A;
 x[6]=A;        x[7]=2*A;
 x[7]=2*A;      x[8]=3*A;
 x[9]=B-A;     x[10]=B;
 x[10]=B;       x[11]=B+A;
 M=11;

 y[0]=-2*B;     y[2]=-B;
 y[1]=-B-A;     y[5]=-A;
 y[2]=-B;       y[6]=0;
 y[3]=-B+A;     y[7]=A;
 y[4]=-2*A;     y[9]=B-2*A;
 y[5]=-A;       y[10]=B-A;
 y[6]=0;        y[11]=B;
 y[7]=A;        y[12]=B+A;
 y[8]=2*A;      y[13]=B+2*A;
 y[10]=B-A;     y[14]=B+B-A;
 y[11]=B;       y[15]=B+B;
 y[12]=B+A;     y[16]=B+B+A;
 y[15]=2*B;     y[17]=3*B;
 N=17;

 for(i=0; i<=M; i++)
     for(j=i; j<=M; j++)
         for(k=0; k<=N; k++)
             for(l=k; l<=N; l++)
                 # 0 sum for degenerate rectangles
                 if(i==j || k==l) {
                     lo[i,j,k,l]=0;
                     hi[i,j,k,l]=0;
                 }                   
                 # squares
                 else if(x[j]-x[i]==y[l]-y[k]) {
                     lo[i,j,k,l]=-1;
                     hi[i,j,k,l]=1;
                 }
                 # other rectangles
                 else {
                     lo[i,j,k,l]=-4;
                     hi[i,j,k,l]=4;
                 }

 # central rectangle: assume its sum is >=3.95
 lo[5,6,6,11]=3.95;

 iter=10000;
 active=1;
 while(iter-- && active) {
     active=0;

     # traverse all possible combinations of 1 rectangle split into 4
     for(i=0; i<M; i++)
         for(j=i+1; j<=M; j++)
             for(k=0; k<N; k++)
                 for(l=k+1; l<=N; l++)
                     for(m=i; m<j; m++)
                         for(n=k; n<l; n++) {
                             lo0=lo[i,j,k,l];
                             lo1=lo[i,m,k,n];
                             lo2=lo[m,j,k,n];
                             lo3=lo[i,m,n,l];
                             lo4=lo[m,j,n,l];
                             hi0=hi[i,j,k,l];
                             hi1=hi[i,m,k,n];
                             hi2=hi[m,j,k,n];
                             hi3=hi[i,m,n,l];
                             hi4=hi[m,j,n,l];

                             # 3rd argument in max() and min() funtions
                             # is for printing purposes only...
                             lo0=max(lo0, lo1+lo2+lo3+lo4, 0);
                             hi0=min(hi0, hi1+hi2+hi3+hi4, 0);
                             lo1=max(lo1, lo0-hi2-hi3-hi4, 1);
                             lo2=max(lo2, lo0-hi1-hi3-hi4, 2);
                             lo3=max(lo3, lo0-hi1-hi2-hi4, 3);
                             lo4=max(lo4, lo0-hi1-hi2-hi3, 4);
                             hi1=min(hi1, hi0-lo2-lo3-lo4, 1);
                             hi2=min(hi2, hi0-lo1-lo3-lo4, 2);
                             hi3=min(hi3, hi0-lo1-lo2-lo4, 3);
                             hi4=min(hi4, hi0-lo1-lo2-lo3, 4);

                             if(lo0>hi0 || lo1>hi1 || lo2>hi2 || lo3>hi3 || lo4>hi4) {
                                 print "CONTRADICTION AT", i,m,j,k,n,l;
                                 exit;
                             }

                             lo[i,j,k,l]=lo0;
                             lo[i,m,k,n]=lo1;
                             lo[m,j,k,n]=lo2;
                             lo[i,m,n,l]=lo3;
                             lo[m,j,n,l]=lo4;
                             hi[i,j,k,l]=hi0;
                             hi[i,m,k,n]=hi1;
                             hi[m,j,k,n]=hi2;
                             hi[i,m,n,l]=hi3;
                             hi[m,j,n,l]=hi4;
                         }
 }
 print "FINISHED OK";
}

function max(s,t, where) {

if(s<t) {
    print "lo=" t, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);
}

function min(s,t, where) {

if(s>t) {
    print "hi=" t, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);
}
'
show/hide this revision's text 3 added 163 characters in body; deleted 4 characters in body

The upper bound is <3.95.

I hope the code below will show correctly...

It proves that assuming a sum of 4 >=3.95 in the central AxB rectangle of the grid ({-B,-B+A,-2A,-A,0,A,2A,B-A,B}+{0,A}) x ({-2B,-B-A,-B,-B+A,-2A,-A,0,A,2A,B-A,B,B+A,2B}+{0,B}) leads to a contradiction in a finite number of steps. With a lot of patience one could then work out an upper bound strictly <4 3.95 is NOT best possible for the generic AxBthis grid, but 3.94 does not lead to a contradiction. It will be easy to refine the number, but more worthwhile is probably to search a larger grid (which starts to get slow in awk.)

awk 'BEGIN {

 A=1;
 # pick B large enough to ensure that there
 # are no accidental squares in the grid below
 B=1000;

 # setting up the grid
 x[0]=-B;       x[1]=-B+A;
 x[1]=-B+A;     x[2]=-B+2*A;
 x[3]=-2*A;     x[4]=-A;
 x[4]=-A;       x[5]=0;
 x[5]=0;        x[6]=A;
 x[6]=A;        x[7]=2*A;
 x[7]=2*A;      x[8]=3*A;
 x[9]=B-A;     x[10]=B;
 x[10]=B;       x[11]=B+A;
 M=11;

 y[0]=-2*B;     y[2]=-B;
 y[1]=-B-A;     y[5]=-A;
 y[2]=-B;       y[6]=0;
 y[3]=-B+A;     y[7]=A;
 y[4]=-2*A;     y[9]=B-2*A;
 y[5]=-A;       y[10]=B-A;
 y[6]=0;        y[11]=B;
 y[7]=A;        y[12]=B+A;
 y[8]=2*A;      y[13]=B+2*A;
 y[10]=B-A;     y[14]=B+B-A;
 y[11]=B;       y[15]=B+B;
 y[12]=B+A;     y[16]=B+B+A;
 y[15]=2*B;     y[17]=3*B;
 N=17;

 for(i=0; i<=M; i++)
     for(j=i; j<=M; j++)
         for(k=0; k<=N; k++)
             for(l=k; l<=N; l++)
                 # 0 sum for degenerate rectangles
                 if(i==j || k==l) {
                     lo[i,j,k,l]=0;
                     hi[i,j,k,l]=0;
                 }                   
                 # squares
                 else if(x[j]-x[i]==y[l]-y[k]) {
                     lo[i,j,k,l]=-1;
                     hi[i,j,k,l]=1;
                 }
                 # other rectangles
                 else {
                     lo[i,j,k,l]=-4;
                     hi[i,j,k,l]=4;
                 }

 # central rectangle: assume its sum is 4
 lo[5,6,6,11]=4>=3.95
 lo[5,6,6,11]=3.95;

 iter=10000;
 active=1;
 while(iter-- && active) {
     active=0;

     # traverse all possible combinations of 1 rectangle split into 4
     for(i=0; i<M; i++)
         for(j=i+1; j<=M; j++)
             for(k=0; k<N; k++)
                 for(l=k+1; l<=N; l++)
                     for(m=i; m<j; m++)
                         for(n=k; n<l; n++) {
                             lo0=lo[i,j,k,l];
                             lo1=lo[i,m,k,n];
                             lo2=lo[m,j,k,n];
                             lo3=lo[i,m,n,l];
                             lo4=lo[m,j,n,l];
                             hi0=hi[i,j,k,l];
                             hi1=hi[i,m,k,n];
                             hi2=hi[m,j,k,n];
                             hi3=hi[i,m,n,l];
                             hi4=hi[m,j,n,l];

                             # 3rd argument in max() and min() funtions
                             # is for printing purposes only...
                             lo0=max(lo0, lo1+lo2+lo3+lo4, 0);
                             hi0=min(hi0, hi1+hi2+hi3+hi4, 0);
                             lo1=max(lo1, lo0-hi2-hi3-hi4, 1);
                             lo2=max(lo2, lo0-hi1-hi3-hi4, 2);
                             lo3=max(lo3, lo0-hi1-hi2-hi4, 3);
                             lo4=max(lo4, lo0-hi1-hi2-hi3, 4);
                             hi1=min(hi1, hi0-lo2-lo3-lo4, 1);
                             hi2=min(hi2, hi0-lo1-lo3-lo4, 2);
                             hi3=min(hi3, hi0-lo1-lo2-lo4, 3);
                             hi4=min(hi4, hi0-lo1-lo2-lo3, 4);

                             if(lo0>hi0 || lo1>hi1 || lo2>hi2 || lo3>hi3 || lo4>hi4) {
                                 print "CONTRADICTION AT", i,m,j,k,n,l;
                                 exit;
                             }

                             lo[i,j,k,l]=lo0;
                             lo[i,m,k,n]=lo1;
                             lo[m,j,k,n]=lo2;
                             lo[i,m,n,l]=lo3;
                             lo[m,j,n,l]=lo4;
                             hi[i,j,k,l]=hi0;
                             hi[i,m,k,n]=hi1;
                             hi[m,j,k,n]=hi2;
                             hi[i,m,n,l]=hi3;
                             hi[m,j,n,l]=hi4;
                         }
 }
 print "FINISHED OK";

}

function max(s,t, where) {

if(s<t) {
    print "lo=" t, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);

}

function min(s,t, where) {

if(s>t) {
    print "hi=" t, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);

} '

show/hide this revision's text 2 edited body

I hope the code below will show correctly...

It proves that assuming a sum of 4 in the central AxB rectangle of the grid ({-B,-B+A,-2A,-A,0,A,2A,B-A,B}+{0,A}) x ({-2B,-B-A,-B,-B+A,-2A,-A,0,A,2A,B-A,B,B+A,2B}+{0,B}) leads to a contradiction in a finite number of steps. With a lot of patience one could then work out an upper bound strictly <4 for the generic AxB.

awk 'BEGIN {

 A=1;
 # pick B large enough to ensure that there
 # are no accidental squares in the grid below
 B=1000;

 # setting up the grid
 x[0]=-B;       x[1]=-B+A;
 x[1]=-B+A;     x[2]=-B+2*A;
 x[3]=-2*A;     x[4]=-A;
 x[4]=-A;       x[5]=0;
 x[5]=0;        x[6]=A;
 x[6]=A;        x[7]=2*A;
 x[7]=2*A;      x[8]=3*A;
 x[9]=B-A;     x[10]=B;
 x[10]=B;       x[11]=B+A;
 M=11;

 y[0]=-2*B;     y[2]=-B;
 y[1]=-B-A;     y[5]=-A;
 y[2]=-B;       y[6]=0;
 y[3]=-B+A;     y[7]=A;
 y[4]=-2*A;     y[9]=B-2*A;
 y[5]=-A;       y[10]=B-A;
 y[6]=0;        y[11]=B;
 y[7]=A;        y[12]=B+A;
 y[8]=2*A;      y[13]=B+2*A;
 y[10]=B-A;     y[14]=B+B-A;
 y[11]=B;       y[15]=B+B;
 y[12]=B+A;     y[16]=B+B+A;
 y[15]=2*B;     y[17]=3*B;
 N=17;

 for(i=0; i<=M; i++)
     for(j=i; j<=M; j++)
         for(k=0; k<=N; k++)
             for(l=k; l<=N; l++)
                 # 0 sum for degenerate rectangles
                 if(i==j || k==l) {
                     lo[i,j,k,l]=0;
                     hi[i,j,k,l]=0;
                 }                   
                 # squares
                 else if(x[j]-x[i]==y[l]-y[k]) {
                     lo[i,j,k,l]=-1;
                     hi[i,j,k,l]=1;
                 }
                 # other rectangles
                 else {
                     lo[i,j,k,l]=-4;
                     hi[i,j,k,l]=4;
                 }

 # central rectangle: assume its sum is 4
 lo[5,6,6,11]=4;

 iter=10000;
 active=1;
 while(iter-- && active) {
     active=0;

     # traverse all possible combinations of 1 rectangle split into 4
     for(i=0; i<M; i++)
         for(j=i+1; j<=M; j++)
             for(k=0; k<N; k++)
                 for(l=k+1; l<=N; l++)
                     for(m=i; m<j; m++)
                         for(n=k; n<l; n++) {
                             lo0=lo[i,j,k,l];
                             lo1=lo[i,m,k,n];
                             lo2=lo[m,j,k,n];
                             lo3=lo[i,m,n,l];
                             lo4=lo[m,j,n,l];
                             hi0=hi[i,j,k,l];
                             hi1=hi[i,m,k,n];
                             hi2=hi[m,j,k,n];
                             hi3=hi[i,m,n,l];
                             hi4=hi[m,j,n,l];

                             # 3rd argument in max() and min() funtions
                             # is for printing purposes only...
                             lo0=max(lo0, lo1+lo2+lo3+lo4, 0);
                             hi0=min(hi0, hi1+hi2+hi3+hi4, 0);
                             lo1=max(lo1, lo0-hi2-hi3-hi4, 1);
                             lo2=max(lo2, lo0-hi1-hi3-hi4, 2);
                             lo3=max(lo3, lo0-hi1-hi2-hi4, 3);
                             lo4=max(lo4, lo0-hi1-hi2-hi3, 4);
                             hi1=min(hi1, hi0-lo2-lo3-lo4, 1);
                             hi2=min(hi2, hi0-lo1-lo3-lo4, 2);
                             hi3=min(hi3, hi0-lo1-lo2-lo4, 3);
                             hi4=min(hi4, hi0-lo1-lo2-lo3, 4);

                             if(lo0>hi0 || lo1>hi1 || lo2>hi2 || lo3>hi3 || lo4>hi4) {
                                 print "CONTRADICTION AT", i,m,j,k,n,l;
                                 exit;
                             }

                             lo[i,j,k,l]=lo0;
                             lo[i,m,k,n]=lo1;
                             lo[m,j,k,n]=lo2;
                             lo[i,m,n,l]=lo3;
                             lo[m,j,n,l]=lo4;
                             hi[i,j,k,l]=hi0;
                             hi[i,m,k,n]=hi1;
                             hi[m,j,k,n]=hi2;
                             hi[i,m,n,l]=hi3;
                             hi[m,j,n,l]=hi4;
                         }
 }
 print "FINISHED OK";

}

function max(s,t, where) {

if(s<t) {
    print "lo=" st, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);

}

function min(s,t, where) {

if(s>t) {
    print "hi=" st, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);

} '

show/hide this revision's text 1