Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko

29.09.2016
czwartek

Przepływy

29 września 2016, czwartek,

Przed ośmiu laty zamieściłem w Łamiblogu zadanie zainspirowane pierwszym prawem Kirchhoffa. Chodziło o oznaczenie krawędzi grafu skierowanego liczbami od 1 do 13 tak, aby suma liczb „wpływających” do  i „wypływających” z   każdego węzła (wierzchołka) były równe. Oto znacznie skromniejszy przykład takiego zadania (liczby od 1 do 6, jedna ujawniona):
Pry_1
Przykład jest niemal trywialny, ale wraz ze wzrostem liczby krawędzi stopień zawiłości zadania szybko rośnie. Inaczej mówiąc, staje się ono coraz bardziej kombinacyjne. Ponieważ zamieszczone wówczas zadanie pochodziło z mistrzostw świata, więc wywołało dyskusję na temat sensu obecności takich zadań na turniejach. Jeśli bowiem próbowanie i błądzenie zaczyna dominować nad logiką, to zawody z założenia intelektualne zmieniają się w loterię. Istotny jest więc nie tyle rodzaj zadania, co stopień jego komplikacji, który powinien być optymalny, czyli taki, aby w trakcie rozwiązywania logika stanowiła danie główne, a kombinowanie tylko przystawkę lub deser. Co innego natomiast, gdy główkujemy bez współzawodnictwa, dla relaksu. Wówczas nieco większa (ale bez przesady) porcja kombinowania bywa całkiem przyjemna, a poza tym można poszukać jakiejś sprytnej metody, która pozwoli ominąć lub znacznie ograniczyć wyboiste próby, aby w miarę prostą logiczno-rachunkową ścieżką dotrzeć do celu. Być może taką ścieżkę uda się znaleźć w poniższym „przepływowym” zadaniu (w kółkach powinny się pojawić liczby od 1 do 12, trójka już jest), które pochodzi z 24-godzinnych mistrzostw w Budapeszcie. Warto dodać, że z 28 tytanów intelektu i kondycji, startujących w tych mistrzostwach, nie rozwiązał go nikt.
Pry_2
Kom

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 9

