Inne, zadanie nr 1921

Autor	Zadanie / Rozwiązanie
pm12 postów: 493	2012-07-15 12:00:22 Ze zbioru liczb {1,2,...,1000} wybrano 501 liczb. Wykaż, ze wśród wybranych liczb istnieją dwie, z których jedna dzieli drugą.

lokipl postów: 3	2012-07-19 09:54:03 Staramy się wybrać liczby z tego zbioru tak, aby żadna z nich nie była dzielnikiem innej. Nie możemy wybierać liczb 1-500 ,ponieważ każda z nich jest dzielnikiem jakiejś liczby w zbiorze. Więc nie można wybrać 500 liczb. Wobec tego możemy wybrać 1000-500=500 innych liczb.Ale musimy 501 ! Trzeba wybrać jedną która dzieli inną. Wśród wybranych liczb muszą istnieć dwie ,z których jedna dzieli drugą.

aididas postów: 279	2012-07-19 17:10:05 źle... Nie w tym kierunku rozwiązać zadanie trzeba. Dla ukazania błędu dajmy przykład liczb ze zbioru 1-500, np 3 oraz 6. Liczba 3 jest dzielnikiem 6. Skupić się należy na zbiorze pięciuset liczb zawartych 501-1000 włącznie. Żadne z tych liczb nie dzieli się nawzajem całkowicie. Szuka się pięciuset jeden liczb, co oznacza, że dobrać będzie trzeba liczbę od 1 do 500, która na pewno posiada przynajmniej jedną wielokrotność wśród liczb 501-1000. Zatem w zbiorze liczb 1,2,...,1000 istnieją dwie, z których jedna dzieli drugą.

tumor postów: 8070	2014-12-06 13:37:28 W zadaniu mowa jest o tym, że ze zbioru wybieramy 501 liczb. Nie jest napisane z góry, że wybieramy liczby 501-1000 i jedną inną. Rozwiązanie ma działać dla dowolnie wybranych 501 liczb, a powyższe nic o tym przypadku nie mówi. :) Liczbę naturalną n można zapisać jako $x2^y$, gdzie x,y są naturalne, a x nieparzysta. Niech A będzie dowolnym 501-elementowym podzbiorem zbioru $\{1,2,...,1000\}$, na zbiorze A określmy funkcję $f(x2^y)=x$ czyli każdej liczbie naturalnej n ze zbioru A przypiszmy największą liczbę nieparzystą, przez którą n się dzieli. Oczywiście różnych wartości funkcji f jest najwyżej $500$ (bo to liczby $1,3,5,...,999$), czyli pewne dwie liczby w A mają postać $n_1=x2^y$ $n_2=x2^z$ ta z mniejszym wykładnikiem dzieli drugą.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj