1
$\begingroup$

Proof/ logic check on the following entry-level combinatorics problem:

"A bicycle path is 30 miles long, with four rest areas. Prove that either there are two rest areas that are at most six miles from each other, or there is a rest area that is at most six miles away from one of the endpoints of the path."


I decided to proceed with proof by contradiction. Let $$P=\text{there are two rest areas that are at most six miles from each other.}$$ and $$Q=\text{there is a rest area that is at most six miles away from one of the endpoints of the path.}$$ Let $e_1,e_2$ denote the two endpoints and $r_1,r_2,r_3,r_4$ denote the four rest areas. In my mind $$P \equiv \exists !r_i \in \Bbb R \exists !r_j \in \Bbb R(|r_i-r_j| \le 6) \text{ for } i=1,2,3 \text{ and } j=i+1$$ and so $$\lnot P \equiv \forall r_i \in \Bbb R \forall r_j \in \Bbb R(|r_i-r_j| \gt 6)$$Similarly, $$Q \equiv \exists !r_i \in \Bbb R \exists !e_j \in \Bbb R(|r_i-e_j| \le6) \text{ for } i=1,4 \text{ and } j=1,2$$ and so $$\lnot Q \equiv \forall r_i \in \Bbb R \forall e_j \in \Bbb R(|r_i-e_j| \gt 6)$$ Obviously, $\lnot (P\lor Q)\equiv \lnot P\land \lnot Q$. Anyways, that is my logic and so here is my proof...


We shall proceed with proof by contradiction. Let $e_1,e_2 \in \Bbb R$ denote the two endpoints, respectively, and $r_1,r_2,r_3,r_4 \in \Bbb R$ denote the four rest areas, respectively. Suppose there are not two rest courses that are at most six miles from each other and there is not a rest area at most six miles from one of the endpoints. Consider the case where for all four of the rest areas, any given two are greater than six miles apart. Additionally, allow that both rest areas adjacent to endpoints are greater than six miles away from them. Let $d_1=|r_1-r_2|, d_2=|r_2-r_3|,$ and $d_3=|r_3-r_4|$ denote the respective distances between each endpoint. If each $d_i \gt 6$ for $1\le i \le 3$, then $$d=d_1+d_2+d_3 \gt 6+6+6=18.$$ It follows that there is $30-d=d'$ miles of trail left. Let $d_1'=|e_1-r_1|$ and $d_2'=|r_4-e_2|$, where $d_1',d_2' \gt 6$. If $d_1',d_2' \gt 6$, then $d'=d_1'+d_2' \gt 6+6=12$. Hence there are $$d+d' \gt 12+18=30$$miles of trail, which contradicts our given that the trail is 30 miles long. Therefore for the 30 mile long bicycle path with four rest areas, it must be true that there are two rest areas at most six miles from each other, or there is a rest area that is at most six miles away from one of the endpoints of the path.


I don't see much room for error other than possibly my logic. What concerns me is that I didn't really need to use much (if any) combinatorics to solve this - for example, my class is primarily focused on the 'pigeon-hole principal' at this point, and I didn't need it here. Any help would be greatly appreciated, thanks in advance...

$\endgroup$
1
$\begingroup$

This is the pigeon-hole answer:

Divide 30 by 6, you have total 5 6mi sections, of which two are adjacent to the start and end. In the middle you have 3. The 4 stops cannot be put in these 3 without less than 6mi distance. Obviously, you can place 3 then the remaining one should be within one of the start or end sections.

$\endgroup$

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.