1. The transformation $ n \to 2n - 1$ or $ n \to 3n - 1$, where $ n$ is a positive integer, is called the 'change' of $ n$. Numbers $ a$ and $ b$ are called 'similar', if there exists such positive integer, that can be got by finite number of 'changes' from both $ a$ and $ b$. Find all positive integers 'similar' to $ 2005$ and less than $ 2005$.
Problem
Source:
Tags: induction, combinatorics proposed, combinatorics
06.03.2009 05:41
Seems easy. If we "change backwardly" from 2005, the only possible sequence is: 2005 -> 1003 -> 502. So 502 and 1003 are the only positive integers similar to 2005.
06.03.2009 07:28
The problem statement means that in the definition of similarity we are allowed to change both $ a$ and $ b$.
10.09.2010 20:14
Im really interested in a solution to this problem. thanks for some help.
10.09.2010 21:51
I think that we can prove next fact : If $ a \sim b$ and $b \sim c$ then $a \sim c$ ( $a \sim b$ <=> $a$ and $b$ are similar ) If we can prove this fact, then easy, by induction, see that $n \sim k$ for any $n \in \mathbb{N}$ and $k \leq n$.
11.05.2011 13:00
@Ovchinnikov Denis How is transitivity supposed to help, im not able to get much out of it. if you could post your solution involving transitivity (involving, but not proving transitivity), i could probably extend that logic somehow btw. transitivity of a relation R means that aRb and bRc $\implies$ aRc
24.06.2012 22:17
Well if you can prove transitivity (and that is a big IF) then an induction on the set {$1,2,...,k$} for $k\in Z_{>0}$ would show that all positive integers are similar to one another. Base case is that $1$ and $2$ are similar to one another ($2=3*1-1$). Then we note that if it is true that all of {$1,2,...,k$} are similar to each other and if $k+1$ is odd then $\frac{k+2}{2} \in$ {$1,2,...,k$} so $k+1$ is similar to {$1,2,...,k$}, if $k+1$ is even then it is similar to $\frac{3(k+1)}{2}$ as $2*\frac{3(k+1)}{2}-1=3k+2$ and $3(k+1)-1=3k+2$ and since $\frac{3(k+1)}{2}$ is a positive integer less than $k+1$ it is in {$1,2,...,k$} so $k+1$ is similar to {$1,2,...,k$}.
03.07.2015 12:30
I think you need to prove another lemma: If a is similar to b and c then bis similar to c.
27.07.2021 08:36
lasha wrote: 1. The transformation $ n \to 2n - 1$ or $ n \to 3n - 1$, where $ n$ is a positive integer, is called the 'change' of $ n$. Numbers $ a$ and $ b$ are called 'similar', if there exists such positive integer, that can be got by finite number of 'changes' from both $ a$ and $ b$. Find all positive integers 'similar' to $ 2005$ and less than $ 2005$. We will define $a \sim b$ as $a$ is similar to $b$ The first Claim 1:- The numbers which are divisible by 6 and those which are even and $\equiv 2 \pmod 3$ can't be similar to a number smaller than it. Proof:- This is obvious since if it could be represented as $a~b,a>b$ then it would be congruent to either $1 \pmod 2$ or $2 \pmod 3$ which contradicts this claim. Claim:2 (Transtivity) If $a \sim b$ and $b \sim c$ then $a \sim c$ Proof:- Since $a \to ........ \to c$ and $b \to ................ \to c$ after finitely many steps,we can put the two sequences together and get $a \to .......... \to b \to ..........\to c$ showing $a \sim c$ Claim 3:- The transformations are all increasing i.e the transformations aren't reflexive. Proof:- Since $2n-1 \ge n$ and it is same for $3n-1$ this is true(except for only 1 $n$ i.e $n=1$) By the above two claims it is easy to see that $2005 \to 1003 \to 503$ is the desired sequence and the answer is $\boxed{2}$ Also some of the above posts claimed that the answer is $n$.,Consider $n=6k$,it can't be similar to any number smaller than it,since it is neither congruent to $-1 \pmod 2$ or $-1 \pmod 3$ so in this case it would be $0 \neq 6k$ a clear contradiction.