POTW Returns!

After taking last week off, Problem of the Week returns. This week's problem has several possible answers, so even after a solution gets posted you can feel free to look for others. In fact, I'd be curious to know the various approaches people took to solve the problem. Did anyone come up with anything more clever than trial and error?

More like this

The cool part at the end even holds for other bases than base-10. If Max(n,m) is the largest m-digit number of base n of this form, i.e. Max(10,4) would be 9876, and Min(n,m) is the smallest, then the relation Max(n,m) = (n-2)*Min(n,m)+m always holds.

"Actaully, there are several possible solutions to this one"

I get, using an exhaustive search, and depending on what one considers a different solution, either, 336, 162, or 42 different solutions.

The number of solutions is a multiple of four, because

ABC+DEF=ABF+DEC=AEC+DBF=AEF+DBC

I found 42 such sets of 4 for a total of 168 solutions. Half of which have a carry from the ones place to the tens, the other half carry from the tens to the hundreds. (There are no solutions with zero or two carries.)

By the way, I'd show my work, but I think it's too much for a blog comment. At any rate, with a maximum of 9!/2 (181440) possible tests of ABC+DEF=GHI from ABC=123 to ABC=498, coding up and running the brute-force method would probably have been much faster than the "clever" method I used.

Oops. I have a typo in my previous post. As Dave W. has, the correct number is 168, not 162.

Certainly this can be searched thoroughly by coding up a search. However, several answers can be found by trial arrangements. Noticing that smaller digits in the hundreds column and that one column may have a carry leads to several answers rather quickly. One is 367+128= 495. Once you try the 7+8 in the ones column the rest falls out easily.

Oh, forgot to add that the solution I give actually provides multiple trivial variant answers (swap order of digits in the columns and swap the hundreds column to the ones column etc.)

Each solution does allow for eight trivial variants by swapping the digits in the columns. Thus George's answer 367 +128 = 495 also gives 368 + 127 = 495, 327 + 168 = 495, etc. There are 42 such answers, each giving eight variants, for 336 different variant solutions.

However, swapping the one's and hundreds column does not in general give another solution. Swapping the ones and hundreds column in the answer above does not produce an answer (763 + 821 = 1584).

We know empirically that every answer has exactly one carry, either out of the ones column or out of the tens column. If the carry is out of the one's column (as in the answer above), swapping the ones column with the hundreds column will not produce an answer, as the carry out of the ones column would thus become a carry out of the hundreds column into the thousands column, and is thus not an answer.

With a carry out of the tens column, there are a few answers in which swapping the ones and hundreds column will produce another answer (241 + 596 = 837 and 142 + 695 = 837, for example), but this is not generally true: 173 + 295 = 468 is an answer, but 371 + 592 = 963, which is not an answer.

So while such pairs of answers with swapped columns do exist, such pairs of answers with swapped columns are not usual; less than half the cases will produce another answer by swapping columns.

Rick, I submit that the trivial variants where the hundreds column is swapped does nothing more than swap the two numbers being added, and since addition is commutative, those are not distinct solutions to the problem as stated. In other words, while 128+367=495 is a solution, 367+128=495 is not a different solution, but precisely the same solution ("three, three-digit numbers such that one of them is the sum of the other two"). So instead of eight trivial variants for each solution, there are only four.

The swapping of entire columns is already covered by the 42 "basic" solutions and their variants. My method of finding solutions finds ABC+DEF=GHJ where ABC<DEF and ABC<ABF and ABC<AEC and ABC<AEF. So the trivial variants all have the first three-digit number larger than the "basic" solution. With that in mind, there is no solution "smaller" than 124+659=783, and there is no solution "larger" than 386+541=927 (which, interestingly, is not a variant of the "largest" "basic" solution, 352+467=819).

Dave:
It depends upon what one counts as a solution.

We have ABC + DEF = GHI.

128 + 367 = 495 is a solution, with A = 1, B = 2, C = 8, etc. 367 + 128 = 495 is also a solution, with A = 3, B = 6, C = 7, etc. Since the digits assigned to each letter are different, the two cases are, in this sense, different solutions. There are 336 solutions under this definition of "different solutions".

You are certainly correct that 128 + 367 = 495 and 367 + 128 are, by the commutative property of addition, simple variants of each other, and certainly can be counted as "the same solution". There are, by this definition, 168 "different solutions". But it is also reasonable to talk of the two variants of each solution, differing in the order of the two addends.

However, the commutative property of addition in this case goes further, to each column of digits independently. Thus we have eight variants:
128 + 367 = 495
127 + 368 = 495
168 + 327 = 495
167 + 328 = 495
328 + 167 = 495
327 + 168 = 495
368 + 127 = 495
367 + 128 = 495
Since these are all simply rearrangements of the numbers in a way that, due to the commutative property of addition, will necessarily produce the same sum and thus if one is a solution the other seven will also be. Thus, by this definition, there are 42 "different solutions", each with eight variants.

I would suggest that all three of these definitions are each reasonable in their own way, and none of them are "wrong" or "the only right" answer.

Rick, in the context of Problem Nine, I have to disagree that the other two definitions of a solution are reasonable. Again, the problem, verbatim:

"Using the digits from 1–9 exactly once each, form three, three-digit numbers such that one of them is the sum of the other two."

It seems obvious that the problem doesn't say anything about the order of addends. Thus, {128,367,495}, {128,495,367}, {367,128,495}, {367,495,128}, {495,128,367} and {495,367,128} are all the same solution. However, {127,368,495} is a distinct solution (even though it's a "trivial" rearrangement of the prior solution), because it's a different set of three numbers.

So far I have 4 basic formulations I call 9/8, 9/7, 8/7 and 8/6. These refer to the column with a carry. That is 9+8 = 7 and a carry for example for 9/8.

Each has 16 trivial variants by arranging the digits and columns. So that gives 64 answers.

There could be more answers but I did not find any so far. A brute for computer search could determine if there are more. So far I do not have a rigorous way to determine if this is all the solutions or not.

Constraint satisfaction problem. The issue is how to rapidly cull possibilities from the solution space. I recognized that constraints propagate from right to left in a sum, and also that at least one carry would be required. I decided to force carries from the outset. I went from

___
___
___ {1, 2, ..., 9}

to

__9
__8
__7 (carry 1) {1, 2, ..., 6}

to unsatisfiable

_69
_58
_27 (carry 1) {1, 3, 4}

It was quite easy to backtrack and repair. I won't pretend to have worked algorithmically at this point. The important thing is that I had methodically eliminated most of the possible solutions.

218
349
567

By Tom English (not verified) on 13 Nov 2014 #permalink

P.S.--I should have said a bit more about constraints, and lack thereof. When a column does not propagate a carry, the digit at the bottom is bigger than the other two. The left column cannot propagate a carry, and that's why I forced carries early. The ordering of the top two digits in a column does not matter. Thus when I got to the leftmost column, with just three digits remaining, I had only one question to answer: is the carry plus the smaller two digits equal to the biggest?

By Tom English (not verified) on 13 Nov 2014 #permalink

I was not able to get completely to solutions analytically, but I was able to get partially there. We know that the sum of the digits from 1-9 is 45. Let ABC + DEF = GHI. Further,
let x = A+B+C+D+E+F and y=G+H+I. Now, if there are no carries, it is clear that x=y. Since x+y=45 and x-y=0, adding those two equations gives 2x=45 or x = 22.5, which is impossible since x is the sum of integers. Thus, there must be at least one carry.

If there are two carries, then they must be in the ones and tens places. Thus C+F = 10+I, 1+B+E = 10+H, and 1+A+D = G. Thus 2+x = 20+y, yielding x-y=18. Since x+y = 45, adding the last two equations gives 2x = 27 or x=13.5, which again is impossible since x is the sum of integers.

This implies that there must be exactly one carry. This can be in either the ones or the tens place. For the following, I will assume the carry is in the ones place. It will not matter for my conclusion whether it is in the ones or the tens place. Now, a carry in the ones place implies that C+F = 10+I, 1+B+E = H and A+D=G. This yields x+1 = 10+y or x-y=9. Adding that to the equation x+y=45 gives 2x=54 or x=27. That implies that y=18. Therefore, the solutions to the problem will all have the sum of the three digits in the answer equal to 18.

It is fairly easy to generate solutions from that point by trial and error. For instance 9+7+2 = 18 so there should be a solution with those three digits as the answer. We know we need one carry, so select 8+4=12 to account for the two in the answer. 5+1 plus the carry gives the 7 and the remaining digits 6+3=9 so one solution would be 658 + 314 = 972. Obviously, as well noted above, other solutions can be generated from this one by swapping digits in the addends.

I'm sure with enough work, someone could come up with a single formula with 168 roots, the decimals of which represent solutions to the problem. But otherwise, it's just a matter of how much brute force needs to be applied.

Sean T wins. The sum of the digits of the sum have to equal 18. Here is the exhaustive list:

