[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
exupery
Użytkownik
Użytkownik
Posty: 518
Rejestracja: 21 lut 2007, o 17:51
Płeć: Mężczyzna
Lokalizacja: Kluczewsko
Podziękował: 20 razy
Pomógł: 67 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: exupery » 31 lip 2011, o 00:01

1.Rozważmy kratę \(\displaystyle{ \mathbb{Z}^2}\) na płaszczyźnie. Początkową kongurację kamyków tworzymy układając kamyki w punktach płaszczyzny o współrzędnych całkowitych na osi OX i pod nią. Mając daną kongurację początkową możemy przesuwać kamyki w następujący sposób: jeżeli dwa kamyki sąsiadują ze sobą poziomo lub pionowo, możemy jednym z nich przeskoczyć drugi, o ile w miejscu lądowania nie ma innego kamyka. Po takim ruchu kamyk przeskakiwany usuwamy z kraty, a skaczący kamyk przesuwa się o dwa kroki poziomo lub pionowo. Początkową konfigurację wybieramy w taki sposób, aby wykonując dozwolone ruchy dowolna ilość razy dotrzec jak najdalej w górę kraty. Pokazać, że nie istnieje skończona początkowa konfiguracja kamyków umożliwiająca dotarcie do poziomu 5.

2.Czy istnieje podzbiór zbioru liczb rzeczywistych, który jest domknięty, nieprzeliczalny i rozłączny ze zbiorem liczb wymiernych?

3.Niech n będzie liczbą naturalną. Definiujemy \(\displaystyle{ a_k=\frac{1}{ {n \choose k} }}\) oraz \(\displaystyle{ b_k=2^{k-n}}\) dla \(\displaystyle{ k=1,2,...,n}\). Pokazać, że \(\displaystyle{ \sum_{i=1}^{n} \frac{a_i-b_i}{i}=0}\)

4.Mamy sobie skoczka który skacze po prostej linii, wykonuje on n ruchów przy czym każdy jest innej długości i nie większej niż n. Tzn. wykonuje ruchy długości \(\displaystyle{ 1;2;3;....n-1;n}\) przy czym w dowolnej kolejności. Czy jest możliwe, aby ustawiając na drodze n-1 min skoczek nie mógł przejść?

No to może dorzucę jeszcze dwa zadanka z tegoż konkursu:
5. Oblicz resztę z dzielenia przez 20 liczby \(\displaystyle{ \left\lfloor (5+\sqrt{29})^{1120} \right\rfloor}\)
6. Czy dla dowolnej liczby naturalnej k istnieje wielomian \(\displaystyle{ Q_k}\) k- zmiennych, taki że \(\displaystyle{ Q_k: \mathbb N^k \to \mathbb{N}}\) jest bijekcją
Ostatnio zmieniony 31 lip 2011, o 18:23 przez exupery, łącznie zmieniany 5 razy.

KPR
Użytkownik
Użytkownik
Posty: 254
Rejestracja: 11 lip 2009, o 20:00
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 31 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: KPR » 31 lip 2011, o 00:22

2:    

exupery
Użytkownik
Użytkownik
Posty: 518
Rejestracja: 21 lut 2007, o 17:51
Płeć: Mężczyzna
Lokalizacja: Kluczewsko
Podziękował: 20 razy
Pomógł: 67 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: exupery » 31 lip 2011, o 00:44

KPR, z faktu że nie zawiera żadnego przedziału nie wynika, że jest przeliczalny. Sztandarowy kontrprzykład Zbiór Cantora

Adifek
Użytkownik
Użytkownik
Posty: 1566
Rejestracja: 15 gru 2008, o 16:38
Płeć: Mężczyzna
Lokalizacja: Ostrzeszów/Wrocław
Podziękował: 8 razy
Pomógł: 398 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: Adifek » 31 lip 2011, o 00:53

I zbiór Cantora stanowi podstawę do skonstruowania takiego zbioru:
253383.htm

exupery
Użytkownik
Użytkownik
Posty: 518
Rejestracja: 21 lut 2007, o 17:51
Płeć: Mężczyzna
Lokalizacja: Kluczewsko
Podziękował: 20 razy
Pomógł: 67 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: exupery » 31 lip 2011, o 01:16

no to może przedstawię mniej inwazyjną metodę na zad 2.
Ukryta treść:    

Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: Swistak » 31 lip 2011, o 13:24

Hahaha słynna "piąta kolumna" !
Rozwiązanie oczywiście nie jest mojego autorstwa.
Piąta kolumna:    

KPR
Użytkownik
Użytkownik
Posty: 254
Rejestracja: 11 lip 2009, o 20:00
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 31 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: KPR » 31 lip 2011, o 13:53

Tu był blef

Awatar użytkownika
jerzozwierz
Użytkownik
Użytkownik
Posty: 526
Rejestracja: 22 lut 2009, o 10:13
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 8 razy
Pomógł: 42 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: jerzozwierz » 31 lip 2011, o 14:09

4.
Ukryta treść:    

marcin_smu
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 21 lut 2011, o 20:49
Płeć: Mężczyzna
Lokalizacja: Skierniewice
Pomógł: 10 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: marcin_smu » 31 lip 2011, o 15:00

Trochę się spóźniłem z tym rozwiązaniem, ale jak już zrobiłem to napisze
4:    

KPR
Użytkownik
Użytkownik
Posty: 254
Rejestracja: 11 lip 2009, o 20:00
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 31 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: KPR » 31 lip 2011, o 15:39

3:    

Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 611 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: Vax » 31 lip 2011, o 18:04

5:    

Awatar użytkownika
adamm
Użytkownik
Użytkownik
Posty: 253
Rejestracja: 1 paź 2009, o 22:04
Płeć: Mężczyzna
Lokalizacja: Sopot/Warszawa
Podziękował: 5 razy
Pomógł: 15 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: adamm » 31 lip 2011, o 18:14

Trochę inaczej
5:    

exupery
Użytkownik
Użytkownik
Posty: 518
Rejestracja: 21 lut 2007, o 17:51
Płeć: Mężczyzna
Lokalizacja: Kluczewsko
Podziękował: 20 razy
Pomógł: 67 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: exupery » 31 lip 2011, o 18:22

No to może pochwale się swoim sposobem na zadanie 5:
Ukryta treść:    

Awatar użytkownika
adamm
Użytkownik
Użytkownik
Posty: 253
Rejestracja: 1 paź 2009, o 22:04
Płeć: Mężczyzna
Lokalizacja: Sopot/Warszawa
Podziękował: 5 razy
Pomógł: 15 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: adamm » 31 lip 2011, o 18:27

exupery pisze:No to może pochwale się swoim sposobem na zadanie 5:
Ukryta treść:    
Mmmmmmm, bardzo fajne rozwiązanie, gratki.

Marcinek665
Korepetytor
Korepetytor
Posty: 1824
Rejestracja: 11 sty 2007, o 20:12
Płeć: Mężczyzna
Lokalizacja: Katowice, Warszawa
Podziękował: 73 razy
Pomógł: 228 razy

[MIX][Kombinatoryka] problemy kombinatoryczne-liga agh

Post autor: Marcinek665 » 31 lip 2011, o 18:30

Ukryta treść:    
Trochę za późno, ale szkoda mi było to kasować

ODPOWIEDZ