Home › Archief › Universitaire Competities › PUMA › 2009 › Politie op de bus

Politie op de bus

Tags:

Opgave - PUMA 2009 vraag 5

In Projectivistan liggen een aantal bushaltes, en door elk van die haltes lopen meerdere buslijnen. Elke buslijn heeft precies 9 haltes, en voor elke twee bushaltes is er precies één buslijn die in beide stopt. Bovendien hebben elke twee buslijnen precies één halte gemeen. Door recente incidenten wil de politie vaste agenten plaatsen om de veiligheid te verhogen. Ze plaatst in 10 bushaltes een agent, op zodanige wijze dat er nooit drie agenten op dezelfde buslijn staan.

  1. Toon aan dat er door elke halte precies 9 buslijnen gaan.
  2. Startend in een willekeurige halte zonder agent, op hoeveel buslijnen door die halte staan twee agenten? Eén agent? Geen agenten?
  3. Als er al negen agenten geplaatst zijn, met geen drie agenten op eenzelfde buslijn, toon aan dat er dan altijd een halte is waar men de tiende kan plaatsen zonder drie agenten op dezelfde buslijn te hebben.

Een iets kleinere variant, met 3 haltes per buslijn en 4 agenten, kan gevonden worden in het PRIME-logo. Plaatsen we agenten op haltes 1, 3, 5, 7 dan lopen door elke halte waarop een agent staat, twee lijnen met twee agenten, nul lijnen met één agent één lijn met nul agenten.

Oplossing

Ingediend door PRIME

Noem een buslijn respectievelijk onbemand, onderbemand, bemand of overbemand als er respectievelijk $0$, $1$, $2$ of meer dan $2$ agenten op die buslijn staan.

Noem een bushalte onbemand (resp.~bemand) als er geen (resp.~wel een) agent staat.

  1. Kies een willekeurige bushalte en noem ze $p$. We merken eerst op dat het niet mogelijk is dat alle buslijnen door $p$ gaan: had dat wel zo geweest, dan zou door elke andere bushalte $p'$ maar één buslijn gaan (want door $p$ en $p'$ gaat maar één buslijn), terwijl het gegeven zegt dat er meerdere buslijnen door elke bushalte gaan. Dus is er voor elke bushalte $p$ een buslijn $L$ waar $p$ niet op ligt. Door elk van de negen haltes $q_1,...,q_9$ op $L$ gaat er een unieke buslijn tegelijk door $p$ en $q_i$, en elke buslijn door $p$ moet $L$ snijden in één van de bushaltes $q_1,...,q_9$. Dus er gaan precies $9$ bushaltes door $p$, en dit voor elke keuze van $p$.
  2. Iedere agent staat in een bushalte, dus hij staat op precies negen buslijnen. Op geen enkele van die negen buslijnen mogen nog twee andere agenten staan (anders was ze overbemand), dus moeten de negen andere agenten zo staan dat op elk van die negen buslijnen juist één andere agent staat. Iedere buslijn is dus ofwel onbemand, ofwel bemand (onderbemand kan niet). Dus moeten er door elke onbemande bushalte $\frac{10}{2}=5$ bemande buslijnen en $9-5=4$ onbemande buslijnen gaan.
  3. Neem een bemande buslijn en bekijk de $7$ onbemande haltes erop: gezien er zeven agenten buiten deze buslijn staan, moet er vanuit elk van die haltes een oneven aantal onderbemande buslijnen gaan (en dus minsten één). Maar door elke bemande bushalte in Projectivistan gaat ook juist één onderbemande buslijn (want er gaan 8 bemande buslijnen door: één voor elk van de andere agenten), dus elke onbemande halte op een bemande buslijn ligt op juist één onderbemande buslijn.

    Dat wil zeggen dat zodra een onbemande halte op twee onderbemande buslijnen ligt, deze halte op geen enkele bemande buslijn meer kan liggen. Aangezien door elke twee bushaltes een buslijn loopt, is deze halte verbonden met de negen bemande bushaltes, dus lopen door deze bushalte $9$ onderbemande buslijnen (en geen andere). Neem dus het snijpunt van twee onderbemande buslijnen (we zagen daarnet dat die bestaan) en plaats hier een agent. Deze negen lijnen worden nu bemand, dus nu staan er 10 agenten en is toch geen enkele bushalte overbemand.