Pytania otagowane jako puzzles

6
Siatka
Aktualizacja : Zestaw przeszkód (tj. „Bariera” NxM pomiędzy rozmiarami siatki do barwienia i bezbarwności) dla wszystkich 4-kolorów bez monochromatycznych prostokątów jest teraz znany . Czy ktoś ma ochotę wypróbować 5 kolorów? ;) Z teorii Ramseya wynika następujące pytanie . Rozważmy -coloring z n -by- m wykres siatki. Występuje, gdy cztery …
8
Jaka jest minimalna liczba bitów wymagana do przechowywania układanki sudoku?
Uwaga: chodzi o standardową łamigłówkę sudoku 9x9. Rozwiązanie musi obsługiwać tylko rozwiązane, legalne zagadki . Dlatego rozwiązanie nie musi obsługiwać pustych komórek i może polegać na właściwościach rozwiązanej łamigłówki sudoku. Zastanawiałem się nad tym, ale nie mogłem wymyślić odpowiedzi, z której byłbym zadowolony. Naiwne rozwiązanie wykorzystywałoby jeden bajt na każdą …
2
Ograniczenia wejściowe nieskończonych sekwencji
Oto łamigłówka, której nie udało mi się rozwiązać. Chciałbym wiedzieć, czy ten problem jest już znany, czy ma łatwe rozwiązanie. Możliwe jest zdefiniowanie biosekcji przy użyciu właściwości dwuczęściowych kategorii zamkniętych. Andrej Bauer zamieścił wyjaśnienie, co to znaczy na swoim blogu jako „ Konstruktywny klejnot: żonglerka wykładnicza ”.3N≅5N3N≅5N 3^\mathbb{N} \cong 5^\mathbb{N} …
2
Czy istnieją lokalne maksima w liczbie ruchów wymaganych do rozwiązania Kostki Rubika?
Peter Shor poruszył interesujący punkt w związku z próbą odpowiedzi na wcześniejsze pytanie dotyczące złożoności rozwiązania kostki Rubika n×n×nn×n×nn \times n \times n . Podjąłem dość naiwną próbę wykazania, że ​​musi być zawarta w NP. Jak zauważył Peter, moje podejście w niektórych przypadkach zawodzi. Jednym z potencjalnych przypadków takiego wystąpienia …
1
Konstrukcja wykresów, w których każda para wierzchołków ma unikalnego wspólnego sąsiada
Niech będzie prostym wykresem na wierzchołkach bez wierzchołka stopnia . Załóżmy, że dla dowolnych dwóch wierzchołków istnieje unikalny wierzchołek przylegający do nich obu. Jest to ćwiczenie z Kursu kombinatoryki van Linta i Wilsona, aby udowodnić, że taki wykres jest regularny.GGGnnn(n>3)(n>3)(n > 3)n−1n−1n − 1GGG Moje pytanie brzmi jednak, czy w …
2
Rozwiązywanie labiryntu z numerami
Mój 8-latek znudził się tworzeniem konwencjonalnych labiryntów i zaczął tworzyć warianty, które wyglądają tak: Chodzi o to, aby zacząć od x i osiągnąć normalne zasady. Dodatkowo możesz „przeskoczyć” z dowolnej liczby całkowitej aaa na inną liczbę całkowitą bbb , ale musisz zapłacić |a−b||a−b||a-b|dolarów za przywilej. Celem jest rozwiązanie labiryntu przy …
1
Układanka do cięcia pałeczek
Problem: Dostajemy zestaw drążków o długości całkowitej. Całkowita suma ich długości wynosi n (n + 1) / 2. Czy możemy je rozbić, aby uzyskać kije wielkości czasie wielomianowym? 1 , 2 , … , n1,2),…,n{1,2,\ldots,n} Co zaskakujące, jedynym odniesieniem do tego problemu jest starożytna dyskusja: http://www.iwriteiam.nl/cutsticks.html Co jeszcze wiadomo na …
1
Jak trudna jest binarna łamigłówka Sudoku?
Sudoku jest dobrze znaną łamigłówką, która jest kompletna NP. Sudoku Binarne to wariant, który dopuszcza tylko cyfry i 1 . Zasady są następujące.000111 Każdy wiersz i każda kolumna musi zawierać równą liczbę zer i jedynek. Każdy wiersz i każda kolumna jest unikalny. Żaden wiersz ani kolumna nie zawiera kolejnych potrójnych …
2
Interaktywny dowód liczby Boga?
Ostatnio uczyłem się o interaktywnych dowodach i zastanawiałem się, czy cała ta sprawa była jedynie ciekawostką teoretyczną, czy też miała jakieś praktyczne zastosowania. Myślałem, że zacznę od przykładu, który przyszedł mi do głowy pod prysznicem: Ostatnio ogłaszano, że „liczba Boga” = 20. (Liczba Boga to minimalna liczba kroków potrzebnych do …
1
Jaka jest złożoność (być może zwięzłego) Nurikabe?
Nurikabe to układanka wypełniająca siatki oparta na ograniczeniach, luźno podobna do Saperów / Nonogramów; liczby są umieszczane na siatce, która ma być wypełniona wartościami włączania / wyłączania dla każdej komórki, przy czym każda liczba wskazuje region połączonych komórek „on” o tej wielkości, a także pewne drobne ograniczenia w obszarze komórek …
2
Złożoność ukrytej łamigłówki wielokątów na kwadratowych siatkach?
Hiroimono jest popularną łamigłówką . Interesuje mnie złożoność obliczeniowa powiązanej układanki.N.P.NPNP Problemem jest: Dane wejściowe : Biorąc pod uwagę zestaw punktów na siatce kwadratowej x i liczbie całkowitejn knnnnnnkkk Pytanie : Czy istnieje wielokąt prostoliniowy (jego boki równoległe do osi lub ) taki, że liczba punktów na rogach wielokąta wynosi …
1
Ograniczanie liczby krawędzi między wykresami gwiazdowymi, tak że wykres jest płaski
Mam wykres solGGktóry składa się tylko z wykresów gwiazd. Wykres gwiezdny składa się z jednego centralnego węzła mającego krawędzie do każdego innego węzła w nim. PozwolićH.1,H.2), ... ,H.nH1,H2,…,HnH_1, H_2, \ldots, H_n być różnymi wykresami gwiazd o różnych rozmiarach, które są obecne w solGG. Nazywamy zbiór wszystkich węzłów, które są centrami …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.