2
$\begingroup$

enter image description here

A certain city has 10 bus routes. Is it possible to arrange the routes and the bus stops so that if one route is closed, it is still possible to get from anyone stop to any other (possibly changing along the way), but if any two routes are closed, there are at least two stops such that it is impossible to get from one to the other?

Given the solution above, why did the authors feel compelled to answer: Yes. Consider 10 straight lines in the plane, no 2 are parallel & no 3 are concurrent. Let lines be bus routes & let points of intersection be stops. We get from anyone stop to any other (if the stops lie on 1 line, w/o changing; & if not, then with just 1 change). If we discard 1 line, it's still possible to get from anyone stop to any other, changing buses at most once. However, if we discard 2 lines, then 1 stop-their point of intersection-will have no bus routes passing thru it, & it'll be impossible to get from this stop to any other.

Source: A. M. Yaglom and l. M. Yaglom CHALLENGING MATHEMATICAL PROBLEMS WITH ELEMENTARY SOLUTIONS Volume II Problems From Various Branches of Mathematics Translated by James McCawley, Jr. Revised and edited by Basil Gordon DOVER PUBLICATIONS, INC. NEW YORK

$\endgroup$
7
  • 1
    $\begingroup$ Yes, the answer is correct. $\endgroup$ Jun 9, 2019 at 6:12
  • 1
    $\begingroup$ My guess, Joe, is that when they wrote "changing", they meant "changing once". $\endgroup$ Jun 9, 2019 at 13:04
  • $\begingroup$ Your answer is correct and fine. It is possible the authors just didn't think of this solution and thus put their solution into the book. Everybody overlooks something every now and then. $\endgroup$
    – auscrypt
    Jun 9, 2019 at 15:30
  • $\begingroup$ My solution fails to meet the requirement, "If we discard 1 line, it's still possible to get from anyone stop to any other, changing buses at most once." $\endgroup$ Jun 10, 2019 at 0:55
  • $\begingroup$ Gerry, your interpretation of the wording is what makes the problem sufficiently complex. Thanks. $\endgroup$ Jun 10, 2019 at 0:58

1 Answer 1

1
$\begingroup$

Let’s go back to the roots.

I guess this is a problem 101 at p.53 from a book “Non-elementary problems in elemntary presentation” by A.M. Yaglom & A.M. Yaglom (“Неэлементарные задачи в элементарном изложении” by Акива Моисеевич и Исаак Моисеевич Яглом), Moskow, State publishing house of technical and theoretical literature, 1954.

enter image description here

It is the same problem which you quoted and your solution fits for it.

Also author’s solution is the same which your quoted.

enter image description here

I can explain the situation as follows. The problem is contained in a subsection devoted to arrangements of points and planes and the authors say that this topic was developed in XIX century into a big science, called projective geometry. The questions, considered in problems 101–107 belong to relatively narrow topic of projective geometry, namely, to so-called configuration theory, which has a big importance in modern mathematics. This explains the solution, but it is still surprising how your simple solution was missed.

But I guess that this problem probably was taken from Moskow mathematical competition from 1950 (9-10 forms, second round, problem 4):

Можно ли провести в городе $10$ автобусных маршрутов и установить на них остановки так, что какие бы $8$ маршрутов ни были взяты, найдётся остановка, не лежащая ни на одном из них, а любые $9$ маршрутов проходят через все остановки.

(Given a city, can we arrange $10$ bus routes and set bus stops on them such that for each 8 routes there is a bus stop not belonging to any of the routes, but each $9$ routes contain all stops).

The proposed solution is the same as Yagloms’:

Проведём $10$ попарно пересекающихся прямых, никакие три из которых не пересекаются в одной точке. Пусть маршруты проходят по этим прямым, а остановками служат точки пересечения прямых. Любые $9$ маршрутов проходят через все остановки, поскольку через каждую остановку, лежащую на оставшейся прямой, проходит одна из $9$ прямых, соответствующих этим маршрутам. Любые $8$ маршрутов не проходят через остановку, которая является точкой пересечения оставшихся двух маршрутов.

But although this problem looks similar to Yagloms’, its essence is different! It asks not about connectivity of a graph with removed edges, but about incidence requirements. The geometric solution satisfies them, whereas the cyclic graph doesn’t.

$\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.