szukanie zaawansowane
 [ Posty: 13 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 15 sty 2012, o 16:09 
Użytkownik

Posty: 10
Lokalizacja: Kraków
1. W prostokącie o wymiarach 3x4 danych jest 6 punktów. Wykaż, że wśród nich istnieją takie dwa, których odległość jest nie większa niż \sqrt{5} .
2. W kwadracie o boku długości 1 danych jest 101 punktów. Wykaż, że pewne trzy spośród nich tworzą trójkąt o polu nie większym niż 0,01.
3. Pięciokąt wypukły ma wierzchołki w punktach kratowych. Wykaż, że zawiera on w swoim wnętrzy co najmniej jeden punkt kratowy.
4. Udowodnij, że w dowolnym stukącie wypukłym istnieje przekątna nierównoległa do żadnego z boku wielokąta.
5. Spośród liczb 1,2,...,200 wybrano 101 liczb. Wykaż, że wśród wybranych liczb znajdziemy dwie takie, że jedna dzieli się przez drugą.

Zaznaczam, że należy skorzystać tu z Zasady Szufladkowej Dirichleta.
Chciałbym także oznajmić, że jestem początkującym użytkownikiem tego forum i proszę o wyrozumiałość względem moich błędów.
Góra
Mężczyzna
PostNapisane: 15 sty 2012, o 16:27 
Gość Specjalny
Avatar użytkownika

Posty: 4977
Lokalizacja: Kraków
5. załóżmy, że k wśród wybranych liczb jest \leq 100 oznaczmy je a_1,...,a_k. Pozostałe 101-k jest >100, ich zbior to B.
Rozważmy liczby 2a_1,...,2a_k, wszystkie są wieksze od 100 i nie większe niż 200, z zasady szufladkowej pewna liczba należy jednocześnie do zbioru \{2a_1,...,2a_k\} i B.
Góra
Mężczyzna
PostNapisane: 15 sty 2012, o 16:38 
Użytkownik

Posty: 10
Lokalizacja: Kraków
Mhmm, dzięki.. Znaczy, że szedłem dobrym tropem ;) a coś z pozostałych może wiesz? ;>

/edit

dziwi mnie tylko założenie 101 - k>100.. czy oby na pewno to jest dobrze ?
Góra
Mężczyzna
PostNapisane: 15 sty 2012, o 16:50 
Gość Specjalny

Posty: 3053
Lokalizacja: Świdnik
A sam na żadne inne nie masz pomysłu?

W 2 pewnie pomocne będzie podzielenie tego kwadratu na 100 mniejszych :) .
Góra
Mężczyzna
PostNapisane: 15 sty 2012, o 17:04 
Użytkownik

Posty: 10
Lokalizacja: Kraków
Wiesz.. Coś mi w głowie świta, ale nie potrafię tego logicznie wytłumaczyć. Zresztą gdybym nie miał problemu to zapewne bym się nie zwracał o pomoc ;)
Góra
Mężczyzna
PostNapisane: 15 sty 2012, o 17:15 
Gość Specjalny
Avatar użytkownika

Posty: 4977
Lokalizacja: Kraków
hardboy95 napisał(a):
dziwi mnie tylko założenie 101 - k>100.. czy oby na pewno to jest dobrze ?

Takiego czegoś nie napisałem. Przeczytaj całe zdanie.
Góra
Mężczyzna
PostNapisane: 15 sty 2012, o 17:25 
Użytkownik

Posty: 10
Lokalizacja: Kraków
oj przepraszam. fail.
Góra
Kobieta
PostNapisane: 15 sty 2012, o 17:39 
Użytkownik

Posty: 84
Lokalizacja: Stalowa Wola
Zordon napisał(a):
Rozważmy liczby 2a_1,...,2a_k, wszystkie są wieksze od 100 i nie większe niż 200

Ja bym się tego czepiła, ale pewna wielokrotność każdej z nich będzie w tym przedziale
Góra
Mężczyzna
PostNapisane: 15 sty 2012, o 19:45 
Użytkownik
Avatar użytkownika

