losowanie liczb

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
klimat
Użytkownik
Użytkownik
Posty: 117
Rejestracja: 13 paź 2017, o 08:24
Płeć: Mężczyzna
Lokalizacja: Tu
Podziękował: 42 razy

losowanie liczb

Post autor: klimat »

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.
Ostatnio zmieniony 16 sty 2022, o 15:56 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: losowanie liczb

Post autor: arek1357 »

Klasy abstrakcji

Podobne...
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: losowanie liczb

Post autor: a4karo »

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?
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: losowanie liczb

Post autor: arek1357 »

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...
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: losowanie liczb

Post autor: a4karo »

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ść.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: losowanie liczb

Post autor: arek1357 »

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...
Awatar użytkownika
Flype
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 21 sty 2022, o 23:04
Płeć: Mężczyzna
wiek: 27
Podziękował: 9 razy
Pomógł: 6 razy

Re: losowanie liczb

Post autor: Flype »

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.
Ostatnio zmieniony 22 sty 2022, o 09:42 przez Flype, łącznie zmieniany 1 raz.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: losowanie liczb

Post autor: arek1357 »

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...?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: losowanie liczb

Post autor: kerajs »

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''.
Awatar użytkownika
Flype
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 21 sty 2022, o 23:04
Płeć: Mężczyzna
wiek: 27
Podziękował: 9 razy
Pomógł: 6 razy

Re: losowanie liczb

Post autor: Flype »

Nadal za dużo, nawet jeśli doda się zapamiętywanie wyników (i nie liczenie niczego dwa razy):

Kod: Zaznacz cały

#!/usr/bin/env python3
known = dict()

def f(X, m):
    if len(X) < m:
        return 0
    if m == 1:
        return len(X)
    x = min(X)
    X1 = [a for a in X if a != x]
    X2 = [a for a in X if a % x != 0]
    key = f"{X} @ {m}"
    global known
    if key not in known:
        known[key] = f(X1, m) + f(X2, m-1)
    return known[key]

n = 25
numbers = list(range(4, 2*n+1))
f(numbers, n)
print(f"{len(known)} times")
# 24503 times
Pewne objawienie przyszło, kiedy rozbiłem sobie te 1632 sposoby według najmniejszej liczby, jaką wybraliśmy. Wyszło coś takiego:

Kod: Zaznacz cały

8 96




12 384

14 384

16 256
17 256
18 128
19 64
20 32
21 16
22 8
23 4
24 2
25 1
26 1
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: losowanie liczb

Post autor: Dasio11 »

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)}\).
diagram.png
diagram.png (61.26 KiB) Przejrzano 588 razy
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:

Lemat 1:    
Lemat 2:    
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:
diagram 2.png
diagram 2.png (28.61 KiB) Przejrzano 588 razy
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:
diagram 3.png
diagram 3.png (10.38 KiB) Przejrzano 588 razy
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}\).
ODPOWIEDZ