A positive integer is called vaivém when, considering its representation in base ten, the first digit from left to right is greater than the second, the second is less than the third, the third is bigger than the fourth and so on alternating bigger and smaller until the last digit. For example, 2021 is vaivém, as 2 > 0 and 0 < 2 and 2 > 1. The number 2023 is not vaivém, as 2 > 0 and 0 < 2, but 2 is not greater than 3.
a) How many vaivém positive integers are there from 2000 to 2100?
b) What is the largest vaivém number without repeating digits?
c) How many distinct 7-digit numbers formed by all the digits 1, 2, 3, 4, 5, 6 and 7 are vaivém?
Since the first two digits must be 20 the third can be any from 1 to 9. The last must be less than the third. For a given digit n, there are n digits that are less than n. Therefore number is the sum of 1 through 9 which is 45.
Part b is almost trivial. Start with 9876543210 and rearrange slightly to get 9785634120.
Part c: As the number of digits increases the vaivem count increases rapidly. I found these by writing them out
1 digit: 1
2 digits: 1
3 digits: 2
4 digits: 5
5 digits: 16
I didn't spot any recursive structure and I didn't feel like going further.
However these, terms were enough to find https://oeis.org/A000111
which gives
6 digits: 61
7 digits: 272
The above sequence is about ordered objects, not digits, so these vaivem numbers will differ from the up/down numbers beyond n=10.
This sequence is very well studied and has one of the longest oeis entries I've seen.
|
|
Posted by Jer
on 2024-07-13 11:26:09 |
Solution & comments
