Ytukyg

I am trying to solve this below problem from Norman Bigg's Discrete Mathematics textbook, but cannot reconcile his solution with my work.

Let $X$ be a subset of ${1, 2, ldots 2n}$ and $Y$ be the set of odd numbers ${1, 3, ldots, 2n-1}$. Define a function $f: X to Y$ by the rule
begin{equation}
f(x) = text{the greatest member of $Y$ that exactly divides $x$}.
end{equation}
Show that if $|X| > n + 1$, the n $f$ is not an injection, and deduce in this case that $X$ contains distinct numbers $x_1$ and $x_2$ such that $x_1$ is a multiple of $x_2$.

Here's what I have so far.

Define a function $X to Y$ by the given rule. Clearly, for any $n$, $|Y|=n$, so $|X| > |Y|$, and $f$ cannot be injective by the Pigeonhole Principle, meaning that there are two elements in $X$, $x_1$ and $x_2$, such that $f(x_1) = f(x_2) = y$. If $x_1 = x_2$ for any such $x_1$ and $x_2$, $f$ would be injective, so we must be able to find $x_1$ and $x_2$ such that $x_1 neq x_2$. Since $y$ divides both $x_1$ and $x_2$, we must have
begin{equation}
x_1 = ay text{and} x_2 = by,
end{equation}
for $a, b, in mathbb{N}$. But $x_1$ and $x_2$ are even, by the definition of $X$, it must be the case that $a$ and $b$ are even, since $y$ are not. Hence,
begin{equation}
x_1 = 2cy text{and} x_2 = 2dy,
end{equation}
for $c, d in mathbb{N}$.

Without sacrificing generality, take $x_1 > x_2$. Hence, $a > b$. It suffices to demonstrate that $b | a$.

This is the point at which I am unable to complete the argument. The solutions manual frames the argument quite a bit differently, arguing that we can write $x_1 = 2^{m_1} y$ and $x_2 = 2^{m_2} y$ for naturals $m_1, m_2$. I do not understand why we can write $x_1$ and $x_2$ with powers of $2$, instead of multiples. The one assumption I haven't used is that $y$ is odd: substituting in some form of $2j - 1$ for $y$ doesn't seem to yield much good, though.

Any help with this would be greatly appreciated.

The key thing to note here is that $a$ and $b$ don't just need to be even -- they MUST be powers of two. Why? Because $f(x)$ is defined as the greatest odd divisor of $x$. By pulling out factors of $2$ you can write $a=2^kc$ for some odd $c$, which means $x_1=2^kcy$. But then $cy$ is an odd divisor of $x_1$; the fact that $y$ was already the greatest odd divisor implies that we must have $c=1$.

So, we can write $x_1=2^ky$ and $x_2=2^hy$. And necessarily, one of these must be a multiple of the other. (Take whichever one has a higher exponent; or, if they are the same, either way works.)