Matematyka.pl

Na ile sposobów można wybrać \(\displaystyle{ 25}\) liczb spośród liczb \(\displaystyle{ 1,2,...,50}\) , że dla dowolnych dwóch różnych liczb, które wybieramy, żadna nie jest dzielnikiem drugiej.

Klasy abstrakcji

Podobne...

arek1357 pisze: 21 sty 2022, o 09:32 Klasy abstrakcji

Podobne...

Czyżbyś sugerował że że relacja podzielności jest relacją równoważności?

To może ty bo ja nie, ale między tymi zadaniami jest pewna subtelna zależność (podobieństwo między zadaniowe)...

Jeżeli tego nie widzisz to trudno...

No nie widzę. Ale gdybyś mógł napisać coś, co pytającemu dałoby jakąś wskazówkę, to pewnie byłby Ci wdzięczny..

NB branchiostoma lanceolatum i homo sapiens też łączy pewna subtelna zależność.

Dobrze więc naświetlę sprawę w sposób bardziej ogólny i pokażę jak powinno wyglądać z dzielnikami sprawa dla dowolnego \(\displaystyle{ n}\)...

1. dla \(\displaystyle{ n=1}\) nie ma żadnych par, więc nie ma o czym mówić

2. Dla \(\displaystyle{ n=2}\) mamy:\(\displaystyle{ \left\{ 1,2\right\} }\) - para jest jedna:\(\displaystyle{ \left\{ 1,2\right\} }\) ale jedynka jest dzielnikiem każdej liczby więc wynik będzie zero...

3.\(\displaystyle{ n=3}\) mamy:\(\displaystyle{ \left\{ 1,2,3\right\} }\) para która nas interesuje to:\(\displaystyle{ \left\{ 2,3\right\} }\) więc tu mamy jedną

możliwość...


4. Dla: \(\displaystyle{ n=4 }\) mamy: \(\displaystyle{ \left\{1,2,3,4 \right\} }\) par interesujących jest dwie: \(\displaystyle{ \left\{ 2,3\right\} \left\{ 3,4\right\} }\)

Jak widać pary w których występuje jedynka odpadają mamy więc:

\(\displaystyle{ a_{2}=0, a_{3}=1, a_{4}=2, a_{5}=5, a_{6}=7, a_{7}=12,... }\)

Teraz jak tworzyć takie pary, no więc w zestawie typu:

\(\displaystyle{ \left\{ 1,2,3,4,5,...,n\right\} }\) , ponieważ jedynka nie może być w żadnej parze mamy na początek:

\(\displaystyle{ {n-1 \choose 2} }\) - pary z których odejmujemy pary "niewygodne" czyli typu:

\(\displaystyle{ \left\{ 2,4\right\} , \left\{ 2,6\right\} , \left\{ 2,8\right\} ,....}\)

\(\displaystyle{ \left\{ 3,6\right\} , \left\{ 3,9\right\} , \left\{ 3,12\right\} ,....}\)

................................................................................................

\(\displaystyle{ \left\{ k,2k\right\} , \left\{ k,3k\right\} , \left\{ k,4k\right\} ,....}\)

Par typu:

\(\displaystyle{ \left\{ 2,4\right\} , \left\{ 2,6\right\} , \left\{ 2,8\right\} ,....,\left\{ 2,2s_{1}\right\} }\)

jest: \(\displaystyle{ s_{1} , 2 \le s_{1} \le \left[ \frac{n}{2} \right] }\)

Par typu:

\(\displaystyle{ \left\{ 3,6\right\} , \left\{ 3,9\right\} , \left\{ 3,12\right\} ,....,\left\{ 3,3s_{2}\right\} }\)

jest: \(\displaystyle{ s_{2} , 2 \le s_{2} \le \left[ \frac{n}{3} \right] }\)

itd... aż do:

\(\displaystyle{ \left\{ k,2k\right\} , \left\{ k,3k\right\} , \left\{ k,4k\right\} ,....,\left\{ k,ks_{k-1}\right\} }\)

jest: \(\displaystyle{ s_{k-1} , 2 \le s_{k-1} \le \left[ \frac{n}{k} \right] }\)

I teraz zliczmy poszczególne odrzucone pary , pary z dwójkami najpierw czyli:

\(\displaystyle{ n=2 ,3,4,5,6,7,...}\)

Par odrzuconych z dwójkami mamy:

\(\displaystyle{ 0,0,1,1,2,2,3,3,...}\)

nazwijmy go ciągiem: \(\displaystyle{ r_{s}^{(2)}}\)

Ciąg ten powstaje rekurencyjnie :

\(\displaystyle{ r_{2}^{(2)}=0, r_{3}^{(2)}=0, r_{4}^{(2)}=1,...}\)

rekurencyjnie:

\(\displaystyle{ r_{s+1}^{(2)}=r_{s}^{(2)}+t_{s}^{(2)}, r_{0}^{(2)}=0 , 2 \le s \le n-1 }\)

Ciąg typu: \(\displaystyle{ t_{s}^{(2)}, s \ge 2}\) wprowadziłem go bo będą to sekwencje zer i jedynek: \(\displaystyle{ 0,1,0,1,0,1,...}\)

Wprowadziłem go bo łatwiej poszukać na niego jawną sekwencję (jeszcze o nim powiem coś)

Analogicznie:

Gdy wyrzucamy trójki to będziemy mieli analogiczny ciąg:


\(\displaystyle{ r_{s+1}^{(3)}=r_{s}^{(3)}+t_{s}^{(3)} , r_{0}^{(3)}=0, 2 \le s \le n-1 }\)

gdzie teraz: \(\displaystyle{ t_{s}^{(3)}=0,0,1,1,0,0,1,1,...}\) przy trójce będzie szedł co dwa itd...

dla dowolnego \(\displaystyle{ k}\) mamy:

\(\displaystyle{ r_{s+1}^{(k)}=r_{s}^{(k)}+t_{s}^{(k)} , r_{0}^{(k)}=0, 2 \le s \le n-1 }\)

\(\displaystyle{ t_{s}=0,0,0,...,0,1,1,1,...,1,...}\) tam są sekwencje po.: \(\displaystyle{ k-1}\) zer i jedynek na przemian...


Więc ostatecznie mamy wzór:

\(\displaystyle{ a_{n}= \sum_{j=2}^{ \infty } r_{n}^{(j)}}\)

gdzie:

\(\displaystyle{ r_{s+1}^{(k)}=r_{s}^{(k)}+t_{s}^{(k)} , r_{0}^{(k)}=0, 2 \le s \le n-1 }\)

Z obserwacji zauważyłem, że funkcja charakterystyczna ciągów typu: \(\displaystyle{ t_{n}^{(k)}}\) jest:

dla:

\(\displaystyle{ 010101...: \frac{x}{\left( 1-x\right)\left( 1+x\right) } }\)

\(\displaystyle{ 001100110011...: \frac{x^2}{\left( 1-x\right)\left( 1+x^2\right) } }\)

\(\displaystyle{ 000111000111000111...: \frac{x^3}{\left( 1-x\right)\left( 1+x^3\right) } }\)

\(\displaystyle{ 000011110000111100001111...: \frac{x^4}{\left( 1-x\right)\left( 1+x^2+x^4\right) } }\)

\(\displaystyle{ 000001111100000111110000011111...: \frac{x^5}{\left( 1-x\right)\left( 1+x^2+x^5\right) } }\)

\(\displaystyle{ 000000111111000000111111000000111111...: \frac{x^6}{\left( 1-x\right)\left( 1+x^2+x^4+x^6\right) } }\)

\(\displaystyle{ 000000011111110000000111111100000001111111...: \frac{x^7}{\left( 1-x\right)\left( 1+x^2+x^4+x^7\right) } }\)

.................................................................................................................................................................

Jak widać też mamy pewną zależność co łatwo zauważyć...


Obliczyłem ilość par w których , żadna liczba nie jest dzielnikiem drugiej czyli tej z pary, bo jak wiadomo wszystkich par w tym zadaniu jest:

\(\displaystyle{ {50 \choose 2} }\)

Dodano po 19 minutach 32 sekundach:
Oczywiście liczyłem tylko pary ... bo wydało się to dość ciekawe...

Dodano po 11 minutach 7 sekundach:
Co do zadania natomiast to bym najpierw wypisał wszystkie liczby większe od \(\displaystyle{ 25}\) tam żadna para się nie dzieli a potem próbowałbym coś dokoptować żeby było 25 tych liczb

Dodano po 4 minutach 3 sekundach:
Albo jeszcze wypisać wszystkie liczby pierwsze od dwa do 47 a jest ich 15 a potem dokładać inne jak najwięcej...

Dodano po 7 minutach 2 sekundach:
Choć teraz można się zastanowić, czy w każdym zestawie 25 liczb (mniejszych lub równych 50) nie znajdzie się dwie gdzie jedna dzieli drugą ...

Dodano po 11 godzinach 9 minutach 5 sekundach:
Jeszcze jedno bo popatrzyłem na to inaczej i w tym zadaniu pierwszy zestaw może być:

\(\displaystyle{ \left\{ 26,27,28,...,50\right\} }\)

Potem wyrzucamy po jednym i wstawiamy mniejszy w ten sposób:

\(\displaystyle{ \left\{ 25,26,...,49\right\} }\)

\(\displaystyle{ \left\{ 24,26,...,47,49,50\right\} }\)

\(\displaystyle{ \left\{ 23,,26,...,45,47,48,49,50\right\} }\)

........................................................................

\(\displaystyle{ \left\{ 17,26,...,33,35,...,49,50\right\} }\)

A teraz te pierwsze liczby w tych zestawach bierzemy po dwa, trzy, cztery,..., dziesięć i wychodzi:

\(\displaystyle{ 10+ {9 \choose 2} + {9 \choose 3} +...+ {9 \choose 9} }\)

może są jeszcze jakieś inne na razie tyle widzę, oczywiście pierwsza część ego co rozpisałem jest luźno związana ze strikte treścią zadania ale nie omieszkałem policzyć wszystkie pary dla ogólnego przypadku...

1632 sposoby.

Niech \(\displaystyle{ f(X, m)}\) oznacza ilość sposobów, na ile ze zbioru \(\displaystyle{ X}\) można wybrać \(\displaystyle{ m}\) liczb tak, by żadna nie dzieliła innej.
- Jeśli \(\displaystyle{ |X| < m}\), to nie ma czego wybierać i \(\displaystyle{ f(X, m) = 0}\).
- Jeśli \(\displaystyle{ m = 1}\), to można wziąć cokolwiek i \(\displaystyle{ f(X, 1) = |X|}\).
- Jeżeli żaden z tych dwóch warunków nie zachodzi, oznaczmy przez \(\displaystyle{ x}\) najmniejszy element zbioru \(\displaystyle{ X}\) i zdefiniujmy \(\displaystyle{ X_1 = X \setminus \{x\}}\) oraz \(\displaystyle{ X_2 = S \setminus \{kx : k = 1, 2, \ldots, \lfloor \frac 1 x \max X\rfloor\}}\) (albo bierzemy element \(\displaystyle{ x}\), albo nie). Mamy \(\displaystyle{ f(X, m) = f(X_1, m) + f(X_2, m-1)}\), a to już można zaimplementować w swoim ulubionym języku programowania.

Dla \(\displaystyle{ m = 25}\) oraz \(\displaystyle{ X = \{1, 2, \ldots, 2m\}}\) zależność rekurencyjna została użyta 590 167 razy, więc nie widzę jak można byłoby to zadanie policzyć na palcach.

Fakt sporo się tego produkuje w taki sposób ...

Dodano po 1 minucie 54 sekundach:
Podoba mi się ta rekurencja wygląda ok...ale z jawną implementacją byłoby gorzej...

Dodano po 1 godzinie 19 minutach 45 sekundach:
Tam powinno być chyba X zamiast S...?

Flype pisze: 22 sty 2022, o 09:15 Dla \(\displaystyle{ m = 25}\) oraz \(\displaystyle{ X = \{1, 2, \ldots, 2m\}}\) zależność rekurencyjna została użyta 590 167 razy, więc nie widzę jak można byłoby to zadanie policzyć na palcach.

A ile program dokona sprawdzeń jeśli \(\displaystyle{ m = 25}\) oraz \(\displaystyle{ X = \{5, 6, \ldots, 2m\}}\) ?

Pytam, bo 1, 2 oraz 3 nie mogą należeć do wybieranego zbioru, a liczbę zbiorów z czwórką można policzyć ''na palcach''.

Nadal za dużo, nawet jeśli doda się zapamiętywanie wyników (i nie liczenie niczego dwa razy): Pewne objawienie przyszło, kiedy rozbiłem sobie te 1632 sposoby według najmniejszej liczby, jaką wybraliśmy. Wyszło coś takiego:

Ja to widzę tak: dowolną liczbę naturalną \(\displaystyle{ a \ge 1}\) można jednoznacznie zapisać w postaci \(\displaystyle{ a = r \cdot 2^n}\), gdzie \(\displaystyle{ r \ge 1}\) jest nieparzyste i \(\displaystyle{ n \ge 0}\). Rozważmy dowolny 25-elementowy podzbiór \(\displaystyle{ A = \{ a_1, \ldots, a_{25} \} \subseteq \{ 1, 2, \ldots, 50 \}}\) i zapiszmy każdy element w opisanej postaci: \(\displaystyle{ a_i = r_i \cdot 2^{n_i}}\). Nietrudno sprawdzić, że

\(\displaystyle{ a_i \mid a_j \iff r_i \mid r_j \wedge n_i \le n_j}\),

jeśli więc \(\displaystyle{ r_i = r_j}\) dla pewnych \(\displaystyle{ i \neq j}\), to \(\displaystyle{ a_i \mid a_j}\) lub \(\displaystyle{ a_j \mid a_i}\), czyli zbiór nie spełnia warunków zadania. Załóżmy więc od tej pory, że \(\displaystyle{ r_i}\) są parami różne, tj. każdy element ze zbioru \(\displaystyle{ R := \{ 1, 3, 5, \ldots, 49 \}}\) występuje jako pewne \(\displaystyle{ r_i}\) dokładnie raz.

Zbiór \(\displaystyle{ R}\) z relacją podzielności tworzy zbiór częściowo uporządkowany \(\displaystyle{ (R, \mid)}\). Oznaczmy odpowiadający mu ostry porządek przez \(\displaystyle{ \prec}\), tj.

\(\displaystyle{ r \prec s \iff r \mid s \wedge r \neq s}\).

Rozważmy funkcję \(\displaystyle{ f_A : R \to \mathbb{N}}\) daną wzorem \(\displaystyle{ f(r_i) = n_i}\). Korzystając z opisanej wcześniej charakteryzacji podzielności nietrudno sprawdzić, że zbiór \(\displaystyle{ A}\) spełnia warunki zadania dokładnie wtedy, gdy \(\displaystyle{ f_A}\) jest ściśle malejąca, tj.

\(\displaystyle{ r_i \prec r_j \implies f_A(r_i) > f_A(r_j)}\).

Również nietrudno sprawdzić, że przypisanie \(\displaystyle{ A \mapsto f_A}\) jest bijekcją między rodziną wszystkich zbiorów spełniających warunki zadania i rodziną funkcji ściśle malejących \(\displaystyle{ f : (R, \mid) \to (\mathbb{N}, \le)}\) takich że \(\displaystyle{ r \cdot 2^{f(r)} \le 50}\) dla \(\displaystyle{ r \in R}\). Wystarczy więc zliczyć wszystkie takie funkcje.

Poniższy rysunek przedstawia diagram Hassego porządku \(\displaystyle{ (R, \mid)}\).
Wszystkie elementy w górnej części powinny być połączone z jedynką, ale krawędzie te pominąłem dla zwiększenia przejrzystości. Ponadto obok każdego wierzchołka \(\displaystyle{ r}\) napisany jest zbiór \(\displaystyle{ V_r \subseteq \mathbb{N}}\) wszystkich wartości, jakie może dlań przyjąć funkcja \(\displaystyle{ f}\), wynikających z warunku \(\displaystyle{ r \cdot 2^{f(r)} \le 50}\) i faktu, że funkcja ma być malejąca. Podsumowując: szukamy liczby wszystkich funkcji malejących \(\displaystyle{ f : R \to \mathbb{N}}\), takich że \(\displaystyle{ (\forall r \in R) \, f(r) \in V_r}\).

Żeby wyjaśnić dalszą procedurę, rozważmy ogólniejszy problem: dany jest skończony porządek częściowy \(\displaystyle{ (X, \le)}\) i rodzina zbiorów \(\displaystyle{ V_x \subseteq \NN}\) indeksowana elementami \(\displaystyle{ x \in X}\). Oznaczmy przez \(\displaystyle{ D_X}\) zbiór wszystkich funkcji malejących \(\displaystyle{ f : X \to \NN}\), takich że \(\displaystyle{ (\forall x \in X) \, f(x) \in V_x}\). Intuicyjnie oczywiste są dwa poniższe lematy:

W praktyce lematów używa się tak: mamy \(\displaystyle{ 1 \prec 47}\) i każda dopuszczalna wartość ze zbioru \(\displaystyle{ V_1 = \{ 3, 4, 5 \}}\) jest większa od każdej dopuszczalnej wartości ze zbioru \(\displaystyle{ V_{47} = \{ 0 \}}\), zatem krawędź łączącą te liczby można usunąć nie zmieniając szukanej liczby \(\displaystyle{ |D_R|}\). Powstały porządek jest zaś rozłączną sumą \(\displaystyle{ \{ 47 \}}\) i \(\displaystyle{ R \setminus \{ 47 \}}\) (bo usunęliśmy jedyną krawędź łączącą \(\displaystyle{ 47}\) z czymkolwiek), a zatem \(\displaystyle{ |D_R| = |D_{ \{ 47 \}}| \cdot |D_{R \setminus \{ 47 \}}| = |D_{R \setminus \{ 47 \}}|}\).

Analogicznie możemy usunąć np. \(\displaystyle{ 23}\), dostając że \(\displaystyle{ |D_R| = 2 \cdot |D_{R \setminus \{ 23 \}}|}\) (bo \(\displaystyle{ |V_{23}| = 2}\)).

Usunąć w ten sposób można kolejno wszystkie elementy \(\displaystyle{ r \in R}\), takie że \(\displaystyle{ V_r = \{ 0 \}}\), i dalej \(\displaystyle{ 17, 19, 23, 25}\), dostając że \(\displaystyle{ |D_R| = 16 \cdot |D_{R_1}|}\), gdzie porządek \(\displaystyle{ R_1}\) dany jest przez poniższy diagram Hassego:
Następnie usuwamy wierzchołki \(\displaystyle{ 11, 13, 15}\) oraz krawędzie \(\displaystyle{ (1, 7), (3, 21)}\), co daje \(\displaystyle{ |D_{R_1}| = 2|D_{R_2}|}\) gdzie \(\displaystyle{ R_2}\) jest jak niżej:
Teraz już wystarczy ręcznie zliczyć dobre funkcje dla każdego z tych porządków, otrzymując ostatecznie \(\displaystyle{ |D_{R_2}| = 17 \cdot 3 = 51}\) czyli \(\displaystyle{ |D_R| = 2^5 \cdot 51 = 1632}\).