6

Given a segment $AB$ of length $1$, define the set $M$ of points in the following way: it contains the two points $A,B$ and also all points obtained from $A,B$ iterating the following rule: for every pair of points $X,Y$ in $M$, the set $M$ also contains the point $Z$ of the segment $XY$ for which $YZ = 3XZ$. Prove by induction that the set $M$ consists of points $X$ from the segment $AB$ for which the distance from the point $A$ is either $$AX = \dfrac{3k}{4^n} \hspace{3 mm} \text{or} \hspace{3 mm}AX = \dfrac{3k-2}{4^n}$$ where $n,k$ are nonnegative integers.

I am confused by this question since I am not used to doing induction geometrically. Seeing as how we have to iterate each time a new point, I find it hard to formalize an inductive argument to prove this.

user19405892
  • 15,592

2 Answers2

4

Every point on the segment $AB$ has some distance from $A$. So let's say you have two such points, $X$ and $Y$. Let $x$ denote the distance of $X$ from $A$, $y$ the distance of $Y$ from $A$.

Let $D$ be the set of distances from $A$ to each point in the set $M$ that is constructed in the problem. Recall the rule in the problem that says that if $X$ and $Y$ are members of the set $M$, the point $Z$ of the segment $XY$ for which $YZ = 3XZ$ is too. An equivalent rule is, if $x$ and $y$ are numbers in the set $D$, then the number $z$ between $x$ and $y$ such that $|z - y| = 3|z - x|$ also is in the set $D$.

The theorem you are to prove is that $D$ consists entirely of numbers of the form $\dfrac{3k}{4^n}$ or of the form $\dfrac{3k-2}{4^n}$.

There, now it's not a geometric induction any more. Just arithmetic.

There are still some complications, for example you can't just assume $x < y$, you can't just assume that one of $x$ and $y$ has the form $\dfrac{3k}{4^n}$ and the other has the form $\dfrac{3k-2}{4^n}$ (they might both have the same form), and you can't just use one value of $k$ to write both $x$ and $y$. You might have to consider several possible cases separately for the induction step.

David K
  • 98,388
  • Case $1$: $x$ has form $\dfrac{3k}{4^n}$ and $y$ has form $\dfrac{3k-2}{4^n}.$ Then $z = \dfrac{3k+1}{4^n}$ or $z = \dfrac{6k-1}{2^{2n+1}}$. Why isn' this of the correct form? – user19405892 Jan 12 '16 at 15:25
  • Both $z$ outcomes are of the correct form: $\dfrac{3k+1}{4^n} = \dfrac{3(k+1) - 2}{4^n}$, and $\dfrac{6k-1}{2^{2n+1}} = \dfrac{3(4k) - 2}{4^{n+1}}$. (But make sure that you didn't just assume that both $x$ and $y$ use the same multiple of $3$ and the same power of $4$.) – David K Jan 12 '16 at 15:34
  • You might want to show first that you can convert any number of one of those to forms into one of those forms with any higher power of $4$. That way at least you can justify putting $x$ and $y$ into forms that use the same power of $4$ (that is, given two numbers with different powers of $4$ in the denominator, rewrite the one that has the smaller power of $4$ so that it has the same power of $4$ as the other). Otherwise I think different powers of $4$ could be a huge hassle. – David K Jan 12 '16 at 15:37
  • Can you show the proof as an answer since it seems hard to do this. – user19405892 Jan 12 '16 at 17:50
  • gave a proof, then looked at answers; since David seems to have chosen explicitly not to give a full solution, I removed mine – cats Jan 13 '16 at 03:01
  • @cats In part, I was hoping the exercise would be more useful for the OP if given a few hints and a nudge rather than a complete step-by-step writeup, but part of my lack of response was that I had my own work to do. Your solution is more elegant than anything I likely would have written, anyway. The technique of taking a union of sets $M_n$ is a very useful one for this kind of problem and OP would benefit by knowing how to do it, if you care to try to explain it. – David K Jan 13 '16 at 03:19
0

Using the same starting point as David K to transform this into something more arithmetic, his expression

$|z - y| = 3|z - x|$

is equivalent to $z=\dfrac {3x}4 + \dfrac{y}{4} \quad\forall x ,y \in D$.

If $y>z>x$,then $|z - y| = 3|z - x|$ is equivalent to $y-z=3(z-x)$.

If, however, $x>z>y$, then $|z - y| = 3|z - x|$ is equivalent to $z-y=3(x-z)$. Both are equivalent statements. Solving for $z$,

$z-y=3(x-z)$

$z-y=3x-3z$

$4z=3x+y$

$z=\dfrac{3x}4+\dfrac y4$

$z$ will always take the form of $y$ (either $\dfrac{3k}{4^n}$ or $\dfrac{3k-2}{4^n}$). Modular arithmetic may ease explanation. The numerator is either 0 (first case) or 1 (second case) mod 3. $3x=0\mod 3$ so we need only consider how $y$ affects the form of $z$.

If $x$ and $y$ have the same denominator, then the numerator of $z$ is simply $3x+y$ and $(3x+y)\mod\ 3=y\mod\ 3$.

If the denominator of $y$ is greater than that of $x$, the numerator of $z$ is $(3x)(4^n)+y$ and $(3x)(4^n)+y\mod\ 3=y\mod\ 3$.

If the denominator of $x$ is greater than that of $y$, the numerator of $z$ is $3x+y(4^n)$. In modular arithmetic $(ab)\mod c=[(a\mod c)(b\mod c)]\mod c$. $4^n=1 \mod c \quad\forall n \in \mathbb{Z}$.
Therefore, $3x+y(4^n) \mod\ 3=y\mod\ 3$.

Euclid419
  • 11
  • 1
    it can be shown that That's not an answer, unless you do actually show that or at least provide a credible hint thereof. – dxiv Jan 12 '16 at 07:24
  • It's actually the other way around, my formula for $z$ is equivalent to $z = \frac34 x + \frac14 y$, although of course both formulas will describe numbers in the set since either of the two input numbers could have been chosen as $x$. – David K Jan 12 '16 at 15:23
  • Yes, thank you David. Correction made. And "it can be shown that" will be replaced with evidence. – Euclid419 Jan 13 '16 at 01:36