11
$\begingroup$

Start with an arbitrary positive integer, and construct a sequence from it as follows.

For each term in the sequence, subtract its largest digit from it to get the next term.

How many consecutive odd numbers can this sequence have before going even?


Inspired by a puzzle from the (Russian) Tournament of Towns.

$\endgroup$
  • $\begingroup$ What do you mean by "consecutive"? Like, a run of odd numbers in the sequence's terms? Also, does "subtract its largest digit" mean something like 9117111345 -> 9117111345 - 9 or 9117111345 -> 117111345? $\endgroup$ – EKons Feb 2 '18 at 14:13
  • $\begingroup$ @Έρικ 1) Yes. 2) The first: actually subtracting the highest digit, not removing it from the decimal representation of the number. $\endgroup$ – Rand al'Thor Feb 2 '18 at 17:06
14
$\begingroup$

I can have a series of:

5 odd numbers

First, some observations:

When the highest digit is odd then we have the last odd number of the series, as odd - odd = even.
==> We should avoid appearance of 9 in the number.
We always lose one and only one in the tenth number.
==> The max odd sequence is then limited to 10 (8-7-6-5-4-3-2-1-0-9-non odd).
It is impossible to have a unit digit going down or being stable as you always subtract a digit higher than it.
So we must go up in unit digit as slow as possible (i.e subtracting by 8) 2 by 2.

Then we must have a number in the form:

8a1 with a greater than or equal to 4, for example
841 --> 833 --> 825 --> 817 --> 809 (--> 800)
EDIT: Actually 'a' needs to be greater than or equal to 3, as pointed by @chronocidal.

$\endgroup$
  • 2
    $\begingroup$ The lowest possible value for a is actually 3, not 4: >!831 > 823 > 815 > 807 > 799 > 790 $\endgroup$ – Chronocidal Feb 2 '18 at 13:54
8
$\begingroup$

Second try

My initial thought seems to be actually correct, and the longest chain must be:

Length 5.

Untitpoi posted his answer while I was editing, but I believe our approaches are similar. One such chain is:

881-873-865-857-849-840

Why this is optimal:

Without loss of generality, consider the first number in a chain. If it's largest digit is odd, at the next step we will have an even number. As such, its largest digit must be even. Consider the case where this number is the largest for all but the last number of the chain. We can consider number mod 10, and keep subtracting from there. This yields the following possibilities:
Largest digit 2: x1-x9 END
Largest digit 4: x1-x7 END, x3-x9 END
Largest digit 6: x1-x5-x9 END, x3-x7 END
Largest digit 8: x1-x3-x5-x7-x9 END
Other starts need not be considered, since they simply start later in the chain.
If we assume this digit is NOT continuously the highest in the chain, but we do constantly have an even highest digit (as required), we consider two cases:
- The highest digit is the last digit. Then, the numbers are even, so this is not possible.
- The highest digit is not the last digit. For this to happen, we would need to subtract more than 10, which is clearly impossible.
As such, we have the case where 8 is always the highest, leading (possibly) to the above chain.

Generalization

Using the above explanation, it's easy to see to that in base-n, we have a maximum chain length of

n/2

Using some number that:

Always has n-2 as the highest digit. This results in a chain with numbers ending in 1, 3, 5, [...], n-5, n-3, n-1, END.

First try

Not sure if I'm getting this right, but... EDIT: This logic is clearly flawed, as indicated in the comments. I'm leaving it here for future reference.

888[...]881 seems to give an infinite number of consecutive odd numbers.
To be clear, there is an infinite number of eights. The next number will be 888[...]873, then 888[...]865... Eight is always the largest number, and since it's infinitely long, there will be no end. Not for us common folk, anyway, mathematicians will start arguing about types of infinity, I guess...

In addition to my edit: This does give at least a lower bound - Though I have no clue as to how much this can be improved (I'm assuming it can).

The lower bound:

5, with the chain being 881-873-865-857-849-840

$\endgroup$
  • $\begingroup$ @Saeïdryl Ah, of course. I should've noticed that. Gonna ponder a bit on further answers I guess... $\endgroup$ – Lolgast Feb 2 '18 at 12:57
  • $\begingroup$ Your infinite chain doesn't work. 888[...]881 (-8)= 888[...]873 (-8)= 888[...]865 (-8)= 888[...]857 (-8)= 888[...]849 (-9)= 888[...]840, which is even . $\endgroup$ – Penguino Feb 4 '18 at 22:01
  • $\begingroup$ @Penguino That's why I mentioned "This logic is clearly flawed" $\endgroup$ – Lolgast Feb 4 '18 at 22:02
  • $\begingroup$ Also does not start with a positive integer... $\endgroup$ – Matt Stevens Feb 5 '18 at 11:15
  • $\begingroup$ @Mattstevens I do? Perhaps not with an even one, but that's not in the rules that it should be. $\endgroup$ – Lolgast Feb 5 '18 at 11:22
2
$\begingroup$

The same answer as the first two respondents, but hopefully a tidier explanation.

The longest run is 5.

The explanation;

To sustain a run, the largest digit must be even and the current number odd. When the largest digit becomes odd, the next number is always even. This limits the run.

The largest positive digit is 8, any number between 800 and 888 allows 8, any arbitrary number of digits to the left are allowed so long as there are no digits larger than 8.

The only number larger than 8 is 9, meaning if the highest digit = 9, then being an odd number, the run is over.

For each of the four odd numbers less than 9;
837 – 08 = 829, 2 consecutive odd numbers
835 – 16 = 819, 3 consecutive odd numbers
833 – 24 = 809, 4 consecutive odd numbers
831 – 32 = 799, 5 consecutive odd numbers

The longest run of five odd numbers, holds for any of the following six values; 831, 841, 851, 861, 871, 881.

$\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.