Posty: 3704
Lokalizacja: blisko
Jak w 2 gim podzielisz kwadrat na kwadraciki malutkie o wymiarach: 2mm x 1mm to tych kwadracików będzie 50 i w jednym kwadraciku muszą być 3 punkty a nawet największe pole jaki będą tworzyły to co najwyżej połowa pola kwadratu.Pierwsze podobnie robisz.
Góra
Mężczyzna
PostNapisane: 15 sty 2012, o 23:25 
Gość Specjalny
Avatar użytkownika

Posty: 4977
Lokalizacja: Kraków
adri napisał(a):
Zordon napisał(a):
Rozważmy liczby 2a_1,...,2a_k, wszystkie są wieksze od 100 i nie większe niż 200

Ja bym się tego czepiła, ale pewna wielokrotność każdej z nich będzie w tym przedziale


Słusznie, dzięki za uwagę, zatem całe rozwiązanie ma istotną lukę, bo wielokrotności mogą się nam pokryć, czego nie chcemy.
W tej chwili nie potrafię tego poprawić, ale w zamian mogę podać alternatywne rozwiązanie, mianowicie teza zadania wynika z tw. Dilwortha ;).

edit: chociaż tak po prawdzie to to nawet nie jest tw. Dilwortha, tylko jedna (trywialna) implikacja, pozostaje rozbić \{1,...,200\} na mniej niż 101 łańcuchów względem |.
Góra
Mężczyzna
PostNapisane: 16 sty 2012, o 08:06 
Użytkownik

Posty: 10
Lokalizacja: Kraków
arek1357 napisał(a):
Jak w 2 gim podzielisz kwadrat na kwadraciki malutkie o wymiarach: 2mm x 1mm to tych kwadracików będzie 50


Fajnie, ale nie widziałem jeszcze kwadratu o różnych bokach :D
Góra
Mężczyzna
PostNapisane: 16 sty 2012, o 13:42 
Użytkownik
Avatar użytkownika

Posty: 3704
Lokalizacja: blisko
Hehehe sorki prostokąty. miały być dobre hehehe!
Chyba że w jakiejś metryce będą takie prostokąty kwadracikami

-- 16 stycznia 2012, 15:45 --

A w tym stukącie wrzuć wszystkie przekątne do 100 szuflad (tyle ile boków) i zobaczysz ile jest równoległych przekątnych do siebie. Jeżeli założysz, że każda przekątna jest równoległa do jakiegoś boku powinna wyjść sprzeczność.
Góra
Mężczyzna
PostNapisane: 21 sty 2012, o 14:09 
Użytkownik

Posty: 319
Lokalizacja: Warszawa
Wczoraj natknąłem się na zadanie 5 i też zabiło mi ćwieka...
Po jakimś czasie wszelako wpadłem na taki oto pomysł:

tworzymy pary:
\left(1,2 \right);\left( 2,4\right);\left( 3,6\right);...;\left( 99,198\right);\left( 100,200\right)

tylko jeden element z każdej pary może zostać wybrany.

teraz łączymy pary w następujące "zestawy":
\left(1,2,4,8,16,32,64,128\right);\left( 3,6,12,24,48,96\right);\left( 5,10,20,40,80,160\right) itd.

tylko jeden element z każdego zestawu może zostać wybrany.
Zestawów jest 50, gdyż każdy zaczyna się od liczby nieparzystej mniejszej od 100.
Liczb które nie znajdują się w żadnym zestawie jest również 50, gdyż są to liczby nieparzyste z przedziału <100,200>.
ZSD implikuje brak jednej liczby.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 13 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 zasada wlaczania i wylaczania - zadanie 2  BSD  1
 zasada szufladkowa ?  BSD  2
 liczby podzielne - zasada wlaczania i wylaczania  BSD  3
 3 zadania...  Ciapanek  2
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl