BdMO Selection Round 2021 Higher Secondary Problem 10

Forum rules
Please don't post problems (by starting a topic) in the "X: Solved" forums. Those forums are only for showcasing the problems for the convenience of the users. You can always post the problems in the main Divisional Math Olympiad forum. Later we shall move that topic with proper formatting, and post in the resource section.
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
BdMO Selection Round 2021 Higher Secondary Problem 10

Unread post by Anindya Biswas » Fri Mar 12, 2021 7:39 pm

You have a magical machine that when given an even integer as input returns one-half of it. And when it is given an odd integer as input, it adds $3$ to that integer and returns it. The machine then keeps on going by using its output as input. The only time it stops is when it sees a number it has already seen. To make sure the machine runs as long as possible, what positive integer not greater than $100$ must you provide to it as input initially?
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BdMO Selection Round 2021 Higher Secondary Problem 10

Unread post by Mehrab4226 » Sat Mar 13, 2021 12:25 pm

Mathematical Approach
Lemma: If n a positive integer is the input, $n\neq 1,2,3$ and $3| n$ the last output will be 6, and the same for n not a multiple of 3, is 4.
Proof:
We, see that the sequence of inputs and outputs is ever decreasing, but they will become equal after finite iterations. Let say for what condition of n the computer cannot get the same number. If n is even $\frac{n}{2}$ is always less than n. If n is odd then to satisfy our condition,
$\frac{n+3}{2} < n-3$[Because if $\frac{n+3}{2}$ is odd and is not less than n-3 then the number become equal to n which is not what we want]
$n+3<2n-6$
Or,$9<n$
So the magic computer will stop when the input value becomes less than or equal to 9. If we take 2-9 inclusive as inputs we will get that the final output will be 4 or 6 and the condition is stated in the lemma. So we proved that the computer will keep running until it reaches a number $\leq 9$ and then we see that if it is a multiple of 3 it reaches 6 and if it is not a multiple of 3 it reaches 4.[1,2,3 are exceptions][remember if an input is a multiple of 3 all inputs are multiple of 3]. So, lemma proved.

Now, we know how the chain will end and can do the opposite of what the computer does and find the number which gives us the longest chain.
(1) $4 \to 1 \to 2 \to 4 \to 8 \to 5 \to 10 \to \cdots $
(2) $6 \to 3 \to 6 \to 12 \to 9 \to 18 \to 15 \to \cdots$
The reverse chain is like this,
$n \to 2n$ if n is odd.
$n \to n-3$ if n is even .
$n \to 2n $ is also possible if n is even but it gives us fewer iterations to reach a larger number which is not what we want.
In this way, we will get 67 as the greatest by (1) which is made by 15 iterations. And 51 as the greatest by (2) by probably 10 iterations. So 67 wins. 67 is the ans.

This solution can be wrong. But it served my purpose. Because I got a similar question but asked what the last output will be which is proved by my lemma. The best part is I didn't prove it during the test, I gave the answer with the same conjecture.
A partial computational Approach
After seeing the problem, it looked a lot like a computer program. So I tried my level best for half an hour to code the magical machine in python. You can use it to get the last output and the number of iteration needed to get there from your given input I am providing it here.

Code: Select all

#This is a python program for our math problem#

g=[]
def magic(x):
    if x in g:
        print("Last output",x)
        print("Number of itterations",len(g))
        g.clear()

    else:
        
        if x%2==0:
            g.append(x)
            x=x/2
            
            

        else:
            g.append(x)
            x=x+3
        magic(x)    

The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply