7
$\begingroup$

All the whole numbers 1−9 are placed in the 9 triangular cells. A negative sign is placed in front of some numbers. The letters A−F are products of 3 or 5 of the numbers. Find all possible solutions.

A=320 B=162 C=6048 D=−60 E=756 F=−240

click here to view diagram

$\endgroup$
5
$\begingroup$

Completed grid without minus signs:

enter image description here

Signs:

One possibility is that 5 is negative and all others are positive. [EDITED to add:] No, wait, that's nonsense; thanks to "w l" for pointing that out in comments. Instead, take the following configuration: 6,3,7 are negative, all others positive. There are then three independent changes we can make that leave all the given products unchanged: we can flip the signs of all three corners (1,2,7); we can flip the signs of all of 8,6,4,3; we can flip the signs of all of 5,8,3,9. (You might look at those last two and say "what about the third option: 5,4,6,9?" That one's good too, but it's not independent: it's the same as doing both of the last two.)

Sketch of solution process:

Let's begin by ignoring the +/- signs. First of all, it's easy to get the corners: we know the product of all the cells, and then pairs like A,B give us the product of "all but X" for each corner X. Now we can look at the three remaining cells on each long side, and pin down what numbers have to be there; e.g., the remaining cells on the NW side have a product of 160, which can be implemented only as 4x5x8. The rest is straightforward.

We then

have to figure out the signs. There are 9 cells and 6 constraints on the signs (which you can think of as linear relations over the field with 2 elements, if you're feeling fancy) and it's fairly clear that they're independent: so there must be 9-6=3 independent things you can do without changing the signs of the given products, and a little trial and error suffices to discover what they are. Then we just need to find one configuration of signs that gives the right results. Considering once again the products of all numbers and all-but-a-corner, we see that the SE corner has to differ from the other two; let's make it negative and the others positive. The given products have a symmetry about the obvious line through that corner, so let's look for patterns symmetrical about that line. Then it's just a little trial and error again.

$\endgroup$
  • $\begingroup$ Having only the 5 negative does not work, because then A would be negative as well. It might also be nice to add the simplified constraints: same sign: 2 and 1 as well as 5 and 9; different sign: 8 and 3, 6 and 4 as well as 1 and 7 (plus any of the original constraint). $\endgroup$ – w l Mar 7 '18 at 10:00
  • $\begingroup$ Oops, you're right. Will fix the discussion of signs. ... Now done; thanks! $\endgroup$ – Gareth McCaughan Mar 7 '18 at 10:18
  • $\begingroup$ Just wanted to add this remark on solving the numbers without the sign: 5 and 7 have only 1 multiple in the range of numbers we have to use, so looking at which products they divide (A, F and D for 5, and C and E for 7), you know where to put them. $\endgroup$ – Florian Bourse Mar 7 '18 at 10:53
  • $\begingroup$ Yup. (My answer was kinda sketchy on the details, but that was indeed part of the mental process.) $\endgroup$ – Gareth McCaughan Mar 7 '18 at 10:57
2
$\begingroup$

Here's verification that Gareth's solution is unique. I wrote a C program that just runs through every combination, with just about no smarts to speed it up since it just wasn't required. It found just the one given solution, runtime 5 milliseconds. The variables i0 through i8 correspond to triangle locations 7 012 65438

I modified it to output all possible sets of targets, and sorted them in order of "smallest total difference between all length 3 products and all length 5 products" (ie add up three differences between the three length 5 products and the three differences between the three length 3 products) and the smallest was a sum of 92, with length 6 targets (1120,1134,1152) and length three targets (40,45,54). I also checked how many sets of targets had multiple solutions. Of the 322560 sets of targets, 309888 were distinct, with 309840 being unique, 12433 having two solutions, and 48 having 6 solutions. Examples of target sets with 6 solutions are (6048, 12, 1080, 48, 840, 48) and (1680, 24, 2160, 24, 3024, 24)

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int targets[6]={320,162,6048,60,756,240};

int maxval=9;
int minval=1;

unsigned long Total_secs;                   // time run so far
int Milli_secs;                     // plus millisecs
static long starttime;

// Gets the system time

void Time(int First)
{
    static clock_t ticks, lticks;

    ticks = clock();
    if (First != 1)
    {
        double  Tsecs;
        Tsecs = ((double) ticks-lticks) / CLK_TCK;
        Total_secs += (unsigned long) Tsecs;
        Milli_secs += (int) (1000.0 * (Tsecs - (double) ((unsigned long) Tsecs)));
        if (Milli_secs >= 1000)
        {
            Milli_secs -= 1000;
            Total_secs++;
        }
        if (Milli_secs < 0)
        {
            Milli_secs += 1000;
            Total_secs--;
        }
    }
    else
    {
        Total_secs = 0;
        Milli_secs = 0;
    }
    lticks = ticks;
}

void main(int argc, char **argv)
{
    int i0,i1,i2,i3,i4,i5,i6,i7,i8,isols=0;

    Time(1);                                    // Initialise time registers
    for (i0=minval;i0<=maxval;i0++)
    {
        for (i1=minval;i1<maxval;i1++)
        {
            if (i1==i0) continue;
            for (i2=minval;i2<=maxval;i2++)
            {
                if (i2==i0 || i2==i1) continue;
                if (i0*i1*i2 != targets[5]) continue;
                for (i3=minval;i3<=maxval;i3++)
                {
                    if (i3==i0 || i3==i1 || i3==i2) continue;
                    for (i4=minval;i4<=maxval;i4++)
                    {
                        if (i4==i0 || i4==i1 || i4==i2 || i4==i3) continue;
                        if (i2*i3*i4 != targets[1]) continue;
                        for (i5=minval;i5<=maxval;i5++)
                        {
                            if (i5==i0 || i5==i1 || i5==i2 || i5==i3 || i5==i4) continue;
                            if (i0*i4*i5 != targets[3]) continue;
                            for (i6=minval;i6<=maxval;i6++)
                            {
                                if (i6==i0 || i6==i1 || i6==i2 || i6==i3 || i6==i4 || i6==i5) continue;
                                for (i7=minval;i7<=maxval;i7++)
                                {
                                    if (i7==i0 || i7==i1 || i7==i2 || i7==i3 || i7==i4 || i7==i5 || i7==i6) continue;
                                    if (i6*i5*i0*i1*i7 != targets[0]) continue;
                                    for (i8=minval;i8<=maxval;i8++)
                                    {
                                        if (i8==i0 || i8==i1 || i8==i2 || i8==i3 || i8==i4 || i8==i5 || i8==i6 || i8==i7) continue;
                                        if (i7*i1*i2*i3*i8 != targets[2]) continue;
                                        if (i8*i3*i4*i5*i6 != targets[4]) continue;
                                        isols++;
                                        printf("Sol %d\n", isols);
                                        printf("  %1d  \n",i7);
                                        printf(" %1d%1d%1d \n",i0,i1,i2);
                                        printf("%1d%1d%1d%1d%1d\n", i6,i5,i4,i3,i8);
                                    }
                                }
                            }
                        }                       
                    }
                }
            }
        }
    }       
    printf("Found %d sols\n",isols);
    Time(2);
    printf("Time taken: %d.%d\n", Total_secs, Milli_secs);
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.