Taka mała uwaga: bardziej regularne klasy otrzymujemy, gdy rozpatrujemy zbiór liczb X={0,...,999}, a potem zrobimy poprawkę w klasie 1. Zadanie w formie ogólnej jest bardziej olimpijskie: Mamy zbiór X={0,...,n^m-1}, liczby o długości m cyfr tworzymy w bazie B=n i przy tym zadajemy rozmaite formy pytań j.w. Oczywiście dla n=10 i m=3 mamy nasze zadanie jako szczególny przypadek. Jest szybsza i bezpieczniejsza metoda liczenia, która pozwala na rozwiązanie wersji uogólnionej i podanie wzorów ogólnych. Na przykład problem jaka jest liczba M(n,m) określająca maksymalną liczność klasy tej relacji. Punkty a, pierwsze pół b i c są w każdym przypadku trywialne. Odpowiedź c to oczywiście (n-1)m, czyli seria samych "dziewiątek" (największych cyfr systemu pozycyjnego) określa pułap dla liczby klas (oczywiście w settingu oryginalnym jeszcze -1). Zadanie olimpijskie dodatkowo nawiązywałoby do aktualnego roku, czyli albo n=2025, albo m=2025. A jakby autor zadania był wyjątkowo złośliwy, to np. podałby warunek n+m=2025, tudzież m-n=2025, mn=2025.
@@pianoplayer281 Może jeszcze podam w skrócie i na szybko moją metodę "geometryczną" liczenia tego M(n,m). Dla m=2 i n=10 możemy przypadki rozpisać w takiej tabelce rzędami dla klas (z uwzględnieniem przesunięć dla większych m) i otrzymamy pojedynczą skośną wstęgę wysokości n i szerokości (w najszerszym miejscu) n. Dla m=3, n=10 mamy 10 takich wstęg, każda rozpoczynająca się o 1 niżej niż poprzednia. W przypadku m=4, n=10 mamy dziesięć po dziesięć wstęg, każda grupa zaczyna się o 1 niżej itd. To pozwala już na łatwe sformułowanie ogólnego wzoru na M(n,m) w formie sumy. Przykładowo dla m=3 oraz n=10 mamy M(n,m)=75 i to w dwóch wierszach (dla n nieparzystych będzie pojedynczy wiersz z maximum) i sumując "wstęgami" wyraża się ta liczba tak: 6+7+8+9+10+9+8+7+6+5 albo 5+6+7+8+9+10+9+8+7+6. Zatem metodą na rozwiązanie tego zadania w formie ogólnej i olimpijskiej jest udowodnienie istnienia tej wstęgowej struktury w tabelce klas, wyliczenie indeksu klasy w środku tej tabelki, a następnie przeprowadzenia sumowania n liczb czynników (na odpowiedniej "przekątnej" wstęgi) j.w. w przypadku m=3 (dla m=2 jest to po prostu n), dla m=4 sumowania n grup po n liczb czynników na "przekątnych", itd. dla większych m=5,6,7,.... Widać po prostu, że liczba cyfr w systemie pozycyjnym nie ma dużego wpływu na postać wzoru końcowego, zaś m odpowiada za strukturę "wstęgową" czyli liczbę poziomów sumowań. Można to zapisać w formie rekurencji, no i tyle w kwestii "Matematyki Konkretnej" Donalda Knutha. 😄
@@pianoplayer281 Szybciej i prościej jest napisać program, który to wizualizuje. Można użyć przeglądarki, strony HTML i skryptu JavaScript. Dla bardziej zaawansowanych można też wygenerować skryptem obrazek w SVG. W każdym razie aby zobaczyć tę strukturę już dla n=10, m=4 generowanie komputerowe w zasadzie gwarantuje możliwość zauważenia struktury. Jeśli zaś chodzi o prace ręczne, to ja zrobiłem najpierw myk z przejściem do mniejszych baz, np. do systemu czwórkowego, żeby zobaczyć, iż liczba cyfr nie zmienia "geometrii", a jedynie zmienia wielkość struktur, a dopiero potem rozciągnąłem te wnioski na system dziesiątkowy. Ot takie przyzwyczajenia matematyka stosowanego plus wieloletniego programisty 😛
dla kazdego k liczby 10k,10k+1,...,10k+9 sa w parami roznych klasach abstrakcji, wiec z zasady szufladkowej dirichleta max wielkosc szufladki to nie wiecej niz 1000/10 = 100
Bardzo fajne, ale zbiór masz od 1 do 1000, a nie od 0 do 999. Zbiór musisz rozbić na dwa podzbiory {10...999} i {1,2,3,4,5,6,7,8,9,1000}. {10...999} z Dirichleta tak jak napisałaś + klasy w {1,2,3,4,5,6,7,8,9,1000}. Co daje 99+2 czyli 101. W pytaniu było o więcej niż 101 czyli ok.
Jeżeli 27 to największa możliwa suma cyfr to kolejna powinna być 26 itd. U ciebie kolejny zbiór oznaczyłeś jako A_28 i od tego szedłeś dalej. Dlatego nie zgadza się przy tych dwóch ostatnich.
OOO Mam ta ksiazke moglbys zrobic jakies zadania z grafow albo drzew?
metodą włączeń i wyłączeń można, ale jeśli się jej nie widziało wcześniej to trudno samemu wymyślić
Taka mała uwaga: bardziej regularne klasy otrzymujemy, gdy rozpatrujemy zbiór liczb X={0,...,999}, a potem zrobimy poprawkę w klasie 1. Zadanie w formie ogólnej jest bardziej olimpijskie: Mamy zbiór X={0,...,n^m-1}, liczby o długości m cyfr tworzymy w bazie B=n i przy tym zadajemy rozmaite formy pytań j.w. Oczywiście dla n=10 i m=3 mamy nasze zadanie jako szczególny przypadek. Jest szybsza i bezpieczniejsza metoda liczenia, która pozwala na rozwiązanie wersji uogólnionej i podanie wzorów ogólnych. Na przykład problem jaka jest liczba M(n,m) określająca maksymalną liczność klasy tej relacji. Punkty a, pierwsze pół b i c są w każdym przypadku trywialne. Odpowiedź c to oczywiście (n-1)m, czyli seria samych "dziewiątek" (największych cyfr systemu pozycyjnego) określa pułap dla liczby klas (oczywiście w settingu oryginalnym jeszcze -1). Zadanie olimpijskie dodatkowo nawiązywałoby do aktualnego roku, czyli albo n=2025, albo m=2025. A jakby autor zadania był wyjątkowo złośliwy, to np. podałby warunek n+m=2025, tudzież m-n=2025, mn=2025.
@@imcwaszec937 jak zawsze mogę liczyć na cenne informacje! Dzięki! :)
@@pianoplayer281 Może jeszcze podam w skrócie i na szybko moją metodę "geometryczną" liczenia tego M(n,m). Dla m=2 i n=10 możemy przypadki rozpisać w takiej tabelce rzędami dla klas (z uwzględnieniem przesunięć dla większych m) i otrzymamy pojedynczą skośną wstęgę wysokości n i szerokości (w najszerszym miejscu) n. Dla m=3, n=10 mamy 10 takich wstęg, każda rozpoczynająca się o 1 niżej niż poprzednia. W przypadku m=4, n=10 mamy dziesięć po dziesięć wstęg, każda grupa zaczyna się o 1 niżej itd. To pozwala już na łatwe sformułowanie ogólnego wzoru na M(n,m) w formie sumy. Przykładowo dla m=3 oraz n=10 mamy M(n,m)=75 i to w dwóch wierszach (dla n nieparzystych będzie pojedynczy wiersz z maximum) i sumując "wstęgami" wyraża się ta liczba tak: 6+7+8+9+10+9+8+7+6+5 albo 5+6+7+8+9+10+9+8+7+6. Zatem metodą na rozwiązanie tego zadania w formie ogólnej i olimpijskiej jest udowodnienie istnienia tej wstęgowej struktury w tabelce klas, wyliczenie indeksu klasy w środku tej tabelki, a następnie przeprowadzenia sumowania n liczb czynników (na odpowiedniej "przekątnej" wstęgi) j.w. w przypadku m=3 (dla m=2 jest to po prostu n), dla m=4 sumowania n grup po n liczb czynników na "przekątnych", itd. dla większych m=5,6,7,.... Widać po prostu, że liczba cyfr w systemie pozycyjnym nie ma dużego wpływu na postać wzoru końcowego, zaś m odpowiada za strukturę "wstęgową" czyli liczbę poziomów sumowań. Można to zapisać w formie rekurencji, no i tyle w kwestii "Matematyki Konkretnej" Donalda Knutha. 😄
@ będę musiał to rozpisać na kartce :)
@@pianoplayer281 Szybciej i prościej jest napisać program, który to wizualizuje. Można użyć przeglądarki, strony HTML i skryptu JavaScript. Dla bardziej zaawansowanych można też wygenerować skryptem obrazek w SVG. W każdym razie aby zobaczyć tę strukturę już dla n=10, m=4 generowanie komputerowe w zasadzie gwarantuje możliwość zauważenia struktury. Jeśli zaś chodzi o prace ręczne, to ja zrobiłem najpierw myk z przejściem do mniejszych baz, np. do systemu czwórkowego, żeby zobaczyć, iż liczba cyfr nie zmienia "geometrii", a jedynie zmienia wielkość struktur, a dopiero potem rozciągnąłem te wnioski na system dziesiątkowy. Ot takie przyzwyczajenia matematyka stosowanego plus wieloletniego programisty 😛
dla kazdego k liczby 10k,10k+1,...,10k+9 sa w parami roznych klasach abstrakcji, wiec z zasady szufladkowej dirichleta max wielkosc szufladki to nie wiecej niz 1000/10 = 100
@@yennefer415 o takie rozwiązanie mi chodziło :) dziękuję :)
Bardzo fajne, ale zbiór masz od 1 do 1000, a nie od 0 do 999. Zbiór musisz rozbić na dwa podzbiory {10...999} i {1,2,3,4,5,6,7,8,9,1000}. {10...999} z Dirichleta tak jak napisałaś + klasy w {1,2,3,4,5,6,7,8,9,1000}. Co daje 99+2 czyli 101. W pytaniu było o więcej niż 101 czyli ok.
Sumy cyfr są w przedziale [0;27], a więc klas abstrakcji jest 28 a nie 10
Poza tym Zasda Dirichleta mówi o minimalnej liczbie w szufladkach. Można przecież wszystkie przedmioty umieścic w jednej szufladzce.
@ a nie 1-27? Bo zera nie ma w zbiorze X
Jeżeli 27 to największa możliwa suma cyfr to kolejna powinna być 26 itd. U ciebie kolejny zbiór oznaczyłeś jako A_28 i od tego szedłeś dalej. Dlatego nie zgadza się przy tych dwóch ostatnich.
@@piotrbiskup3507 tak dokładnie. A poza tym wszystkie obliczenia się zgadzają :)