475 + 218 = 693
418 + 275 = 693
415 + 278 = 693
493 + 182 = 675
492 + 183 = 675
483 + 192 = 675
482 + 193 = 675
394 + 281 = 675
391 + 284 = 675
384 + 291 = 675
381 + 294 = 675
439 + 218 = 657
438 + 219 = 657
419 + 238 = 657
418 + 239 = 657
397 + 251 = 648
391 + 257 = 648
357 + 291 = 648
351 + 297 = 648
487 + 152 = 639
482 + 157 = 639
457 + 182 = 639
452 + 187 = 639
378 + 216 = 594
376 + 218 = 594
318 + 276 = 594
316 + 278 = 594
394 + 182 = 576
392 + 184 = 576
384 + 192 = 576
382 + 194 = 576
439 + 128 = 567
438 + 129 = 567
429 + 138 = 567
428 + 139 = 567
349 + 218 = 567
348 + 219 = 567
319 + 248 = 567
318 + 249 = 567
387 + 162 = 549
382 + 167 = 549
367 + 182 = 549
362 + 187 = 549
368 + 127 = 495
367 + 128 = 495
328 + 167 = 495
327 + 168 = 495
359 + 127 = 486
357 + 129 = 486
329 + 157 = 486
327 + 159 = 486
295 + 173 = 468
293 + 175 = 468
275 + 193 = 468
273 + 195 = 468
286 + 173 = 459
283 + 176 = 459
276 + 183 = 459
273 + 186 = 459

By Another Matt (not verified) on 13 Nov 2014 #permalink

Another Matt: where's 478+215=693?

And all the solutions with totals above 693, like 124+659=783 or 291+546=837 or 357+624=981?

Ooops, copy/paste malfunction. Here's the exhaustive list for the reals (I mean for the integers):

746 + 235 = 981
745 + 236 = 981
736 + 245 = 981
735 + 246 = 981
657 + 324 = 981
654 + 327 = 981
627 + 354 = 981
624 + 357 = 981
658 + 314 = 972
654 + 318 = 972
618 + 354 = 972
614 + 358 = 972
748 + 215 = 963
745 + 218 = 963
718 + 245 = 963
715 + 248 = 963
738 + 216 = 954
736 + 218 = 954
718 + 236 = 954
716 + 238 = 954
683 + 271 = 954
681 + 273 = 954
673 + 281 = 954
671 + 283 = 954
783 + 162 = 945
782 + 163 = 945
763 + 182 = 945
762 + 183 = 945
628 + 317 = 945
627 + 318 = 945
618 + 327 = 945
617 + 328 = 945
784 + 152 = 936
782 + 154 = 936
754 + 182 = 936
752 + 184 = 936
586 + 341 = 927
581 + 346 = 927
546 + 381 = 927
541 + 386 = 927
675 + 243 = 918
673 + 245 = 918
645 + 273 = 918
643 + 275 = 918
576 + 342 = 918
572 + 346 = 918
546 + 372 = 918
542 + 376 = 918
657 + 234 = 891
654 + 237 = 891
637 + 254 = 891
634 + 257 = 891
567 + 324 = 891
564 + 327 = 891
527 + 364 = 891
524 + 367 = 891
659 + 214 = 873
654 + 219 = 873
619 + 254 = 873
614 + 259 = 873
739 + 125 = 864
735 + 129 = 864
729 + 135 = 864
725 + 139 = 864
593 + 271 = 864
591 + 273 = 864
573 + 291 = 864
571 + 293 = 864
529 + 317 = 846
527 + 319 = 846
519 + 327 = 846
517 + 329 = 846
695 + 142 = 837
692 + 145 = 837
645 + 192 = 837
642 + 195 = 837
596 + 241 = 837
591 + 246 = 837
546 + 291 = 837
541 + 296 = 837
576 + 243 = 819
573 + 246 = 819
546 + 273 = 819
543 + 276 = 819
467 + 352 = 819
462 + 357 = 819
457 + 362 = 819
452 + 367 = 819
658 + 134 = 792
654 + 138 = 792
638 + 154 = 792
634 + 158 = 792
659 + 124 = 783
654 + 129 = 783
629 + 154 = 783
624 + 159 = 783
569 + 214 = 783
564 + 219 = 783
519 + 264 = 783
514 + 269 = 783
596 + 142 = 738
592 + 146 = 738
546 + 192 = 738
542 + 196 = 738
586 + 143 = 729
583 + 146 = 729
546 + 183 = 729
543 + 186 = 729
478 + 215 = 693
475 + 218 = 693
418 + 275 = 693
415 + 278 = 693
493 + 182 = 675
492 + 183 = 675
483 + 192 = 675
482 + 193 = 675
394 + 281 = 675
391 + 284 = 675
384 + 291 = 675
381 + 294 = 675
439 + 218 = 657
438 + 219 = 657
419 + 238 = 657
418 + 239 = 657
397 + 251 = 648
391 + 257 = 648
357 + 291 = 648
351 + 297 = 648
487 + 152 = 639
482 + 157 = 639
457 + 182 = 639
452 + 187 = 639
378 + 216 = 594
376 + 218 = 594
318 + 276 = 594
316 + 278 = 594
394 + 182 = 576
392 + 184 = 576
384 + 192 = 576
382 + 194 = 576
439 + 128 = 567
438 + 129 = 567
429 + 138 = 567
428 + 139 = 567
349 + 218 = 567
348 + 219 = 567
319 + 248 = 567
318 + 249 = 567
387 + 162 = 549
382 + 167 = 549
367 + 182 = 549
362 + 187 = 549
368 + 127 = 495
367 + 128 = 495
328 + 167 = 495
327 + 168 = 495
359 + 127 = 486
357 + 129 = 486
329 + 157 = 486
327 + 159 = 486
295 + 173 = 468
293 + 175 = 468
275 + 193 = 468
273 + 195 = 468
286 + 173 = 459
283 + 176 = 459
276 + 183 = 459
273 + 186 = 459

