16
$\begingroup$

Consider 2 arbitrary, fixed points A and B on the plane. Suppose you can move from point A in unit distance at any angle to another point and from this point you can again travel a unit distance at any angle to another point and so on. Ultimately your goal is to travel from point A to point B along a path of unit-distance line segments without repeating a point during your journey. Is the set of such paths countable or uncountable?

I believe it is uncountable and here is my thought process, but I'm not sure of my logic. Consider the line between the two points equidistant from them; call this line L. A path of only unit distances can be made between A and any point, P, which lies on L without crossing L(I don't know how to prove this statement but it seems true). This path can be mirrored on the other side of L to connect B to P. Thus for any point, P, which lies on L a path can be made from A to B crossing through P halfway through the path. Since the points on L are uncountable the set of paths between A and B are also uncountable.

$\endgroup$
12
$\begingroup$

Yes, this looks convincing. For the missing step, go directly from A towards P in unit steps until the distance left is less than 2. Then use the remaining distance as the base of an isosceles triangle with unit legs, which you make point away from L.

$\endgroup$
  • $\begingroup$ It's not only convincing, it's simply correct. OP has shown a mapping of domain subset (domain here is all possible paths with the given constrains) to the straight line so the cardinality of domain has to be no less than the cardinality of a line (which of course is uncountable). $\endgroup$ – Ister Mar 6 at 12:28
6
$\begingroup$

Go one unit from $a$ at an angle of $t$ to $c$.
Go in unit steps along ca until one is less than a unit away from $b$ to a point $p$.
If $p \neq b$, then draw a triangle with base $pb$ and sides of unit length adding the sides as the final steps.

As for each $t$ in $[0,2\pi)$, I've constructed a different accepted zigzaging from $a$ to $b$, there are uncountably many ways of so staggering from $a$ to $b$.

$\endgroup$
2
$\begingroup$

Let $C$ be on the line through $B$ that is perpendicular to the segment $AB$ with the distance $BC$ equal to $1/2.$ Take any half-line $L$, not through $B$, that originates at $A$ and intersects the segment $BC.$ For some $n\in \Bbb N$ there is a path along $L,$ starting at $A,$ determined by $n$ points $A=A_1,...,A_n$ where $A_j,A_{j+1}$ are distance $1$ apart for each $j<n,$ and such that the distance from $A_n$ to $B$ is less than $1.$

Let the point $D$ be such that $A_nD=BD=1$ nd $D\not \in \{A_1,...,A_n\}.$ Then the path determined by $\{A_1,...,A_n\}\cup \{D\}$ is a path of the desired type.

The cardinal of the set all such $L$ is $2^{\aleph_0}$ so there at least this many paths of the desired type, joining pairs of points .

And each path is determined by a function from some $\{1,2,...,m\}\subset \Bbb N$ into $\Bbb R^2.$ The set of all such functions has cardinal $2^{\aleph_0}$ so there are at most $2^{\aleph_0}$ paths of the desired type.

$\endgroup$
1
$\begingroup$

Suppose first that the distance $AB$ between $A$ and $B$ is strictly between $2$ and $3$. Then for every point $C$ such that $AC=1$ and $BC<2$, there is a second point $D$ such that $CD=1=BC$ (draw an isosceles triangle). The set of such points $C$ forms an open arc on the unit circle centered at $A$, and so there are uncountably many such $C$, hence uncountably many such "unit paths".

For general points $A$ and $B$, just find one unit path between $A$ and $B$ that contains two intermediate points $A'$ and $B'$ with $2<A'B'<3$ (for example, points on a giant circle eventually connecting $A$ to $B$), and then vary the path from $A'$ to $B'$ in the way described above.

This proof even shows that one can get uncountably many unit paths with the same number of unit-steps. A slight sharpening shows that for any integer $k>AB$, there are uncountably many unit paths from $A$ to $B$ with exactly $k$ unit-steps.

$\endgroup$
0
$\begingroup$

I believe it is uncountable also, and here is my thought process:

For each direction vector $v\in\Bbb R^2=T_a\Bbb R^2$, take a curve $\alpha_v$ from $a$ to $b$ with $\alpha_v'(0)=v$.

