Tripolis
Jak nazwać miasto, które ma kształt trójkąta, a układ ulic tworzy trójkątną sieć? Podchodzi mi określenie Tripolis, choć nie jest jednoznaczne, ponieważ równie, a nawet bardziej pasuje ono jako synonim trójmiasta.
Oto małe Tripolis z oznaczoną siecią ulic:
Na trzech skrzyżowaniach (a2, b3, c1) umieszczone są kamery policyjne. Tyle wystarczy, aby wszystkie skrzyżowania były przez władzę obserwowane.
Kolej na inne, większe Tripolis; albo to samo, ale po stu latach:
Piszemy o tym, co ważne i ciekawe
Kwartet solistów
Po przyjęciu wotum zaufania rząd Donalda Tuska kupił sobie parę tygodni spokoju, ale sam premier nie wychodzi z tej operacji wzmocniony. Stracił sporo autorytetu w oczach swoich wyborców, koalicjantów, nawet macierzystej formacji. Czy zdoła jeszcze odwrócić złą passę?
Na ilu co najmniej skrzyżowaniach i na których należy w tym mieście ustawić kamery, aby miały one oko na wszystkie 45 skrzyżowań? Inaczej mówiąc, z każdego skrzyżowania powinna być widziana przynajmniej jedna kamera. Zakładamy oczywiście, że kamera może obserwować także skrzyżowanie, na którym się znajduje.
Komentarze
Na pierwszy rzut oka znajduję rozwiązanie z pięcioma kamerami. Można je umieścić na wiele sposobów, np.: A1, B2, C3, D4, E5
Domyślam się, że wystarczy mniej kamer… zatem szukamy dalej…
Na drugi rzut oka znalazłem następujące rozwiązanie: A9, B5, D1, F3
http://www.gg.pl/dysk/lwSSZ7uVKb9QlgSSZ7uVOZY/tripolis.jpg
Oczywiście to jedno rozwiązanie generuje 5 innych poprzez zastosowanie jednego z automorfizmów naszego miasta.
i1 e2 c6 a4
plus 5 symetrycznych rozwiązań
Czy narożniki to też skrzyżowania? wg mnie na 100% wystarczą 4 kamery ale póki co rozwiązania brak.
Narożnik=skrzyżowanie (powinienem ciutek poprzedłużać ulice :))
mp
PS byłoby ciekawie, gdyby ktoś opisał metodę rozwiązywania. Moim zdaniem rozwiązanie jest tylko jedno (z dokładnością do obrotów i odbić)
kamera stojąca poza ulicą nadbrzeżną miasta obserwuje na niej co najwyżej 2 skrzyżowania. Trójkąt ma bok 9. Jeśli mają wystarczyć 4 kamery, na każdej krawędzi miasta musi stać kamera.
a) jeśli kamera stoi w wierzchołku trójkąta, to nie ma sensu stawiać jej w innym wierzchołku. Czyli, uwzględniając symetrię, rozwiązań wystarczy szukać, stawiając kamerę w górnym wierzchołku i w a2 lub a3 lub a4 lub a5.
b) gdyby żadna kamera nie stała w wierzchołku, aż 3 kamery musiałyby stać na 3 różnych brzegach miasta. Rozpatrzmy wewnętrzny trójkąt o rozmiarze 6. Żaden jego boków nie jest w pełni obserwowany przez 3 kamery z brzegu miasta patrzące „z boku”, bo te kamery „z boku” widzą tylko 1 skrzyżowanie. Pozostała, 4. kamera nie może uzupełnić tego braku. Więc co najmniej 2 kamery muszą stać w a2, h2, b7. Szybko można stwierdzić, że w tym przypadku nie ma rozwiązań. Wracamy do wariantu a)
Jeżeli wiemy, że jedną kamerę należy ustawić w wierzchołku, to zagadnienie redukujemy do problemu „ustawić 3 kamery w tripolisie o rozmiarze 7”. Rozumując analogicznie widzimy, że co najmniej 2 z tych kamer muszą stać na jego brzegach. Łatwo zauważyć, że żadna nie może stać w jego wierzchołku (bo wtedy 2 kamery kontrolowałyby tripolis o boku 5), więc 3 kamery stoją na bokach wewnętrznego tripolis o boku 7. To już dość potężna wskazówka.
Komputer potwierdził, że istnieje tylko 6 rozwiązań. Jedno z nich podałem wczoraj, pozostałe powstają przez odbicie symetryczne i/lub obroty.
Przyznam, że rozwiązanie znalazłem ręcznie przez przypadek, więc ciężko mi opisać sposób jego uzyskania.
Można umieścić 4 kamery na skrzyżowaniach: a6, c /2, e /4, i /1.
Pozdrawiam
A1,B6,D2,F4.
).
Potwierdzam, że z dokładnością do obrotów i odbić, jest to jedyne rozwiązanie (sprawdzone komputerowo
Dla Tripolis o jeden stopień mniejszego (z 36 skrzyżowaniami), również potrzeba 4 kamer.
Trzy kamery wystarczą do obserwacji w Tripolis o 2 stopnie mniejszym (z 28 skrzyżowaniami).
a4, c7, e4, i5
Może niedokładnie opisałam położenie. Inaczej : a4, c68, e26, i19.
Oba zapisy są nietypowe, choć łatwo się zorientować w czym rzecz i rozwiązanie jest poprawne.
Właściwy zapis: a4, c6, e2, i1 (litera oznacza rząd, cyfra – kolejne skrzyżowanie w danym rzędzie).
mp
Tripolis o rozmiarze 8 można załatwić trzema kamerami umieszczonymi na trzech bokach miasta – każda w odległości dwóch skrzyżowań od któregoś wierzchołka.
W Tripolis o rozmiarze 9 umieszczenie kamery w narożniku sprowadza problem do powyższego.
Jest jedno rozwiązanie z dokładnością do odbić i obrotów:
1,1
2,4
4,6
6,2
Jeśli dopuścimy, że każde skrzyżowanie jest „inne” to mamy 6 rozwiązań otrzymanych z powyższego przez obroty trójkąta o 60 stopni i odbicia względem wysokości.
5 kamerkami nie ma problemu, jest mnóstwo rozwiązań,
Doszedłem jednak do wniosku, że 4 kamerkami się nie da.
Dowód: Spójrzmy np. na skrzyżowania na dolnej krawędź trójkąta, jeśli nie będzie na niej żadnej kamerki to jedno skrzyżowanie na pewno nie zostanie obstawione, gdyż każda kamerka widzi dwa z nich.
Postawmy więc kamerkę na dolnej krawędzi (gdziekolwiek poza wierzchołkiem trójkąta), obstawimy wówczas dwa skrzyżowania lewej krawędzi, 7 pozostaje nieobstawionych, więc trzy kamerki to za mało, no chyba, że jedna z nich będzie na lewej krawędzi. Ale wtedy na prawej krawędzi pozostanie nam do obstawienia 5 skrzyżowań mając dwie kamerki do dyspozycji. Więc znowu kamerka musiałaby być na krawędzi. Wtedy pozostanie nam jedna wolna kamerka, którą w żaden sposób nie pokryjemy pozostałych skrzyżowań.
Postawmy więc jedną kamerkę na wierzchołku trójkąta. Niech będzie to górny wierzchołek. Boczne krawędzie mamy załatwione, jednak na dolnej pozostaje 7 skrzyżowań, mamy tylko trzy kamerki więc jedna z nich musi być na tejże właśnie krawędzi. Pozostają nam dwie kamerki i układ skrzyżowań taki, że nie sposób ich obstawić tylko dwoma kamerkami. W tym miejscu dowód się urywa ale jestem na 99% pewien, że nie sposób to rozwiązać. Zapewne właśnie ten 1% to to jedno rozwiązanie o którym pisze gospodarz
Ciekawe jak te minimalne układy wyglądają dla kolejnych n ???
Mając rozwiązanie dla n=9 można łatwo dostrzec rozmieszczenie 3 kamer dla n=8.
W rozwiązaniu, które podałem wcześniej, dla pierwszych współrzędnych jest oczywiście a=1, b=2 i.t.d….
Poniżej link do programu, który w kilkanaście sekund oblicza rozwiązanie:
http://pokazywarka.pl/62y9zs/
Da się obstawić ten trójkąt 4 kamerkami.
Dowód: przedostatni wpis Rubika ma numer 190017, a ostatni – 190026. Oznacza to, że jest tam 8 nieujawnionych wpisów z dobrymi odpowiedziami. Plus 2 dobre między Miodziem a Rubikiem.
A jednak się da… http://bankfotek.pl/view/1849859
Metodologia taka jak w moim „dowodzie”
Musi być kamerka na wierzchołku i na przeciwległej do niego krawędzi. Pozostałe dwie kamerki metoda prób i błędów.
Łatwo zauważyć, że skrzyzowań na brzegach jest 9, kamera potrafi na jeden ‚brzeg’ rzucic dwa promienie. Przy 4 kamerach mamy ‚obstawione’ tylko 8 skrzyżowań, a więc jedna z tych kamer powinna stać na brzegu miasta, co obstawi nam to 9 skrzyżowanie.
Ponieważ miasto jest trójkątne (nie wdając się w głębsze przemyślenia) kamera powinna stać na ostrzu trójkąta, wyeliminuje to nam dwa brzegi 9-skrzyzowaniowe, pozostawiając trzeci brzeg miasta z 7 skrzyżowaniami. Rozumując podobnie (3 kamery, 7 skrzyzowań => kamera musi byc na linii) i delikatnie zgadując, można dość szybko dojść do układu z 4 kamerami.
http://postimg.org/image/ms46x9lgh/
P.S. Przy okazji mamy rozwiązane podobne zadanie dla 3 kamer i miasta z bokiem z 7 skrzyzowaniami.
P.P.S. w tym przypadku cieszę się, że wpisy pojawiają sie rzadziej… mogłem ugryźć to zadanie zaglądając tu raz na tyle dni
choć mam lekko mieszane uczucia, czy to wystarczający argument na taką częstotliwość pojawiania sie wpisów 

Możliwe, że to wynik jakiejś pandemii braku czasu obejmującej, na szczęście, tak duży obszar Polski, od gór po pojezierze
Oczywiście napisałem głupotę, ale z dobrymi intencjami
W pierwszym zdaniu miało być „Tripolis o rozmiarze 7”.
@y-b: Tak, tak, ja też walnąłem tego byka, ale już nie prostowałem, bo wiadomo o co chodzi. Prawnicy mówią na coś takiego „oczywista pomyłka”