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

23.11.2019
sobota

Elki

23 listopada 2019, sobota,

Jeśli w zadaniu w roli głównej pojawiają się elementy w kształcie litery „L”, to jest spora szansa, że jego tytuł będzie taki, jak wyżej. Parę „Elek” trafiło się w Omnibusach, ale w Łamiblogu jeszcze nie gościły. Pora na debiut takiego ich rodzaju, który w moim dorobku dotąd się nie pojawiał, choć jest podobny do zamieszczonego w zimowym Omnibusie przed dwoma laty.
Białą część diagramu należy podzielić na L-działki złożone z czterech kratek, uwzględniając oczywiście także odbicia lustrzane, czyli Г-działki. Żadna elka nie może obejmować szarej kratki.

Przykład


Zadanie


W rozwiązaniu wystarczy podać, ile elek znajduje się w diagramie w takiej pozycji jak litera L w tekście.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 23

Dodaj komentarz »
  1. Jest ich wszystkich 22.
    Dwie z nich są normalne (około 9% populacji).

    Czyli dość przyzwoita statystyka.

  2. Są dwie L

  3. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  4. Przed chwilą kliknąłem „Opublikuj komentarz”, lecz go nie widzę… Więc jeszcze raz:

    Są dwie eLki:
    http://pokazywarka.pl/dwie_elki/

  5. Ponieważ zadanie było łatwe, to dodajmy cosik:
    Wszystkich eLek nie da się pomalować trzema kolorami, potrzebne są cztery. Jeśli ten czwarty kolor będziemy używać najoszczędniej, jak tylko się da, to:
    – ile eLek musi być nim pomalowanych?
    – na ile sposobów takie kolorowanie można wykonać?

  6. Takie eLki są tylko dwie. Jedna z nich w prawym rogu diagramu, druga
    mniej więcej centralnie. Zaczyna się w trzecim wierszu piątej kolumnie i kończy się w piątym wierszu i szóstej kolumnie.

  7. @xswedc
    Wystarczy jedna elka inna, ale na ile sposobów – nie wiem. Co najmniej dwa 🙂

  8. W diagramie podstawowym usuwamy dodatkowo cztery białe pola – tak, że tworzą one kwadrat 2×2.
    Cel zadania pozostaje bez zmian: trzeba wypełnić białe pola Elkami.
    Usunięty kwadrat 2×2 można umieścić dowolnie w obrębie białych pól.
    Zastanawiam się, co podpowiada intuicja w takiej sytuacji.

  9. @apartado
    Intuicja podpowiada, aby zostawić ją w spokoju. Kolejne eLki wstawia się w sposób jednoznacznie wymuszony (z dokładnością do kolejności), co oznacza, usunięcie czegokolwiek, co nie jest eLką, uniemożliwi rozwiązanie.

  10. Jest jedno rozwiązanie. 2 elki są jak w tekście

    @apartado
    po wyjęciu kwadratu 2×2 nie da się ułożyć puzzli

  11. Jest jedno rozwiązanie w którym są dwie elki jak w tekście.

  12. @apartado
    Po wyjęciu kwadratu 2×2 nie da się ułożyć puzzli.

  13. A jak będzie jeśli przez „diagram podstawowy” będziemy rozumieli kwadrat 10×10 bez żadnych szarych kwadracików i z takiego czystego kwadratu usuwamy kwadracik 2×2. Czy teraz można ułożyć wszystkie 24 elki?

    Chyba warto by wskazać miejsce, z którego usuwamy kwadrat 2×2. Bo jeśli z dowolnego, to z wyłożeniem 24 elek nie ma problemu.
    mp

  14. Wydaje mi się, że z żadnego miejsca nie możemy wyrzucić bo wyłóżmy naszą posadzkę kafelkami 2×2 z następującym wzorem:
    12
    34
    Wyjmując z dowolnego miejsca kwadrat 2×2 usuwamy zbiór {1,2,3,4}, Natomiast usuwając elkę usuwamy zbiór w którym jedna cyfra się powtarza. A więc kwadrat 10×10 bez kwadracika ma wszystkich cyfr po równo (po 25 sztuk) a w kwadracie bez elki mamy aż trzy różne ilości cyfr. Np 25 jedynek, 23 dwójki oraz 24 trójki i czwórki.

    To ja inaczej: dwie elki pokrywają prostokąt 2×4; usuwając z rogu kwadrat 2×2 bez trudu pokryjemy pozostały obszar 12 prostokątami 2×4.
    mp

  15. „Chyba warto by wskazać miejsce, z którego usuwamy kwadrat 2×2. Bo jeśli z dowolnego, to z wyłożeniem 24 elek nie ma problemu.”
    Można usunąć dowolny kwadrat 2×2 i zawsze rozwiązań są miliony. Jeżeli usuniemy dwa takie kwadraty (nienakładające się) to już nie można ułożyć pozostałej części z Elek.

  16. Wersja zadania z usuwaniem pól:

    Z diagramu 12×12 wypełnionego białymi polami usuwamy cztery pola za pomocą poniższej procedury.

    Rzucamy dwiema kostkami sześciennymi.
    Ilość oczek na każdej z kostek mnożymy przez 2.
    Z diagramu usuwamy pole o współrzędnych policzonych w ten sposób.
    Kostka1 x 2 =>oś X, kostka2 x 2 =>oś Y.
    (Procedurę powtarzamy czterokrotnie).

    Jakie jest prawdopodobieństwo, że tak utworzony diagram można wypełnić Elkami?

    Nie chodzi mi o dokładnie policzone wartości, ale raczej o ocenę typu: „przeważnie można”, „raczej nie można”, „zawsze można” itp
    Czyli: co nam podpowiada intuicja/oszacowanie ?.

  17. Faktycznie można ułożyć 12 prostokątów 2×4, np. tak:
    AAAABBBBAA
    AAAABBBBAA
    BBBBCCCCAA
    BBBBCCCCAA
    AAAABBBBCC
    AAAABBBBCC
    BBBBAAAACC
    BBBBAAAACC
    AAAABBBB
    AAAABBBB
    Zbyt pochopnie zastosowałem trik z kolorowaniem.
    Widać, że zagadnienie jest ciekawe. Czy ktoś zna pokrycie 25 elkami kwadratu 10×10?

    Takie pokrycie nie jest możliwe. Prostokąt axb można pokryć elkami tylko wówczas, gdy iloczyn axb jest wielokrotnością 8 (i oczywiście a,b>1).
    mp

  18. Białego kwadratu 10×10 nie da się wypełnić eLkami. Ogólniej, żadnego prostokąta o polu P=4*n dla nieparzystego n też się nie da.

    Dowód:
    Do każdej kratki prostokąta leżącej w wierszu parzystym wpiszmy 0, natomiast do leżącej w wierszu nieparzystym wpiszmy 1. Wtedy suma cyfr z kratek należących do dowolnej eLki jest zawsze nieparzysta (1 lub 3).
    Liczba n-1 jest parzysta, więc suma liczb z n-1 eLek też jest parzysta. Dodanie sumy ostatniej n-tej eLki da całkowitą sumę nieparzystą. Tymczasem pole P jest parzyste. Sprzeczność.

  19. Zastanawiam się nad dowodem wypełnialności eLkami dowolnej figury zbudowanej z jednostkowych kwadratów. Zakładam, że pole figury jest spójne, czyli, że od dowolnego kwadratu można dojść do każdego z pozostałych robiąc jednostkowe kroki w poziomie lub w pionie. To oznacza, że figura może mieć zarówno „szare pola” wewnątrz, jak i różnego rodzaju wcięcia, wypustki na obwodzie. Może też nie dać się rozciąć na prostokąty o polu będącym wielokrotnością 8.
    Mam w tym tygodniu wyjątkowo mało czasu , więc pokażę tylko kilka początkowych przemyśleń:

    Mamy dwa prostokąty, z których w dwóch narożnikach usunąłem po dwa kwadraty. Pola obydwu figur są równe 44, czyli mogą pomieścić po 11 eLek. Którą z nich można wypełnić eLkami?
    http://pokazywarka.pl/linka1/
    Łatwo to wywnioskować stosując metodę z dowodu przedstawionego wcześniej dla prostokątów: wypełniamy co drugi wiersz jedynkami i liczymy sumę. W lewej figurze wynosi ona 23, a prawej 22. 11 eLek daje sumę nieparzystą, więc można wypełnić tylko figurę lewą (suma 23).
    http://pokazywarka.pl/linka2/

    Zrobiłem też parę figur z podwójnymi wcięciami i wypustkami. Którą/które z tych trzech figur można zaeLkować?
    http://pokazywarka.pl/linka3/
    W każdej z nich suma z eLek wynosi 23 lub 25, więc wszystkie!
    http://pokazywarka.pl/linka4/

    Ale nie rozpędzajmy się… Są też takie figury:
    http://pokazywarka.pl/linka5/
    Niby suma eLek to 19, a nijak nie da się tego wypełnić! To może tak:
    http://pokazywarka.pl/linka6/
    Wypełniłem zerami i jedynkami nie tylko wiersze, ale również kolumny. Jest oczywiste, że i tu i tu suma z eLek musi być nieparzysta, tymczasem dla kolumn jest parzysta! – nie ma więc wypełnienia.

    To były przypadki geometrycznie proste. Są jednak figury wredne, dla których, mimo prawidłowych sum i wierszach i w kolumnach wypełnienie nie istnieje.
    http://pokazywarka.pl/linka7/
    Zastanawiam się, jak takie przypadki ująć w sposób sformalizowany, godny umieszczenia w jakimś ogólnym dowodzie. LOL Za twórcze pomysły Ogólnoświatowe Stowarzyszenie ELkowców będzie wdzięczne…

  20. @OlaGM
    „Wystarczy jedna elka inna, ale na ile sposobów – nie wiem. Co najmniej dwa”.

    Dokładnie dwa 🙂

  21. Problem wypełnienia płaszczyzny figurami o różnych kształtach jest pochodzenia, jeśli nie antycznego, to co najmniej średniowiecznego.
    Nie znalazłem jednak przypadku analizy dla eLek złożonych z czterech kwadratów. Są, owszem, w Internecie algorytmy dla „małych” eLek, czyli figur złożonych z trzech kwadratów tworzących kąt prosty, ale taki problem jest bardzo łatwy do ogarnięcia, więc nie jest tu przedmiotem rozważań.
    Jest więc nisza, w którą każdy może próbować się wcisnąć. W wiadomości 193766 podałem przykład figury
    http://pokazywarka.pl/linka7/
    dla której gołym okiem widać, że jest nie-eLkowata, ale… jak to wyliczyć/udowodnić/wykazać?
    Przyznam, że problem trochę mnie wessał, lecz po dłuższych przemyśleniach nie mam rokującego konceptu. Być może nie ma rozwiązania analitycznego, a może też istnieje takie, lecz ja go nie widzę. Jest to w stu procentach zgodne z ideą Godla, więc…
    Pomysły?

  22. @xswedc

    Myślę, że przyda się znajomość odpowiedzi na pytanie, które zadałem w komentarzu numer 193763: „Wypełnienie tak utworzonej planszy jest NIEMOŻLIWE”.
    Teraz wystarczy wymyślić, jaką wspólną cechę mają pola wyznaczane rzutami kostek.
    Podpowiedź: pomoże w tym szachownica.

css.php