Then if $v\neq w$, we have $\alpha_v\neq\alpha_w$.

But clearly there are uncountably many direction vectors in $\Bbb R^2=T_a\Bbb R^2$.

$\endgroup$
  • $\begingroup$ It seems OP wants movements made of straight line segments all of length $1,$ to go from fixed $A$ to fixed $b$ points. [rather than curves as you use] $\endgroup$ – coffeemath Mar 5 at 3:28
  • $\begingroup$ I did notice that. But I thought, well, straight lines have derivatives. @coffeemath $\endgroup$ – Chris Custer Mar 5 at 4:39
  • $\begingroup$ Cris-- Then to finish one has to show that after the first initial unit straight line step from $A,$ it is possible to continue such steps and somehow arrive at $B.$ $\endgroup$ – coffeemath Mar 5 at 5:17
  • $\begingroup$ @coffeemath yes. Well there certainly appear to be some details missing. But this seems fairly reasonable. Thanks. $\endgroup$ – Chris Custer Mar 5 at 5:21
  • $\begingroup$ William Elliot's answer does this. $\endgroup$ – coffeemath Mar 5 at 5:52
0
$\begingroup$

Your proof is correct. We can fill in the details on the first part: For any two distinct points $A$ and $B$ in the plane, we can construct a path consisting of unit distances from $A$ to $B$.

If $A$ is more than one unit away from $B$, start at $A$ and take unit steps toward $B$ until we are less than one unit from $B$. If $B$ is a whole number of steps away, we will land on $B$. If not, we will land on a point $P$ within the unit circle centered at $B$. Since $P$ is less than a distance of $1$ away from $B$, the unit circle centered at $P$ will intersect the unit circle centered at $B$ in two places. Take one step from $P$ to an intersection point and then one step from the intersection point to $B$ to finish the path.

$\endgroup$
0
$\begingroup$

Yes, and here is a very simple and intuitive argument without mirrors ;-)

Observation:

  • Let C be any point on AB such that 0< |AC| < min( |AB|, 2)
  • We can always travel from A to C in 2 x 1-unit steps. (Construct an appropriate unit side isosceles triangle to a point X on the perpendicular bisector of AC such that |AX| = |XC| = 1).
  • We can then travel from C to B in < |AB| unit steps.
  • So all such paths (whatever value of C we chose) will traverse AXCB in < (|AB| + 2) steps, and all such paths are distinct if their respective C' and C are distinct.

But as C can be any real number in that range of real numbers, the number of distinct C we could have chosen is uncountable. Each C gives a unique valid path, so the number of paths in uncountable.

The followup question would be the cardinality involved. There is a chance it might be more than $\mathfrak c=2^{\aleph_0}$ [cardinality of reals, corrected per comments below] - but that's far beyond my skill to figure out.

$\endgroup$
  • $\begingroup$ The cardinality is 'only' aleph_0. You can unique specify any such path by listing the coordinates of all the intermediate points. Hence the set of all paths is contained in the set of finite lists of real numbers. This set has cardinality aleph_0. $\endgroup$ – quarague Mar 5 at 8:02
  • $\begingroup$ The cardinality of the real numbers is not $\aleph_0$. It is $\mathfrak c=2^{\aleph_0}$. ($\aleph_0$ is the cardinality of the integers.) $\endgroup$ – TonyK Mar 5 at 10:32
  • $\begingroup$ Thanks, both. Especially @quarague - a simple clear answer to that one $\endgroup$ – Stilez Mar 5 at 11:42
  • $\begingroup$ The correction of TonyK is true. We both meant the cardinality of the reals, but aleph_0 is just the cardinality of the integers. $\endgroup$ – quarague Mar 5 at 11:47
  • $\begingroup$ Corrected, thank you. But is "set of finite lists" actually the right descriptor? Eg if A=(0,0) B=(0,1) then any specific path of the form [[ ... (-1,0), (-1,0) {n times} ...(0,1), ...(1,0), (1,0) {n times} ... ]] is a valid path. After all, a list of "arbitrary long but finite" paths sounds indistinguishable from an infinite list? $\endgroup$ – Stilez Mar 5 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.