Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I saw this problem posted by Google. Those posting in the comments found solutions using computer programming. I would like to know if there is an easier solution than trying every single combination.

The Problem

share|improve this question
2  
Programming a computer is quite an easy solution –  Hagen von Eitzen May 5 '13 at 17:52
    
I know, I did this in class on my Ti-84 calculator. I was wondering if it was possible to do it with only pen and paper had I not had my calculator with me. –  EngieOP May 5 '13 at 18:01
    
Some tricks can be used to make it easier; i.e. not filling in the first digit of A or B with 9, since that would make C < A or C < B –  Sim May 5 '13 at 18:01
1  
You wouldn't have to try EVERY combination. There are some you can eliminate as impossible, e.g. if $A>500$ and $B>500$ (to echo @Sim). That cuts down on the computing time somewhat. –  Ian Coley May 5 '13 at 18:20
    
I changed the title - hope it makes things clearer. –  Mark Bennet May 5 '13 at 19:57

2 Answers 2

up vote 2 down vote accepted

There are a total of $168$ solutions. Given the number of solutions, the best way out seems to be to write a small program to do this for you. Below are the $168$ triplets without ordering. With ordering there are $2 \times 168 = 336$ such triplets. \begin{array}{c|c|c} \text{First Number} & \text{Second number} & \text{Third number}\\ \hline\\ 124 & 659 & 783 \\ 125 & 739 & 864 \\ 127 & 359 & 486 \\ 127 & 368 & 495 \\ 128 & 367 & 495 \\ 128 & 439 & 567 \\ 129 & 357 & 486 \\ 129 & 438 & 567 \\ 129 & 654 & 783 \\ 129 & 735 & 864 \\ 134 & 658 & 792 \\ 135 & 729 & 864 \\ 138 & 429 & 567 \\ 138 & 654 & 792 \\ 139 & 428 & 567 \\ 139 & 725 & 864 \\ 142 & 596 & 738 \\ 142 & 695 & 837 \\ 143 & 586 & 729 \\ 145 & 692 & 837 \\ 146 & 583 & 729 \\ 146 & 592 & 738 \\ 152 & 487 & 639 \\ 152 & 784 & 936 \\ 154 & 629 & 783 \\ 154 & 638 & 792 \\ 154 & 782 & 936 \\ 157 & 329 & 486 \\ 157 & 482 & 639 \\ 158 & 634 & 792 \\ 159 & 327 & 486 \\ 159 & 624 & 783 \\ 162 & 387 & 549 \\ 162 & 783 & 945 \\ 163 & 782 & 945 \\ 167 & 328 & 495 \\ 167 & 382 & 549 \\ 168 & 327 & 495 \\ 173 & 286 & 459 \\ 173 & 295 & 468 \\ 175 & 293 & 468 \\ 176 & 283 & 459 \\ 182 & 367 & 549 \\ 182 & 394 & 576 \\ 182 & 457 & 639 \\ 182 & 493 & 675 \\ 182 & 754 & 936 \\ 182 & 763 & 945 \\ 183 & 276 & 459 \\ 183 & 492 & 675 \\ 183 & 546 & 729 \\ 183 & 762 & 945 \\ 184 & 392 & 576 \\ 184 & 752 & 936 \\ 186 & 273 & 459 \\ 186 & 543 & 729 \\ 187 & 362 & 549 \\ 187 & 452 & 639 \\ 192 & 384 & 576 \\ 192 & 483 & 675 \\ 192 & 546 & 738 \\ 192 & 645 & 837 \\ 193 & 275 & 468 \\ 193 & 482 & 675 \\ 194 & 382 & 576 \\ 195 & 273 & 468 \\ 195 & 642 & 837 \\ 196 & 542 & 738 \\ 214 & 569 & 783 \\ 214 & 659 & 873 \\ 215 & 478 & 693 \\ 215 & 748 & 963 \\ 216 & 378 & 594 \\ 216 & 738 & 954 \\ 218 & 349 & 567 \\ 218 & 376 & 594 \\ 218 & 439 & 657 \\ 218 & 475 & 693 \\ 218 & 736 & 954 \\ 218 & 745 & 963 \\ 219 & 348 & 567 \\ 219 & 438 & 657 \\ 219 & 564 & 783 \\ 219 & 654 & 873 \\ 234 & 657 & 891 \\ 235 & 746 & 981 \\ 236 & 718 & 954 \\ 236 & 745 & 981 \\ 237 & 654 & 891 \\ 238 & 419 & 657 \\ 238 & 716 & 954 \\ 239 & 418 & 657 \\ 241 & 596 & 837 \\ 243 & 576 & 819 \\ 243 & 675 & 918 \\ 245 & 673 & 918 \\ 245 & 718 & 963 \\ 245 & 736 & 981 \\ 246 & 573 & 819 \\ 246 & 591 & 837 \\ 246 & 735 & 981 \\ 248 & 319 & 567 \\ 248 & 715 & 963 \\ 249 & 318 & 567 \\ 251 & 397 & 648 \\ 254 & 619 & 873 \\ 254 & 637 & 891 \\ 257 & 391 & 648 \\ 257 & 634 & 891 \\ 259 & 614 & 873 \\ 264 & 519 & 783 \\ 269 & 514 & 783 \\ 271 & 593 & 864 \\ 271 & 683 & 954 \\ 273 & 546 & 819 \\ 273 & 591 & 864 \\ 273 & 645 & 918 \\ 273 & 681 & 954 \\ 275 & 418 & 693 \\ 275 & 643 & 918 \\ 276 & 318 & 594 \\ 276 & 543 & 819 \\ 278 & 316 & 594 \\ 278 & 415 & 693 \\ 281 & 394 & 675 \\ 281 & 673 & 954 \\ 283 & 671 & 954 \\ 284 & 391 & 675 \\ 291 & 357 & 648 \\ 291 & 384 & 675 \\ 291 & 546 & 837 \\ 291 & 573 & 864 \\ 293 & 571 & 864 \\ 294 & 381 & 675 \\ 296 & 541 & 837 \\ 297 & 351 & 648 \\ 314 & 658 & 972 \\ 317 & 529 & 846 \\ 317 & 628 & 945 \\ 318 & 627 & 945 \\ 318 & 654 & 972 \\ 319 & 527 & 846 \\ 324 & 567 & 891 \\ 324 & 657 & 981 \\ 327 & 519 & 846 \\ 327 & 564 & 891 \\ 327 & 618 & 945 \\ 327 & 654 & 981 \\ 328 & 617 & 945 \\ 329 & 517 & 846 \\ 341 & 586 & 927 \\ 342 & 576 & 918 \\ 346 & 572 & 918 \\ 346 & 581 & 927 \\ 352 & 467 & 819 \\ 354 & 618 & 972 \\ 354 & 627 & 981 \\ 357 & 462 & 819 \\ 357 & 624 & 981 \\ 358 & 614 & 972 \\ 362 & 457 & 819 \\ 364 & 527 & 891 \\ 367 & 452 & 819 \\ 367 & 524 & 891 \\ 372 & 546 & 918 \\ 376 & 542 & 918 \\ 381 & 546 & 927 \\ 386 & 541 & 927 \end{array} And here is the MATLAB code. (Not the most efficient one. Took 12 seconds to run on my comp to produce this list.)

