rational – nivotko

An infinite road has traffic lights at intervals of $1500$ m. The lights are all synchronised and are alternately green for $\dfrac{3}{2}$ minutes and red for 1 minute. For which $v$ can a car travel at a constant speed of $v$ m/s without ever going through a red light?

Answer.

Let $x(t)$ be the position of the car at time $t$ s and let $x(0)=x_0$ for some $0 \le x_0 <1500$ . With speed $v$ , the car will be at position $x(t) = x_0 + vt$ at time $t$ s. Without loss of generality, we assume that $0 \le x_0 < 1500$ and assume that the light is green at time $t$ s where $\displaystyle t \in A= \bigcup_{k=0}^\infty [150k, 150k+90)$

We want such that whenever $x(t)=1500n$ if and only if $t \in A$ .

The equation is equivalent to $1500n = x_0 + vt$ meaning that $\dfrac{1500n-x_0}{v}=t$ . Hence, we want for each $n$ , there exists an integer $k$ such that

$150k \le \dfrac{1500n-x_0}{v} < 150k+90$

for some integer $k$ . This means that for every integer $n$ ,

$k \le \dfrac{10n - y_0}{v} < k + \dfrac{3}{5}$ for some integer $k$

i.e. $0 \le \left \{ \dfrac{10n-y_0}{v} \right \} <\dfrac{3}{5}$

where $y_0 = \dfrac{x_0}{150}$ . Here, we have that $0 \le y_0 < 10$ .

Let us discuss the case for $y_0=0$ . If we let $\alpha = \dfrac{10}{v}$ , then the inequality becomes $0 \le \left \{n \alpha \right \} < \dfrac{3}{5}$ for every positive integer $n$ .

Lemma. If $\alpha$ is a positive real number such that $\{\alpha\},\{2\alpha\},\{3\alpha\},\{4\alpha\},\dots$ are all in the interval $\left[0,\dfrac{3}{5}\right)$ , then $\left \{ \alpha \right \} = \dfrac{1}{2}$ .

Sketch of proof of lemma. If $\{\alpha\} = \dfrac{1}{2}$ , then we have that $\{n \alpha\} = 0$ when $n$ is even and $\dfrac{1}{2}$ when $n$ is odd. This clearly satisfies the condition.

If $\alpha$ is an irrational number, then the sequence $\{\alpha\},\{2\alpha\},\{3\alpha\},\dots$ is equidistributed on the interval $[0,1)$ . This is Weyl’s Equidistribution Theorem, but we can easily visualize what happens and prove a weaker statement regarding it being bouded by $\dfrac{3}{5}$ .

Suppose now that $\{\alpha\}=\dfrac{a}{b}$ is a rational number for some relatively prime positive integers $1 \le a < b$ . Suppose that $n$ is a positive integer such that $\dfrac{1}{n+1} \le \dfrac{a}{b} < \dfrac{1}{n}$ . Then, note that $n\dfrac{a}{b}<1$ and hence $\{n\alpha\} = n \dfrac{a}{b} \ge \dfrac{n}{n+1} > \dfrac{3}{5}$ if $n \ge 2$ .

Hence, it must be the case that $\{ \alpha\} > \dfrac{1}{2}$ . But then, since $\{\alpha\} < \dfrac{3}{5}$ , we must have $\{2\alpha\} < \dfrac{1}{5}$ . We can apply the same argument to the sequence $\{2\alpha\},\{4\alpha\},\{6 \alpha\},\{8\alpha\},\dots$ and deduce that one of the elements of the sequence is $> \dfrac{3}{5}$ . $\blacksquare$

According to the lemma, we must have that $\{\alpha\} = \left\{ \dfrac{10}{v} \right \} = \dfrac{1}{2}$ . This gives us solution $v=\dfrac{20}{2n+1}$ meter/second for some non-negative integer $n$ . For example, $v=20, v=\dfrac{20}{3}, v=4$ , etc. will work.

This question appears as Brazilian Mathematical Olympiad 2000 Question 4 (first question on Day 2). Even though it looks like a physics problem, this problem involves very beautiful mathematics of rational and irrational numbers. What a surprise!

My solution above seems not so complete though since I assume that $x_0=0$ ; that is, the car starts at point $0$ (or complete, depending on how we interpret the question — it does not ask for all possible values of $v$ , right?) I am not sure how the solution will change. Do you have any idea how to resolve the case? Please let me know in the comment below. I hope you enjoy this problem as much as I do.

Update (21 Dec 2022). A more general version of the lemma would be $\{\alpha+\beta\}, \{2\alpha+\beta\}, \{3\alpha+\beta\}, \dots$ are all $< \dfrac{3}{5}$ . Here, $\alpha = \dfrac{10}{v}$ and $\beta = \dfrac{y_0}{v}$ where $0 \le y_0 < 10$ . I believe that using similar argument, we can say the condition will hold iff $\{\alpha\} = \dfrac{1}{2}$ and additionally, it must be the case that $\{\beta \} < \dfrac{1}{10}$ . Note that this condition is already sufficient, but I am not sure if this is also a necessary condition.

