Ken's POTW


The Difference Pyramid
The University of Central Florida had an excellent Problem of the Week last week. But they don't post solutions. I'd like to accept and post logical solutions to this problem. 

    O
   O O
  O O O
 O O O O
O O O O O
Distribute all the numbers 1 to 15 in the circles so that the number in each circle shows the difference between the two circles on which it sits.

As warm-ups, find solutions for pyramids with 2, 3, or 4 rows.

Source: The UofCF Problem of the Week 2/27/97 The Difference Between Two Circles

Solution:
I have received a solution for this from Bill Chapp and Denis Borris, and Wilfred Theunissen. Wilfred Theunissen wrote a computer program to find all solutions and found only this one. His program is included below. First are the solutions to each of the problems above and my "logical" analysis of the 15 circles. 
      5
    9  4
   2 11  7
 10 12 1  8
13 3 15 14 6

    3
   2 5
  7 9 4
 8 1 10 6

    3
   4 7
  5 9 2
 6 1 10 8

    4
   1 5
  6 7 2
 9 3 10 8

    4
   2 6
  5 7 1
 8 3 10 9

  1
 3 4
5 2 6

  2
 3 5
4 1 6

  3
 1 4
5 6 2

  3
 2 5
4 6 1

 2
1 3
For the 15 circles:
Name the circles with letters: the top circle is A.
Now, A sits on two circles - let the smaller be B and the larger be F.
F sits on two circles, the smaller C, the larger G.
G sits on two circles, the smaller D, the larger H.
H sits on two circles, the smaller E, the larger I.

We can now see the following relationships:
F = A+B
G = A+B+C
H = A+B+C+D
I = A+B+C+D+E
 Since I is the sum of five unique integers, I must be 15 and A thru E must be 1 thru 5.
     A
    F B
   G C L
  H D K .
15 E J . .
Now we need to find the location for the 15. If it goes in a corner, then the numbers 1 thru 5 must lie in the second "diagonal" (B-E) as shown in the figure. The third diagonal (J-L) will then hold numbers between 6 and 9. Since G = 15-J, and the smallest value J can be is 6, the largest value G can be is 9. So the values in F, G, J, K, L must all be within 6-9. There aren't enough numbers, so 15 is not in a corner. 
 1)  A
    F B
   G C  L
  H D  K N
 E 15 J M O

 2)  A
    F  B
   G  C L
  D  H K N
 J 15 E M O

 3)  A
    F  B
   C  G L
  K  H D N
 J 15 E M O

 4)  A
    B  F
   L  G C
  K  H D N
 J 15 E M O
If 15 is in the second spot on the bottom row, there are four possible configurations. In (1) and (2), K and L must be from 6-9, so N must be either 13 or 14, and at least one of M and O would have to be less than 5. In (4), F, M, and N must be from 6-9, so only one of J and K can be, and J+K=15 can't be satisfied. In (3), M, F, J, and K must all be from 6-9, but then N>9 and M+N=O > 15.

So 15 must be in the center position on the bottom row. There are three possible configurations for the locations of A thru E: 
 1)  A
    F  B
   G  C L
  D H  K N
 J E 15 M O

 2)  A
    B  F
   L  G C
  K H  D N
 J E 15 M O

 3)  A
    F  B
   C  G L
  K H  D N
 J E 15 M O
In (1), G=15-J, so G, J, L, and F must be from 6-9. M and N must be above 9, so M+N>15.
In (2), L=15-J, so L, J, N, and F must be from 6-9. M must be above 9, so M+N>15.
Thus, (3) is the only possible configuration for A thru E.

     A
    F  B
   C  G L
  K H  D N
 J E 15 M O
M is between 10 and 14. If M=10 or 11, any value of O would make N<6.
If M=12, O=6 would make N=6, and any other value of O would make N<6.
If M=13, then if O=6, N=7, and L=6. If O=7, N=6, and L=5. Neither is possible. So, M=14 and D=1. If O=8, N=6, and L=5. If O=7, N=7. So O=6, N=8, and L=7. 
      A
    9  B
   C  G  7
  K H  1  8
 J E 15 14 6
Since F must be from 6-9, and 6-8 are already placed, F=9. (A,B) are (4,5) in some order. (C,E) are (2,3).
If E=2, C=3, H=13, G=12, K=10, J=12. But 12 is used twice.
So E=3, C=2, H=12, G=11, K=10, J=13, B=5, and A=4. 
       5
     9  4
    2 11  7
  10 12 1  8
 13 3 15 14 6

Any comments? Feel free to let me know. -KD
Update 7 November 2006: Damien Guichard sent me a URL where he discusses higher orders of these pyramids:
http://perso.orange.fr/alphablock/pages/absolute_triangles_eng.html
Wilfred Theunissen's program: 
/* c programma */

#include 

void main()
{
        int rij5[6];
        int rij4[5];
        int rij3[4];
        int rij2[3];
        int rij1[2];
        int cg[16];
        int i;
        int ok;
        for (i=0;i<=15;i++)
        {
        cg[i]=0;
        }

        for (rij5[1]=1;rij5[1]<=15;rij5[1]++)
        {
        cg[rij5[1]]=1;
        for (rij5[2]=1;rij5[2]<=15;rij5[2]++)
        {
        if (rij5[2] != rij5[1])
        {
        cg[rij5[2]]=1;
        for (rij5[3]=1;rij5[3]<=15;rij5[3]++)
        {
        if ((rij5[3] != rij5[1]) && (rij5[3] != rij5[2]))
        {
        cg[rij5[3]]=1;
        for (rij5[4]=1;rij5[4]<=15;rij5[4]++)
        {
        if ((rij5[4] != rij5[1]) && (rij5[4] != rij5[2]) && (rij5[4] !=
rij5[3]))
        {
        cg[rij5[4]]=1;
        for (rij5[5]=1;rij5[5]<=15;rij5[5]++)
        {
        if ((rij5[5] != rij5[1]) && (rij5[5] != rij5[2]) && (rij5[5] !=
rij5[3]) && (rij5[5] != rij5[4]))
        {
        cg[rij5[5]]=1;
        for (i=1;i<=4;i++)
        {
        rij4[i] = abs(rij5[i+1]-rij5[i]);
        cg[rij4[i]]++;
        }
        for (i=1;i<=3;i++)
        {
        rij3[i] = abs(rij4[i+1]-rij4[i]);
        cg[rij3[i]]++;
        }
        for (i=1;i<=2;i++)
        {
        rij2[i] = abs(rij3[i+1]-rij3[i]);
        cg[rij2[i]]++;
        }
        rij1[1] = abs(rij2[2] - rij2[1]);
        cg[rij1[1]]++;
        ok=0;
        for (i=1;i<=15;i++)
        {
        if (cg[i] != 1)
        {
        ok=1;
        }}
        if (ok == 0)
        {
        printf("        %2d\n",rij1[1]);
        printf("      %2d  %2d\n",rij2[1],rij2[2]);
        printf("    %2d  %2d  %2d\n",rij3[1],rij3[2],rij3[3]);
        printf("  %2d  %2d  %2d  %2d\n",rij4[1],rij4[2],rij4[3],rij4[4]);
        printf("%2d  %2d  %2d  %2d 
%2d\n\n",rij5[1],rij5[2],rij5[3],rij5[4],rij5[5]);
        }
        cg[rij1[1]]--;
        cg[rij2[1]]--;
        cg[rij2[2]]--;
        cg[rij3[1]]--;
        cg[rij3[2]]--;
        cg[rij3[3]]--;
        cg[rij4[1]]--;
        cg[rij4[2]]--;
        cg[rij4[3]]--;
        cg[rij4[4]]--;
                
        cg[rij5[5]]=0;
        }}
        cg[rij5[4]]=0;
        }}
        cg[rij5[3]]=0;
        }}
        cg[rij5[2]]=0;
        }}
        cg[rij5[1]]=0;
        }
                
}
Mail to Ken