2

A set of natural numbers $\{a_1,a_2,...,a_n\}$ are given. We add the numbers one pair at a time in some order. Is it true that the number of carries during our process is independent of the order?

Example: $\{57, 82, 19\}$.

  • $57+82 = 139$ (1 carry), $139+19 = 158$ (1 carry) = 2 carries

  • $82+19 = 101$ (2 carries), $101 + 57 = 158$ (0 carry) = 2 carries

Each time we perform a carry, it is because the value is too high (higher than $9$). But why does this need to happen the same number of times?

tarthoe
  • 553
  • 1
    Very intriguing ?. I advise running a computer simulation, where (for example) 10 numbers are chosen at random between 1000 and 2000. Once these #s are chosen, order them in each of the 10! ways, counting the # carries with each of the 10! different summations. If time feasible, then repeat with 99 more groups of 10 randomly chosen #'s, to see what happens. This is a std attack method when no elegance suggests itself. If you find a counter-example you can analyze why it is a counter example. If all 100 grps of 10 #'s fail to indicate a diff. you have a reasonable conjecture to explore. – user2661923 Sep 26 '20 at 09:26
  • If no difference is detected, you also have to consider how range-sensitive the 10 numbers are. That is, what happens if 5 of the 10 of the numbers are randomly selected (instead) from the range 1 through 20? – user2661923 Sep 26 '20 at 09:28
  • It seems to be true. Think of it as the sum of the digits, tens... The carries at each column is not depending on the order. Than the carries are added further at the other columns - and the order does not impact the number of carries. – Moti Sep 26 '20 at 18:15
  • @Moti "The carries at each column is not depending on the order." I agree that the aggregate size of the carries at each column is unaffected by the order. However, it is not immediately obvious to me why, with respect to a specific column whose carries have an aggregate size of 2 (for example), why two different orderings couldn't result in one carry of size 2 vs two carries of size 1. – user2661923 Sep 27 '20 at 16:59
  • If you sum them two at a time the carry can not be 2. – Moti Sep 29 '20 at 05:02

0 Answers0