Note that from condition on $\alpha$ , we must have $v=\dfrac{20}{2n+1}$ for some non-negative integer $n$ . The condition on $\beta$ states that $\left \{ \dfrac{y_0(2n+1)}{20} \right \} < \dfrac{1}{10}$ . Suppose that $y_0=4$ , then we have $\left \{ \dfrac{2n+1}{5} \right \} < \dfrac{1}{10}$ . This is true for example for $n=2,7,12,\dots$ (integers that are 2 modulo 5).

This a bonus question for HW 2 Basic Modal Logic course 2016/2017.

Show that transitive fitration on $(\mathbb{Q},<)$ is a finite list of clusters, maybe interspersed by some irreflexive singletons, no two of which may be adjacent.

What I did is to consider it in four steps.

Finiteness and transitivity

This follows from filtration property (upon finite $\Sigma$ ) and the property that $R$ has as a transitive filtration.

Linearity

For all $a \ne b$ , we have $Rab \vee Rba$ .

Proof. WLOG, $a<b$ . Then, we show that for all $\diamond \phi \in \Sigma$ , we have that if $b \Vdash \phi \vee \diamond \phi$ , then $a \Vdash \diamond \phi$ . If $b \Vdash \phi$ , then because $a<b$ , we have $a \Vdash \diamond \phi$ . If $b \Vdash \diamond \phi$ , then there exists some $c>b$ , such that $c \Vdash \phi$ , and thus becaue $a<b<c$ , $a \Vdash \diamond \phi$ . $\blacksquare$

Moreover, we basically have $< \subseteq R$ .

Properties of irreflexive points

If $\neg Raa$ , then there must be some $\diamond \phi \in \Sigma$ , such that $a$ is the greatest number satisfying $\phi$ .

Proof. If $\neg Raa$ , it means that for some $\diamond \phi \in \Sigma$ , we have $a \Vdash \phi \vee \diamond \phi$ but $a \nVdash \diamond \phi$ . Thus, $a \Vdash \phi$ and $a \nVdash \diamond \phi$ . $\blacksquare$

I also claim no two irreflexive points can be adjacent.

Proof. Suppose that $a<b$ are irreflexive points w.r.t. formula $\alpha$ and $\beta$ , respectively and suppose that they are adjacent in the finite list of filtration. Take any number $c \in (a,b) \cap \mathbb{Q}$ . Clearly, $Rac$ . But $a$ and $b$ are adjacent in the filtration, then we must have $Rbc$ for all such $c$ . This means that for all $\diamond \phi \in \Sigma$ , particularly $\diamond \beta$ , we have $c \vDash \beta \vee \diamond \beta$ implies $b \vDash \diamond \beta$ . But, we have $b \nvDash \diamond \beta$ . $\blacksquare$

Properties of non-simple cluster

Now, we prove that for any reflexive point, it belongs to a non-simple cluster.

Proof. If there is no $\diamond \phi \in \Sigma$ , then all the points belong to the same cluster. If there exist $\diamond \phi$ , then for reflexive points $a$ , $Raa$ means for all $\diamond \phi \in \Sigma$ , $a \vDash \phi \vee \diamond \phi$ implies $a \vDash \Diamond \phi$ . This means, $a$ must not be the greatest number satisfying formula $\phi$ for any $\diamond \phi \in \Sigma$ . Because there is only finite number of singletons (due to the finiteness of $\Sigma$ , we can choose rational number $a_1 >a$ such that all the numbers in $(a,a_1) \cap \mathbb{Q}$ are all reflexive (not a singleton). Now pick any $x \in (a,a_1) \cap \mathbb{Q}$ . Clearly $Rax$ . We show $Rxa$ now. Because it means for all $\diamond \phi \in \Sigma$ , $a \vDash \diamond \phi$ implies $x \vDash \diamond \phi$ , and because $a$ is not a singleton, we then just need to check $a \vDash \diamond \phi$ implies $x \vDash \diamond \phi$ . Suppose $a \vDash \diamond \phi$ but $x \nvDash \diamond \phi$ . This means that there’s a singleton for $\phi \in (a,x)$ which is a contradiction. Thus $a$ belongs to a cluster which also contains at least the whole $(a,a_1) \cap \mathbb{Q}$ .

Because every point in filtration is either reflexive or irreflexive, these properties show that the result of filtration is a finite list of clusters, may be interspersed by some irreflexive singletons, no two of which are adjacent.

This is approximately what I wrote in my homework. I have not got any feedback yet at the time I am writing this. I hope it got almost full marks (like 8 or more).

Tag: rational

Avoiding traffic lights