Dodaj komentarz »
  1. Rozwiązanie znalezione przez komputer:
    a=3, b=5, c=12, d=1, e=8, f=6, g=11, h=9, i=4, j=10, k=7, l=2

    A w głowie? 20 minut myślenia nie przyniosło ani rezultatu, ani nawet pomysłu jak się za to zabrać…

  2. Trochę logiki trzeba było użyć – głównie do tego, żeby rozpatrzyć, gdzie może być 1 i 2. Są 4 takie miejsca: B, D, I, L. Potem metodą prób i błędów: B1 – nic z tego; D1 – udało się wszystko dopasować.
    A3; B5; C12; D1; E8; F6; G11; H9; I4; J10; K7; L2

  3. Niech mnie kule biją…
    Zrobiłem za pierwszym razem, niestety nie ma się czym chwalić, bo to raczej szczęście niż jakieś logiczne myślenie.

    http://i.imgur.com/1Vye2MK.png

    Ile wynosi prawdopodobieństwo takiego strzału?

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. A3,B5,C12,D1,E8,F6,G11,H9,I4,J10,K7,L2

    W ciągu kilku minut ustaliłem, że 12-ką może być tylko C albo J.
    Spróbowałem C12…
    … i w pierwszej próbie rozmieściłem całą resztę.

  6. Rozwiązanie to:
    A=3,
    B=5,
    C=12,
    D=1,
    E=8,
    F=6,
    G=11,
    H=9,
    I=4,
    J=10,
    K=7,
    L=2,

    Jeśli ktoś jest zainteresowany to kod programu znajdzie na
    https://github.com/Jacwing/Przeplywy

  7. @kroQ
    Zależy gdzie się strzela. Np. jakie jest prawdopodobieństwo, że strzelając w powietrze na wiwat, strzelę sobie w stopę? (odpowiedź niżej)

    B = E-3 = F-D
    C = 3+H = D+G
    D = F-B = C-G
    E = 3+B = J-L
    F = B+D = J-I
    G = I+K = C-D
    H = K+L = C-3
    I = G-K = J-F
    J = E+L = F+I
    K = G-I = H-L
    L = J-E = H-K

    B+C = J+K = F+G = E+H
    D+I = 3+L = C-K = J-B
    F-E = D-3 = H-G = L-I
    M. (wieloma) in. takie mamy układy równań. Po analizie można ograniczyć np. ostatnie do:
    F-E = D-3 = H-G = L-I = {-2; -1; 1; 2; 3; 4}
    (a to dlatego, że G,I,K!=3, G=I+K>=5, H=C-3<=9, z czego wynika: H-G <= 5)

    Do sprawdzenia jest 6 możliwości i chyba przy każdej "dosyć" szybko da się dojść do sprzeczności lub końcowego rozwiązania.

    Wracając do pytania o prawdopodobieństwa: jeśli ktoś mi każe wybrać "losowo", którąś wartość z mojego zbioru, to na pewno nie wezmę pierwszej z brzegu. Wówczas P(x=-2) = 0.
    Jeśli natomiast do zadania zabiorę się systematycznie, P(x=-2) = 1.

    Tyle teoria. W praktyce zacząłem systematycznie, wybrałem -2 i doszedłem do sprzeczności. Później zacząłem wybierać chaotycznie kolejne wartości i również dostałem sprzeczności. Wreszcie się zniechęciłem i wysmażyłem algorytm, który zrobił wszystko za mnie. Okazało się, że powinienem wybrać -2 i do żadnej sprzeczności nie dochodzić. Niestety u mnie prawdopodobieństwo realizacji takiej powinności jest bliskie zeru.

    A=3
    B=5
    C=12
    D=1
    E=8
    F=6
    G=11
    H=9
    I=4
    J=10
    K=7
    L=2

    Posłowie:
    Drugą grupę z moich równań można osiągnąć przez przekształcenia pierwszej, ale łatwiej je po prostu odczytać z grafu. Wybieramy dowolny zbiór wierzchołków i sumujemy krawędzie przechodzące z naszego zbioru do pozostałych lub na odwrót (te drugie z minusem). Zresztą w ten sam sposób powstała pierwsza grupa równań – tam zbiorem był pojedynczy wierzchołek. Jeszcze odpowiednio pogrupować wyrazy po obu stronach równań i gotowe. A przy odrobinie wprawy końcowe równania widać na grafie gołym okiem.

  8. A=3, B=5, C=12, D=1, E=8, F=6, G=11, H=9, I=4, J=10, K=7, L=2

  9. A,B,C,…,K,L= 3,5,12,1,8,6,11,9,4,10,7,2.
    Można to znaleźć ręcznie w stosunkowo rozsądnym czasie.
    Zauważamy, że najlepszymi kandydatami na 12 są C i J.
    Ponieważ bliżej A=3 jest C, więc od C zaczniemy próby. Następną dobierana zmienną będzie B. Potem wyliczamy E i H. Teraz musimy próbować kolejne L dla których obliczamy J oraz K. Po czym następna seria prób dla I. Tak więc cały układ ma tylko cztery zmienne niezależne.
    W naszej analizie najlepiej (moim zdaniem) jest przyjąć C,B,L,I, właśnie w takiej kolejności. Zaczynamy więc C=12. Wyliczamy H=9. Dla B próbujemy kolejno 1,2,3,4, i otrzymujemy sprzeczności. Dla B=5 mamy E=8 i teraz probujemy L=1 sprzeczność.L=2 to K=7, J=10. Teraz rozwidla się I.
    Odrzucamy kolejno I=1,2,3 (bo sprzeczności) i wreszcie I=4 pozwala wyliczyć resztę zmiennych.
    Oczywiście relatywna szybkość tej metody opiera się na zaufaniu do autora zadania, że przyjął C=12 a nie np. C=10. 🙂

  10. 3 5 12 1 8 6 11 9 4 10 7 2
    „Logika” komputera.

css.php