clear all;
clc;
t=0;
for i=1:9
    for j=1:9
        for k=1:9
            if (j~=i && k~=j && k~=i)
                t       =   t+1;
                A(t,1)  =   i;
                A(t,2)  =   j;
                A(t,3)  =   k;
                A(t,4)  =   100*i+10*j+k;
            end
        end
    end
end
count   =   0;
for k1=1:t
     for k2=1:t
         if(isempty(intersect(A(k1,1:3),A(k2,1:3))))
             if(A(k1,4)<A(k2,4))
                 c          =   A(k1,4) + A(k2,4);
                 rowindex   =   find(A(:,4)==c);
                 if (~isempty(rowindex))
                     if(isempty(intersect(A(k1,1:3),A(rowindex,1:3))))
                         if(isempty(intersect(A(k2,1:3),A(rowindex,1:3))))
                             count      =   count+1;
                             B(count,:) =   [A(k1,4),A(k2,4),A(rowindex,4)];
                         end
                     end
                 end
             end
         end
     end
end
share|improve this answer
    
Thank you! I've never used MatLab before. I got the same number of solutions on my calculator program (10~ minutes to calculate) –  EngieOP May 5 '13 at 21:21

Here's some simple and very fast MAGMA code which only tests permutations of $1,\ldots,9$, as opposed to all $9^9$ triplets of $3$-digit combinations. It ran in $3.042$ seconds on my computer.

Z := {@ 1,2,3,4,5,6,7,8,9 @};
S := SymmetricGroup(9);
X := GSet(S,Z);
sol := [];
for s in S do
    Y := X^s;
    A := Y[1]*100 + Y[2]*10 + Y[3];
    B := Y[4]*100 + Y[5]*10 + Y[6];
    C := Y[7]*100 + Y[8]*10 + Y[9];
    if A + B eq C then
        Append(~sol,Y);
        end if;
    end for;

We can make this faster, actually, by noticing that $g+h+i$ must be exactly equal to $18$. Furthermore, we can use a "carrying" method to rule out certain cases early. The following runs in $1.982$ seconds.

Z := {@ 1,2,3,4,5,6,7,8,9 @};
S := SymmetricGroup(9);
X := GSet(S,Z);
sol := [];
for s in S do
    Y := X^s;
    if Y[7] + Y[8] + Y[9] eq 18 then
        u := Y[3] + Y[6];
        if u mod 10 eq Y[9] then
            v := Floor(u/10) + Y[2] + Y[5];
            if v mod 10 eq Y[8] then
                w := Floor(v/10) + Y[1] + Y[4];
                if w eq Y[7] then
                    Append(~sol,Y);
                    end if;
                end if;
            end if;
        end if;
    end for;
share|improve this answer
    
Thanks! I've never heard of MAGMA before :o –  EngieOP May 5 '13 at 21:35
    
Actually, my MATLAB code doesn't do all the $9^9$ permutations. It first stores the numbers with distinct digits. Anyway, yours check is orders faster. +1. –  user17762 May 5 '13 at 21:36
1  
@user17762 Thanks! That sentence was a response not to your MATLAB code but to OP's request for code which "doesn't try every single combination." –  Alexander Gruber May 5 '13 at 21:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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