By Another Matt (not verified) on 13 Nov 2014 #permalink

Sorry I beat you to it. You get way more credit than I do for the work you did, and for the systematic organization. I'd be willing to erase my previous posts and defer.

Cheers

By Another Matt (not verified) on 13 Nov 2014 #permalink

In reply to by Dave W. (not verified)

Nonono, no sweat. Different methods, same results, it's all good.

I was just going to wait until after the "due date" to spill everything, but I just realized that this problem probably has lots of solutions written all over the Interwebs.

Consider a solution to
ABC
DEF
----
GHI

due to the commutative propery, swapping the two digits in any column of the addends will not change the presence of any of the digits int he addends and will not change the sum, so this gives eight variants for any solution.

We know that there is exactly one carry, so for the three columns of the problem one will generate a carry, one will receive a carry, and one will neither generate nor recieve a carry. It is clear that the leftmost (hundreds) column cannot be the column that generates the carry, and the rightmost (ones) column cannot be the one that receives the carry. Further, the column that receives the carry must be to the immediate left of the one one that generates the carry.

So the column that generates the carry has three digits, two in the addends and one in the sum. Moving this column from the ones column to the tens column, or vice versa, does not change this. Similarly, the column that recieves the carry, if it is to the immediate left of the column that generates the carry, has three digits and, since the carry is still recieved, the two addend digits do not change and the sum digit also does not change. So the two columns that involve the carry will not change the digits present if they are in the hundreds and tens place, or in the tems and ones place. The column that neither generates nor receives the carry will not change if it is in the ones or hundreds place, and will complete the set of all nine digits.

Thus, for any given solution, there is another solution can be obtained by moving the column that generates the carry from the ones to tens place, or from the tens to the ones place. Then move the column that recieves the carry to the immediate left of the carry-generating column, and fill the last column with the remaining column.

Thus, for

Oops. accidentally submitted too early. Anyway, to continue:

Thus for the solution
162
783
---
945

the tens column generates the carry, so move it to the ones place, place the column that receives that carry to its immediate left, and fill the remaining column with whats left:

216
378
---
594

This is equivalent to a roll to the right. If the carry is generates in the ones column, a roll to the left.

We can then swap the digits in the columns of the addend as before to produce 7 additional variants.

Thus for any answer we can, by simply rearranging the digits, obtain 15 additional solutions.

This reduces the number of sets of solutions from 42 sets of eight to 21 sets of sixteen.

My analysis above showing that all solutions have a sum whose digits total 18 also gives a fairly elegant way to determine the total number of solutions. First, we must find the number of possible combinations of digits (without regard to order) that would total 18. These would be the sets {9,8,1}, {9,7,2}, {9.6,3}, {9.5,4}, {8.7,3}, {8,6,4}, and {7,6,5}. That is a total of 7 such sets. Now, realize that each permutation of these sets gives a solution, and that for each permutation, the commutative property (as amply discussed already) allows for 4 total solutions. Thus, there must be 7x6x4 = 168 solutions to the problem.

I just read your post Rick. See mine. In a sense, we could really say that there are only 7 solutions, with each one having 24 variations!

There are exactly 218 different three-digit numbers (TDNs) found in the solutions. 187 are only found as addends, 24 are only found as sums, and seven found as both addends and sums. The TDNs found as addends only are found in quantities of 1, 2, 3, 4 or 6. The TDNs found as sums only are found in quantities of 4 or 8 (of course). TDNs found as both are found in quantities of 9 (567, 675, 783), 6 (576, 657), or 5 (729, 738). [Rick can multiply these quantities by two.]

34 of the TDNs have digits which total to 18, but 297, 378 and 387 are never seen as sums. 4 of the TDNs have digits totaling only 7, and another 4 have digits totaling 20 (the min and max digit totals). The next-most common digit total to 18 is 16, with 26 TDNs.

The longest string of sequential TDNs seems to be 234 through 239.

Followup problem:

In hexadecimal, take the numbers 0-F and make four four-digit numbers such that one is the sum of the other three (or alternatively, so that two are the sum of the other two). No numbers beginning with 0 allowed.

