There is some natural number written on the board. An operation is defined as adding to the number its maximal proper divisor. Prove that after some iterations of this operation that we get a number that's divisible by 32020.
This makes sense in my head but it's very possible I've missed something...
Consider our starting number written on the board, N. We only need to consider even N, since a single application of the operation to an odd N will give us an even number.
If N mod 4 = 0, then a single operation on the number produces 3N/2, and a second operation produces 9N/4. Since 4 divides N, then this is some number bigger than N that has 2 more factors of 3 than N did.
If N mod 4 = 2, then a single operation on the number produces 3N/2. This number is odd, but is also 0 mod 3 (regardless of N mod 3). So a second operation produces 3N/2 + 3N/6 = 2N. This number is now 0 mod 4 and we can continue as in the previous paragraph.
So regardless of the starting value of N mod 4, after a few steps we get to a value of 0 mod 4, which after two more operations produces a value that is 9 times greater than some prior value (i.e. has 2 more factors of 3). So we can just keep repeating these steps and adding more and more factors of 3 until eventually there are at least 2020 of them.
|
|
Posted by tomarken
on 2021-03-18 10:43:18 |
Solution (i think)
