BdMO Selection Round 2021 Higher Secondary Problem 10
Posted: Fri Mar 12, 2021 7:39 pm
by Anindya Biswas
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?
Re: BdMO Selection Round 2021 Higher Secondary Problem 10
Posted: Sat Mar 13, 2021 12:25 pm
by Mehrab4226
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.
#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)