By Another Matt (not verified) on 13 Nov 2014 #permalink

For what it's worth, this is a list of my 21 solutions:
1: 127 + 359 = 486
2: 127 + 368 = 495
3: 128 + 439 = 567
4: 218 + 349 = 567
5: 216 + 378 = 594
6: 218 + 439 = 657
7: 215 + 478 = 693
8: 124 + 659 = 783
9: 214 + 569 = 783
10: 134 + 658 = 792
11: 317 + 529 = 846
12: 125 + 739 = 864
13: 214 + 659 = 873
14: 234 + 657 = 891
15: 324 + 567 = 891
16: 317 + 628 = 945
17: 216 + 738 = 954
18: 215 + 748 = 963
19: 314 + 658 = 972
20: 235 + 746 = 981
21: 324 + 657 = 981

Each one generates 16 variations, for the total of 21 * 16 = 336 (setting aside the philosophical discussion of whether or not 324 + 657 can be counted as a different solution than 567 + 324).

Sean:
I don't think it is correct that "each permutation of these sets gives a solution". For example, the set {9,8,1} does not admit to a solution for the permutations 189 or 198; clearly the first digit in the answer must be at least 3.

Another Matt, what's wrong with a leading zero?

Another Matt:

"...(or alternatively, so that two are the sum of the other two)."

The lowest-hanging fruit: C840+FB73=D951+EA62. Did that one in my head. I think that also provides the highest possible sum, 1C3B3.

What makes this easy is that the carries don't matter (and, as above, the sum can be five digits). Since the sum itself isn't a part of the solution space, we only need to ensure that the column additions of both pairs have the _same_ carries, it doesn't matter what they are.

So, given that for any four sequential integers W, X, Y and Z, it's true that W+Z=X+Y, the easiest solution to find is, for the 1s column, set W=0, for the 10s column, set W=4, for the 100s column, set W=8 and for the 1000s column, set W=C. Since these four sets of four sequential integers don't overlap, there's no possibility of digit re-use.

You can get 18 more solutions by swapping entire columns around (gotta keep the zero out of the 1000s column, otherwise there'd be 24 column swaps), and another 64 by swapping W for Z or X for Y in the 1s, 10s and 100s columns (swapping the 1000s columns just inverts the additions), so each solution comes with another 1151 trivial variations (or 4603 per RIck's philosophy).

I've got a more general algorithm to find all solutions, but don't have the time to write it up.

Shoot, we can make another within-column swap, from W+Z=X+Y to X+Y=W+Z in the three lowest columns, so that's 18 whole-column swaps with 512 within-column swaps each, for a total of 9215 trivial variations (or 36863) for each "basic" solution.

Sean:

This is what I get the number of solutions in each of the sets of possiblities of summing to 18, (using 336 as the number of solutions; you can divide by two for the 168 manner of counting).

{9,8,1} : 64
{9,7,2} : 32
{9,6,3} : 32
{9,5,4} : 64
{8,7,3} : 48
{8,6,4} : 48
{7,6,5} : 48

For the two pairs of four-digit hex numbers problem, you just need to find all combinations of four sets {W,X,Y,Z} where W+Z=X+Y which use all the digits once. If the "first" set of each has W=0, and W+Z for each set is less than or equal to W+Z for the next set, I think you're guaranteed to generate each set of four only once. After that, the within-column and whole-column swaps won't create duplicate solutions.

Thanks Rick. I got lazy and just assumed that the condition that the sum of the digits in the answer must be 18 was a sufficient condition for a solution. It's a necessary condition, but not sufficient obviously.

Okay, I think there are 1990 "basic" solutions to TPFDHN. Times 9216 variations equals 18339840 total solutions.

#15 Sean T

You lose me with x-y = 0? This is not the case? My one solution shows this.

George,

x-y=0 came up while I was considering the case in which there are no carries. This comes about in this case because if there are no carries, then the sum of the digits of the two addends (x) must be equal to the sum of the digits of the answer (y). Since x=y, x-y=0. I went on to prove that if there are no carries, 2x=45, which is not possible given the constraints of the problem. Therefore, the reason you don't see x-y=0 in your solution is that equation only applies to an impossible case. Your solution must contain exactly one carry (since in considering the case of two carries, we also are led to 2x = an odd value).

George,

BTW, if you reread my original post, you will see that for all solutions, x-y=9. That must be the case with your solution. Further, it must also be true for your solution (and any solution) that x=27 and y=18.

#38 Sean

Thanks for the reply and the patience with me. But I do not get it? I get that A+B+C ..+I = 45. I take your x=A+B+C+D+E and y=G+H+I.

Thus x+y = 45. So far so good.

For any solution: ABC + CDE = GHI

Now there is no carry, what I do not get is why then:

A+B+C+D+E+F must equal G+H+I ??

This is the bit I need help understanding?

Thanks

George, X=Y because A+D=G, B+E=H and C+F=I. Substitute, and you get A+B+C+D+E+F=A+B+C+D+E+F.

Sorry for the misunderstanding, George. Dave W. has it precisely correct. I got there by adding Dave's 3 equations together, namely A+D+B+E+C+F = G+H+I. Recall that I had defined x as the sum of the six digits making up the addends and y as the sum of the three digits making up the sum. Thus the left side of that equation is just equal to x and the right is equal to y, hence x=y. Of course, that is only valid if there are no carries. All solutions will have exactly one carry, so you won't see any solution with x=y.

Sean T, in Another Matt's follow-up, "In hexadecimal, take the numbers 0-F and make four four-digit numbers such that one is the sum of the other three..." your trick to finding the carries should work there, too, correct? But in that case, X+Y=120, and odd numbers of carries are impossible due to fractional X. I mean, I think I extended your idea correctly, I would just like confirmation.

(Interestingly, for the no-carry scenario, Y=60, but the highest sum of four hex digits is only 54, so no-carry is ruled out for this problem, too. You can also have many carries: a 1 carried from the 1s place, another 1 carried from the 10s place, and a 2 carried from the 100s place, for example.)

Thanks Sean & Dave. It sank through the thick skull. Got it.

Dave,

I have not worked through Matt's problem, but it seems to me that it's a bit more complex. With three hexadecimal digits, we must account for the fact that any carry value is not necessarily 1; a carry of 2 is possible (eg. A+B+C = 21 in hexadecimal). If you have a single carry of 2, you wind up with the equation 2+x = 32+y, which gives x-y =30. Since x+y=120, that gives x=45, so a single "2" carry is possible.

I would generalize that the total value of the carries must be even for a solution to be possible. The difference between this problem and the POTW is based on the fact that the sum of the digits from 1-9 is odd, whereas the sum of the hexadecimal digits 0-F is even. In general, for problems such as this, the parity of the total of the carry values must be the same as the parity of the sum of all the digits used.

I do agree, though, that the case of zero carries in Matt's problem is ruled out. The sum of four distinct hexadecimal digits does indeed have a maximum possible (decimal) value of 54.

Sean T, I think that not only is a single carry of 2 possible, I think two carries of 1 each is possible. I think any even total is possible across three columns, so even 1, 2, and 1. Or even three 2s... er, nope. F+E+D=2A, C+B+A=21, but 9+8+7=18, so it's impossible to get three columns to all have carries of 2.

Whoops, nevermind. F+B+6=20, E+C+7=21 and D+A+9=20, so there's plenty of situations with three carries of 2 each.

Dave,

Actually, we need to keep in mind that the carry values are hexadecimal carry values, not decimal ones. That is, we must have a sum of 32 or greater to get a carry value of 2. Your example would be three caries of 1 each: F+B+6=14, E+C+7=15, and D+A+9=14 in hexadecimal. You can get 3 carries of 2 each, such as F+A+7=20, E+B+8=21 and C+D+9=22 (all in hexadecimal). I haven't worked out if there's a solution to Matt's problem using any of these, though. All I am claiming is that for any solution to Matt's problem, the sum of the carries must be even.

Dave,

To clarify, if x is the number of "one carries" and y is the number of "two carries", then either x=0 or x=2. If x=0, then 1<=y<=3. If x=2, then 0<=y<=1.

Sean T, my F+B+6=20 was all in hex, which your F+A+7=20 confirmed (considering A is one less than B and 7 one greater than 6).

Sorry Dave, I'm not sure why I was reading your post in decimal. Guess I'm not used to dealing with hex. Obviously, with that in mind, I just gave a second example of a case where there are three "2 carries".

Ha ha. I work in base 12 all the time for my compositions. Well, actually, it's mod 12. It can take a while to get used to 5+7≡0 or 8+A≡6 for sure.

By Another Matt (not verified) on 17 Nov 2014 #permalink

It actually occurred to me that Another Matt's extension of the POTW is really not a truly analogous problem, but rather a subtly different one. The analogous problem would be to find four four-digit base-17 numbers such that all 16 digits (1-G, if you like) are used exactly once and the sum of three of them equals the fourth. This may seem like a minor difference, but it actually makes things interesting, IMO.

Consider an arbitrary generalization of the problem. Namely, for any integer n>=3, find n base n^2+1 numbers with n digits each such that each of the n^2 digits is used exactly once and such that the sum of n-1 of these numbers is equal to the remaining one. What I find interesting about this generalization is that the problem behaves quite differently depending on whether n is odd or even.

In general, let x = the sum of all the digits of the addends and y = the sum of the digits in the remaining number. The sum of all the digits in the problem is the sum of all the digits from 1 to n, or 1/2 * n(n+1) = 1/2(n^2+n). Let k be equal to this value. As defined, therefore, x+y=k. Now, for any base, let b be that base (equal to n^2+1), and let c be the total of all the carry values. That gives the equation x+c = y+bc. (If this is not clear, consider the summation of individual columns. Either the digit in the sum is equal to the sum of the addend digits in that column, or it's equal to the sum of the addend digits - some multiple of the base; ie the carry value). Rearranging, x-y = c(b-1). Adding to the first equation gives 2x = k + c(b-1). Since we are dealing with integers, the value k+b(c-1) must be even.

Now consider an even base (ie. an odd value of n). For an even base, k is odd*. Therefore,c(b-1) must be odd. Therefore, c must be odd, which is the result I obtained for the original POTW in base 10.

Now consider an odd base (even n). For an odd base, k is even**. Therefore c(b-1) must also be even. Since the base is odd, b-1 is even. Therefore c(b-1) is always guaranteed to be even, and we cannot conclude anything about c (based on this analysis; there may be conclusions, such as c cannot be 0 for base 17 since the sum of the highest four base 17 digits is less than 1/2k).

*This statement can be proven with some modular arithmetic. For an even base, n is odd. b=n^2+1, so k = the sum of the digits from 1 to n^2. This is equal to 1/2*n^2*(n^2+1). Since n is odd, n=1 or n=3 mod 4. In either case, n^2=1 mod 4. Since n^2=1 mod 4, n^2+1 = 2 mod 4. Thus k = 1/2 * 1*2 mod 4, or k=1 mod 4, and is therefore odd.

**For an odd base, n is even. Thus, k=1/2*n^2*(n^2+1). n=0 or n=2 mod 4. In either case, n^2=0 mod4. Therefore, n^2*(n^2+1) is divisible by 4. Therefore, 1/2 of that value will be divisible by 2, hence k is even.

Sean T, by my count there are another 61 (dec) possible sets of 3 unique hex digits which sum to more than 1F, after the six examples we gave, above. None of them contain digits below 3 (3+E+F=20). But that doesn't include adding in the carries from other columns. That expands the selection quite a bit, and drops the smallest digit possible to 1 (1+E+F+2=20).

Because leading zeroes aren't allowed, and no set of three digits adding to 20 or more includes a zero (with or without carry), then one of the three columns providing a carry of 2 must sum to exactly 20.

That's right -- I had it written up as base 17, but then thought, "nobody thinks in base 17! better switch to hex."

We use mod 12 in music a lot (12 pitches per octave), but there is one musical structure that depends on the fact that the multiplicative group mod 13 is isomorphic to the addition group mod 12. There are similar structures for any p-1 where p is prime. 17 has a lot of interesting properties.

By Another Matt (not verified) on 17 Nov 2014 #permalink

Dave W.,

Excellent -- I never thought I'd meet someone here who knew anything about Easley Blackwood! Yeah, he is a pioneer of microtonality for sure. I'm about 100 pages into a dissertation about voice-leading in microtonal systems, and Blackwood's thought has found its way in on occasion. His book The Structure Of Recognizable Diatonic Tunings has been helpful. Cheers.

By Another Matt (not verified) on 17 Nov 2014 #permalink

Another Matt, I must confess I only had that album because my dad was the childhood best friend of a president of Columbia records, who made sure my dad got promo copies of lots of the records Columbia produced, and more than one copy to boot (he'd pass dups on to me). It's not because I was a music major or anything. But I did listen to the album, several times, because some of the etudes sounded really good to this naive ear.

Yeah, Blackwood has terrific ears, and it wasn't exactly easy to investigate these systems in 1980. These days I can just code up some synthesis algorithms and I'm good to go; back then it wasn't so easy.

This is my favorite one (13 pitches per octave):

https://www.youtube.com/watch?v=NPZvcAyDY8M

By Another Matt (not verified) on 17 Nov 2014 #permalink

Actually, the 13-pitch piece is the one I found the most jarring.

It's definitely the hardest modulus to work in, although 14 isn't that much better. 19 sounds the most familiar of any between 12 and 24.

By Another Matt (not verified) on 17 Nov 2014 #permalink

Another Matt, don't forget that there's no accounting for taste, also.

I'll get back to the 3-carries-of-2 sub-problem later. I think I'm on to something...

I notice no one has posted any solutions to Matt's problem of three 4-digit hexadecimal numbers summing to a fourth. So here are a couple:
2780+39A1+6EB4=CFD5
3A90+4BC1+5FD7=E628.

it appears that all solutions have either two carries of 1 or two carries of 2, which means that the sum of the digits of the sums always equal either 30 or 45 (by means of the technique Sean used in #15 above)

Rick, I've been quiet because I'm trying to figure out an elegant solution or disproof for the 3-carries-of-2 sub-set of that problem.

I think I have a proof that there are no solutions with three carries of 2. I won't vouch for the elegance, however.

I'm not going to try to learn latex for this post (sorry).

Sean T, in #15 above, used an argument based on the sums of the digits in the original problem to show that the sum of the digits in the answer of that problem equals 18. It is not difficult to generalize that argument to more than two addends and to bases other than 10.

In general, for any addition problem, let
b = base of the number system being used (here 16)
t = sum of all the digits in the problem (here, the sum of 0..15 = 120).
x = sum of the digits in the addends
y = sum of the digits in the sum of the problem.
c = sum of all the carries

Let K be number of columns, and R be the number of rows of addends.

Let d[i][j] be the digit in column j of row i of the addends and s[j] be the digit in column j of the sum. Further, let c[j] be the carry out of column j, so c[j-1] is the carry into column j. counting the columns from 1, c[0] = 0.

so for column j the sum of the digits in the addends is
d[1][j]+d[2][j]+...+d[R][j] + c[j-1] = s[j] + b*c[j]

Iterating of all columns, we get
column 1: d[1][1] + d[2][1] + ... d[R][1] + c[0] = s[1] + b*c[1]
column 2: d[1][2] + d[2][2] + ... d[R][2] + c[1] = s[2] + b*c[2]
...
column K: d[1][K] + d[2][K] + ... d[R][K] + c[K-1] = s[K] + b*c[K]

thus summing it all up of the digit of the addends
(d[1][1] + ... + d[R][K]) + (c[0] + ... c[K]) = (s[1] + ... + s[k]) + (b*c[0] + ... b*c[K])
which is, using the definitions above, (with c[0] = 0)

[1] x + c = y + b*c
Also
[2] x + y = t

combining [1] and [2], and doing the algebra,
[3] y = (t - (b-1)*c)/2
or, since t = b*(b-1)/2, by more algebra,
[3'] y = (b-1)*(b - 2*c)/4)

In this problem, the sum of all the carries could possibly be from 0 to 6 (no carry out of the first column). However, any odd sum of the carries produces a fractional y, so the sum of the carries must be even.

Solving for y with various values of c
c = 0, y = 60
c = 2, y = 45
c = 4, y = 30
c = 6, y = 15

The largest four-digit sum possible in the problem is hexadecimal FEDC; summing the digits (in decimal) gives 15 + 14 + 13 + 12 = 54, which is less than 60, thus in the problem it is not possible to have 0 carries.

The sum is clearly larger than any addend. Since no digit is repeated in this problem, and relaxing the constraint of no leading zeros, the first digit of the sum is 3 or larger, with the three addend rows starting with 0,1,2 with no carry into that column. Further, to achieve an initial digit of 3, the digits 0,1 and 2 are already used, so the no repeat constraint means that the sum in the problem must be no less than 3456, the digits of which sum to 18. 18 is larger than 15, so there is no arrangement of the digits in the sum of the problem that will sum to 15, so three carries of 2 is not possible.

So the sum of digits in th e solution must be 30 of 45, and the sum of the carries must be 2 or 4.

(This argument does allow for a single carry of 2; I don't know it there is such a solution, however)

Yeah, I'd already figured that the total of the digits in the sum must be 15, but I didn't carry that idea far enough.

The 1s, 10s and 100s columns, in order to have sums greater than 1F and so provide a carry of two, must each have a pair of digits above 9 as addends. There are three such pairs, and three columns, so all digits above 9 must appear as addends. So without duplicating digits, the 1000s place of the sum can't be higher than 9, and the 1000s column can't have a zero in it, so the two possible 1000s columns are 1+2+3=8 (remember, 2 gets carried into it) or 1+2+4=9.

Again, there are no leading zeroes, and a zero can't appear as an addend in another column and have that column sum be greater than 1F, so the zero must appear in the lower three digits of the sum.

If the sum starts with 9, the leftover digits are {3,5,6,7,8} and so the smallest possible sum-of-digits of the solution will be 9+5+3+0=17. And if the sum starts with 8, the leftover digits are (4,5,6,7,9} and the smallest digit sum will be 8+5+4+0=17. Obviously, neither of these is 15.

Wish I'd thought of that before doing a bunch of the other analysis I did.

Have you considered one carry of 2 _and_ two carries of 1 (for a total of 4 carries), Rick?

Dave-
No, I have been working on generalizing Sean's argument to at least this problem to see how far that went. I haven't yet considered how the four carries can be arranged.

There are solutions, such as 1284+379D+5CBF=A5E0, that have one 2 and two 1's, but beyond finding one I haven't done aanything.