szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 5 mar 2015, o 15:15 
Użytkownik

Posty: 752
Lokalizacja: Warszawa
Moi drodzy , mam takie dwa zadania lecz proszę tylko i wyłącznie o wskazówki. Nie chcę gotowych rozwiązań a wskazówki mogę być po dwie. Proszę dać mi samemu dojść do końcówki danego problemu, brzmią one tak :

1. Wybieramy dowolnie 10 różnych liczb naturalnych spośród liczb od 0 do 100. Wykaż, że w zbiorze tych dziesięciu wybranych liczb można wybrać dwa rozłączne podzbiory, dające tę samą sumę.

2. Uzasadnij że wśród liczb 1,11,111... jest nieskończenie wiele liczb podzielnych przez daną liczbę k. Tutaj zauważyłem że każda z tych liczb jest postaci \frac{ 10^{n}-1 }{9}. Lecz nadal wiele mi to nie mówi.
Powtarzam jeszcze raz i bardzo proszę tylko i wyłącznie o jakieś drobne porady, wskazówki. :)
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2015, o 15:19 
Moderator
Avatar użytkownika

Posty: 2226
Lokalizacja: Warszawa
Drugie zrób nie wprost.
A i zauważ, że wystarczy udowodnić istnienie choć jednej takiej.
A i brakuje założenia niezbędnego (dlaczego?), że k jest nieparzyste.

No a w pierwszym policz ile takich par rozłącznych podzbiorów jest.
Albo nie, tego lepiej nie rób :p
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2015, o 15:34 
Użytkownik

Posty: 752
Lokalizacja: Warszawa
W pierwszym już zacząłem liczyć , i coś z tym liczeniem nie idzie. Chyba nie w tym kieunku trzeba iść :P
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2015, o 15:36 
Moderator
Avatar użytkownika

Posty: 2226
Lokalizacja: Warszawa
Nie no, tamta wskazówka z liczeniem podzbiorów była błędna (choć samo policzenie nie jest trudne, dałbyś radę!)
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2015, o 17:59 
Użytkownik

Posty: 752
Lokalizacja: Warszawa
A w zad. 2 dowodząc nie wprost masz na myśli to że istnieje skończenie wiele takich liczb postaci 1,11,111,... które są podzielne przez k czy to że zakładać że takich liczb w ogóle nie ma? Wydaje mi się że chodzi Ci o to drugie co napisałem ale lepiej spytać.
Góra
Mężczyzna Online
PostNapisane: 5 mar 2015, o 18:34 
Użytkownik
Avatar użytkownika

Posty: 10616
Lokalizacja: Wrocław
Tak formalnie, to zaprzeczeniem istnienia nieskończenie wielu liczb o danej własności jest istnienie co najwyżej skończonej liczby takowych, więc pierwsza możliwość.
A dokładne zaprzeczenie tezy wyglądałoby tak: istnieje k \in \NN, że jedynie dla skończenie wielu n \in \NN jest k |  \frac{10^{n}-1}{9}

Ale można pokazać, że jeśli dla danego k istnieje jedna liczba tej postaci, która jest podzielna przez k, to mamy zapewnione istnienie nieskończenie wielu liczb z rozważanego ciągu o tej cesze. Niech a_{n}= \frac{10^{n}-1}{9}. Można wykazać, że a_{n} | a_{bn} dla dowolnego b naturalnego dodatniego (choć przy tym wygodniej operować chyba na postaci z jedyneczkami, ale to może kwestia gustu).
Po pokazaniu tego możesz zacząć dowód nie wprost z silniejszym założeniem nie wprost, tj. o nieistnieniu liczby tej postaci, będącej podzielną przez pewne ustalone k naturalne. no i jakiś pałczing na resztach z dzielenia przez k powinien się udać, ale może istnieje coś dużo piękniejszego...
Pozdrawiam.
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2015, o 19:50 
Moderator
Avatar użytkownika

Posty: 2226
Lokalizacja: Warszawa
^To wszystko jest prawda, ale zwyczajniej się to tłumaczy tak, że jak mamy dwie liczby które dzielą się przez n, to sklejenie ich zapisów dziesiętnych też dzieli się przez n.

Więc załóżmy, że takie liczby nie istnieją i wypisz kilka liczb postaci 1, 11, 111 i zacznij coś tam mówić o resztach.

I w ogóle zadanie wybrakowane, bo nie dość, że k nie może być nieparzyste, to jeszcze nie może być podzielne przez 5. We wszystkich innych przypadkach już działa.
Góra
Mężczyzna Offline
PostNapisane: 11 mar 2015, o 08:43 
Gość Specjalny

Posty: 3010
Lokalizacja: Gołąb
Wskazówki do 1.
Ile jest możliwych podzbiorów zbioru 10-elementowego?
Ile jest możliwych sum co najwyżej dziesięciu liczb ze zbioru \left\{0,1,\dots, 100 \right\}?

Zadanie 2 również jest znane i jak wspomniał Ponewor rozwiązanie istnieje wtedy i tylko wtedy gdy k jest względnie pierwsze z 2 i 5.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zasada włączeń i wyłączeń Proste . Czy dobry wynik ?  dragonito  1
 Zasada Szufladkowa, podzielność  Milczek  1
 Zasada szufladkowa - zadanie 20  Ruahyin  1
 Zasada zachowania momentu pędu.  dawid.barracuda  0
 Pierwsza zasada indukcji - inna postać.  pi0tras  12
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl