ciągi binarne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
olcia446
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 2 cze 2011, o 22:26
Płeć: Kobieta
Lokalizacja: Lublin
Podziękował: 9 razy

ciągi binarne

Post autor: olcia446 »

Proszę o pomoc w zadaniu:

Maszyna generuje ciągi binarne długości d w sposób, którego nie znamy. Ile co najmniej ciągów trzeba wygenerować, aby mieć pewność, że wśród nich będą przynajmniej cztery takie same?
aalmond
Użytkownik
Użytkownik
Posty: 2911
Rejestracja: 1 maja 2006, o 21:13
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 623 razy

ciągi binarne

Post autor: aalmond »

Jeżeli maszyna generuje ciągi losowo, to pewności nie będziemy mieli nigdy.
abc666

ciągi binarne

Post autor: abc666 »

aalmond, mylisz się.

olcia446, musimy mieć wszystkie możliwe ciągi 3 razy + 1 dodatkowy. Ciągów binarnych długości \(\displaystyle{ d}\) jest \(\displaystyle{ 2^{d}}\) więc od to
\(\displaystyle{ 3\cdot 2^{d}+1}\)
olcia446
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 2 cze 2011, o 22:26
Płeć: Kobieta
Lokalizacja: Lublin
Podziękował: 9 razy

ciągi binarne

Post autor: olcia446 »

Dziękuję za pomoc
aalmond
Użytkownik
Użytkownik
Posty: 2911
Rejestracja: 1 maja 2006, o 21:13
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 623 razy

ciągi binarne

Post autor: aalmond »

abc666 pisze:aalmond, mylisz się.

olcia446, musimy mieć wszystkie możliwe ciągi 3 razy + 1 dodatkowy. Ciągów binarnych długości \(\displaystyle{ d}\) jest \(\displaystyle{ 2^{d}}\) więc od to
\(\displaystyle{ 3\cdot 2^{d}+1}\)
Czy istnieje możliwość, że maszyna wygeneruje wszystkie ciągi takie same?
Ostatnio zmieniony 4 cze 2011, o 19:39 przez aalmond, łącznie zmieniany 1 raz.
Awatar użytkownika
Errichto
Użytkownik
Użytkownik
Posty: 1629
Rejestracja: 17 mar 2011, o 18:55
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 28 razy
Pomógł: 272 razy

ciągi binarne

Post autor: Errichto »

Tak. Warunek spełniony - będą przynajmniej 4 takie same.
aalmond
Użytkownik
Użytkownik
Posty: 2911
Rejestracja: 1 maja 2006, o 21:13
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 623 razy

ciągi binarne

Post autor: aalmond »

Oczywiście. Macie rację. Moje ostatnie pytanie było bezsensowne. Nie wiem, czym się zasugerowałem. Dzięki za poprawę
ODPOWIEDZ