Dla skończonego zbioru X liczb całkowitych, niech \(\displaystyle{ |X|}\) oznacza moc zbioru, \(\displaystyle{ X−X}\) oznacza \(\displaystyle{ \{x-x' \ | \ x,x'\in X\} }\).
Pokaż że jeśli \(\displaystyle{ A,B\subseteq\{1,2,\dots,n\} \ , \ n>1}\), gdzie \(\displaystyle{ |A||B|\geq 2n-1}\), to \(\displaystyle{ (A-A)\cap(B-B)}\) zwiera dodatni element.
iloczyn zbiorów
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: iloczyn zbiorów
Może spróbuję tu troszkę pozmieniać, namieszać...
Łatwo zauważyć, że nie musimy się wysilać i liczyć wszystkie wartości \(\displaystyle{ A-A}\), możemy ograniczyć się do wartości dodatnich...
niech moce zbiorów: A i B będą odpowiednio równe: \(\displaystyle{ r, s}\), oba zbiory zawierają się w zbiorze:
\(\displaystyle{ \left\{ 1,2,3,...,n\right\} }\)
Idąc za ciosem interesują nas tylko odległości w zbiorze A lub B...
Niech:
\(\displaystyle{ A=\left\{ n_{1},n_{2},...,n_{r} \right\} , B=\left\{ n_{1},n_{2},...,n_{s} \right\} }\)
Tak naprawdę interesują nas:
\(\displaystyle{ n_{j}-n_{i}}\) ze zbioru A, oraz:\(\displaystyle{ n_{j}-n_{i}}\) ze zbioru B, gdzie: \(\displaystyle{ j>i}\)
Dla lepszego oglądu sytuacji możemy "przesunąć" zbiory A i B w dół, tak aby pierwsze liczby w każdym z nich były jedynkami,
nie zmieni to różnic a o nie tu chodzi...
Po takim przesunięciu zauważmy, ze częścią wspólną.: \(\displaystyle{ A \cap B=\left\{ 1\right\} }\)
Jeżeli jakikolwiek element należałby jeszcze do części wspólnej to teza zadania natychmiast byłaby spełniona.
Więc musimy założyć, że oba zbiory nie mają więcej wspólnych punktów niż jedynkę...
Zauważmy jeszcze jedną ciekawą zależność, najmniej różnych odległości mają np. zbiory tego typu:
\(\displaystyle{ A=\left\{ 1,2,3,4,5\right\} \vee A=\left\{ 1,5,9,13\right\} }\)
Takich odległości jest dokładnie:
\(\displaystyle{ r-1 \vee s-1}\)
w powyższym przypadku: \(\displaystyle{ 1,2,3,4 \vee 4,8,12}\) czyli cztery lub trzy
Najwięcej odległości różnych jest: \(\displaystyle{ {r \choose 2} }\),
np:
\(\displaystyle{ A=\left\{ 1,2,4,8\right\} }\)
mamy:
\(\displaystyle{ 1,2,3,4,6,7}\) czyli \(\displaystyle{ {4 \choose 2}=6}\) różnych odległości...
Mamy udowodnić, że jeżeli spełniony jest warunek:
\(\displaystyle{ r \cdot s \ge 2n-1}\) to w zbiorze A i B są diw równe odległości...
W związku z tym próbowałem przedstawić zbiory A i B w pierwszej ćwiartce układu współrzędnych...
Zbiór A na osi OX a zbiór B na osi OY,
Teraz myślowo spróbujmy sobie odkładać (powielać) zbiór A na dowolnych osiach:
\(\displaystyle{ y=a>0, a}\) - całkowite
Mamy:
\(\displaystyle{ A_{a}=\left\{ a,n_{2}a,...,n_{r}a\right\} ,a=1,...}\)
Na razie zbiór A sobie odkładaliśmy "byle jak" a teraz musimy tak odkładać, żeby jak najwięcej odłożyć zapełniając jak "najlepiej" kwadrat:
\(\displaystyle{ (n-1) \times (n-1)}\)
I teraz do czego zmierzam odkładając w ten sposób zbiór A musimy jak najwięcej odkładać aby punkty zbioru:
\(\displaystyle{ A_{a}}\) nie utworzyły żadnego kwadratu na tym polega cała zabawa bo wtedy odległości jakieś tam na osi OX i OY się powtórzą i spełni się teza zadania, my musimy zbadać sytuację "najgorszą" to znaczy aby zbiór \(\displaystyle{ A_{a}}\) był jak największy...
Pokażę przykład:
\(\displaystyle{ n=8, A=\left\{ 1,2,3\right\} }\)
Odległości mamy tu:
\(\displaystyle{ 1,2 }\) - dwie różne
Niech:
\(\displaystyle{ A_{1}=\left\{ ((1,1),(2,1),(3,1)\right\} }\)
Nie możemy tworzyć więc \(\displaystyle{ A_{2} ani A_{3}}\) bo natychmiast powstałby kwadrat i teza byłaby spełniona...
Ale możemy tworzyć sobie \(\displaystyle{ A_{4}}\) i potem już np \(\displaystyle{ A_{7}}\) lub \(\displaystyle{ A_{8}}\)
Każdy następny automatyczni da nam tezę...
Więc nakreśliłem mniej więcej o co mi biega, chcę stworzyć jak najwięcej prostokątów w kwadracie:
\(\displaystyle{ \left\{ 1,...,n\right\} \times \left\{ 1,...,n\right\} }\) takich z których żaden nie będzie kwadratem...
Więc muszę wziąć "najgorszy" przypadek czyli taki gdzie w zbiorze A jest najmniej różnych odległości, czyli:
\(\displaystyle{ r-1}\)
Widać teraz, że aby warunek zadania był spełniony musimy dobrać takie x aby:
\(\displaystyle{ x \cdot (r-1) \ge n}\)
Przyjmując: \(\displaystyle{ x=s-1}\)
mamy więc:
\(\displaystyle{ (s-1)(r-1) \ge n}\)
Jeżeli będzie zachodził ten warunek to teza zadania będzie spełniona.
jednak musi być tu: \(\displaystyle{ s, r>2}\)
Zauważmy, że dla \(\displaystyle{ r=2}\), musi być \(\displaystyle{ s=n}\) i wtedy faktycznie teza jest spełniona,
U mnie jednak musi być mocniejsze założenie...
Zestawmy jednak to z warunkiem zadania, czyli:
\(\displaystyle{ s \cdot r \ge 2n-1}\)
dla lepszego samopoczucia wprowadźmy:
\(\displaystyle{ r=x, y=s }\)
Zapiszmy oba te warunki "funkcyjnie":
\(\displaystyle{ (x-1)(y-1) \ge n}\) - mój warunek
\(\displaystyle{ xy \ge 2n-1}\) - zadaniowy warunek
lub:
\(\displaystyle{ y \ge 1+ \frac{n}{x-1} }\) - mój
\(\displaystyle{ y \ge \frac{2n-1}{x} }\)
Na piechotę łatwo sprawdzić oba warunki dla:
\(\displaystyle{ n=3,4,5,6,7}\)
np: \(\displaystyle{ n=4 }\)
\(\displaystyle{ 2 \cdot 4-1=7}\)
\(\displaystyle{ r, s=3}\)
\(\displaystyle{ 3 \cdot 3 \ge 9, 2 \cdot 2=4}\)
\(\displaystyle{ n=6, r=3,r=4}\)
\(\displaystyle{ 3 \cdot 4 \ge 11, 2 \cdot 3=6}\)
\(\displaystyle{ n=7, r=3,s=5 \vee r=4, s=4}\)
Nie spełniony jest tylko mój warunek w konfiguracji:
\(\displaystyle{ n=5, s=3,r=3}\)
Teraz rozumowanie nasze przeniesie się na:
\(\displaystyle{ n \ge 8}\)
Sprawdzimy kiedy:
\(\displaystyle{ 1+ \frac{n}{x-1} \le \frac{2n-1}{x} }\)
lub:
\(\displaystyle{ x^2-nx+2n-1 \le 0}\)
\(\displaystyle{ x \in \left\langle \frac{n- \sqrt{(n-2)^2-4} }{2}; \frac{n+ \sqrt{(n-2)^2-4} }{2}\right\rangle }\)
Dla: \(\displaystyle{ n \ge 8}\) sytuacja się stabilizuje ponieważ:
\(\displaystyle{ x_{1} \le 2, x_{2} \ge n-2}\)
Co łatwo sprawdzić
Więc ten "mój" warunek jest dla: \(\displaystyle{ n \ge \wedge r, s >2}\) nawet "mocniejszy niż warunek z zadania,
Lecz to i tak nic nie zmienia ponieważ największa różnica (między warunkami) dla:
\(\displaystyle{ x= \frac{n}{2} }\) i tak nie zawiera całkowitych liczb.
Więc reasumując mój warunek jest równoznaczny z warunkiem zadaniowym dla:
\(\displaystyle{ n \ge 8, \wedge r,s>2}\)
Ale warunek z zadania jest spełniony dla:
\(\displaystyle{ r=2}\), wtedy \(\displaystyle{ s=n}\) - co widać gołym okiem
Na piechotę sprawdziliśmy dla.: \(\displaystyle{ n=2,3,4,5,6,7}\) też warunek zadaniowy praktycznie pokrywa się z moim więc jest spełniony...
Mój nie jest spełniony dla:
\(\displaystyle{ n=5, r=s=3}\)
Ale łatwo sprawdzić sprawdzić na piechotę nawet, że zawsze jakieś odległości w takich zbiorach: A i B trójelementowych
muszą się pokryć, a więc warunek z zadania jest dobry...
cnd...
Łatwo zauważyć, że nie musimy się wysilać i liczyć wszystkie wartości \(\displaystyle{ A-A}\), możemy ograniczyć się do wartości dodatnich...
niech moce zbiorów: A i B będą odpowiednio równe: \(\displaystyle{ r, s}\), oba zbiory zawierają się w zbiorze:
\(\displaystyle{ \left\{ 1,2,3,...,n\right\} }\)
Idąc za ciosem interesują nas tylko odległości w zbiorze A lub B...
Niech:
\(\displaystyle{ A=\left\{ n_{1},n_{2},...,n_{r} \right\} , B=\left\{ n_{1},n_{2},...,n_{s} \right\} }\)
Tak naprawdę interesują nas:
\(\displaystyle{ n_{j}-n_{i}}\) ze zbioru A, oraz:\(\displaystyle{ n_{j}-n_{i}}\) ze zbioru B, gdzie: \(\displaystyle{ j>i}\)
Dla lepszego oglądu sytuacji możemy "przesunąć" zbiory A i B w dół, tak aby pierwsze liczby w każdym z nich były jedynkami,
nie zmieni to różnic a o nie tu chodzi...
Po takim przesunięciu zauważmy, ze częścią wspólną.: \(\displaystyle{ A \cap B=\left\{ 1\right\} }\)
Jeżeli jakikolwiek element należałby jeszcze do części wspólnej to teza zadania natychmiast byłaby spełniona.
Więc musimy założyć, że oba zbiory nie mają więcej wspólnych punktów niż jedynkę...
Zauważmy jeszcze jedną ciekawą zależność, najmniej różnych odległości mają np. zbiory tego typu:
\(\displaystyle{ A=\left\{ 1,2,3,4,5\right\} \vee A=\left\{ 1,5,9,13\right\} }\)
Takich odległości jest dokładnie:
\(\displaystyle{ r-1 \vee s-1}\)
w powyższym przypadku: \(\displaystyle{ 1,2,3,4 \vee 4,8,12}\) czyli cztery lub trzy
Najwięcej odległości różnych jest: \(\displaystyle{ {r \choose 2} }\),
np:
\(\displaystyle{ A=\left\{ 1,2,4,8\right\} }\)
mamy:
\(\displaystyle{ 1,2,3,4,6,7}\) czyli \(\displaystyle{ {4 \choose 2}=6}\) różnych odległości...
Mamy udowodnić, że jeżeli spełniony jest warunek:
\(\displaystyle{ r \cdot s \ge 2n-1}\) to w zbiorze A i B są diw równe odległości...
W związku z tym próbowałem przedstawić zbiory A i B w pierwszej ćwiartce układu współrzędnych...
Zbiór A na osi OX a zbiór B na osi OY,
Teraz myślowo spróbujmy sobie odkładać (powielać) zbiór A na dowolnych osiach:
\(\displaystyle{ y=a>0, a}\) - całkowite
Mamy:
\(\displaystyle{ A_{a}=\left\{ a,n_{2}a,...,n_{r}a\right\} ,a=1,...}\)
Na razie zbiór A sobie odkładaliśmy "byle jak" a teraz musimy tak odkładać, żeby jak najwięcej odłożyć zapełniając jak "najlepiej" kwadrat:
\(\displaystyle{ (n-1) \times (n-1)}\)
I teraz do czego zmierzam odkładając w ten sposób zbiór A musimy jak najwięcej odkładać aby punkty zbioru:
\(\displaystyle{ A_{a}}\) nie utworzyły żadnego kwadratu na tym polega cała zabawa bo wtedy odległości jakieś tam na osi OX i OY się powtórzą i spełni się teza zadania, my musimy zbadać sytuację "najgorszą" to znaczy aby zbiór \(\displaystyle{ A_{a}}\) był jak największy...
Pokażę przykład:
\(\displaystyle{ n=8, A=\left\{ 1,2,3\right\} }\)
Odległości mamy tu:
\(\displaystyle{ 1,2 }\) - dwie różne
Niech:
\(\displaystyle{ A_{1}=\left\{ ((1,1),(2,1),(3,1)\right\} }\)
Nie możemy tworzyć więc \(\displaystyle{ A_{2} ani A_{3}}\) bo natychmiast powstałby kwadrat i teza byłaby spełniona...
Ale możemy tworzyć sobie \(\displaystyle{ A_{4}}\) i potem już np \(\displaystyle{ A_{7}}\) lub \(\displaystyle{ A_{8}}\)
Każdy następny automatyczni da nam tezę...
Więc nakreśliłem mniej więcej o co mi biega, chcę stworzyć jak najwięcej prostokątów w kwadracie:
\(\displaystyle{ \left\{ 1,...,n\right\} \times \left\{ 1,...,n\right\} }\) takich z których żaden nie będzie kwadratem...
Więc muszę wziąć "najgorszy" przypadek czyli taki gdzie w zbiorze A jest najmniej różnych odległości, czyli:
\(\displaystyle{ r-1}\)
Widać teraz, że aby warunek zadania był spełniony musimy dobrać takie x aby:
\(\displaystyle{ x \cdot (r-1) \ge n}\)
Przyjmując: \(\displaystyle{ x=s-1}\)
mamy więc:
\(\displaystyle{ (s-1)(r-1) \ge n}\)
Jeżeli będzie zachodził ten warunek to teza zadania będzie spełniona.
jednak musi być tu: \(\displaystyle{ s, r>2}\)
Zauważmy, że dla \(\displaystyle{ r=2}\), musi być \(\displaystyle{ s=n}\) i wtedy faktycznie teza jest spełniona,
U mnie jednak musi być mocniejsze założenie...
Zestawmy jednak to z warunkiem zadania, czyli:
\(\displaystyle{ s \cdot r \ge 2n-1}\)
dla lepszego samopoczucia wprowadźmy:
\(\displaystyle{ r=x, y=s }\)
Zapiszmy oba te warunki "funkcyjnie":
\(\displaystyle{ (x-1)(y-1) \ge n}\) - mój warunek
\(\displaystyle{ xy \ge 2n-1}\) - zadaniowy warunek
lub:
\(\displaystyle{ y \ge 1+ \frac{n}{x-1} }\) - mój
\(\displaystyle{ y \ge \frac{2n-1}{x} }\)
Na piechotę łatwo sprawdzić oba warunki dla:
\(\displaystyle{ n=3,4,5,6,7}\)
np: \(\displaystyle{ n=4 }\)
\(\displaystyle{ 2 \cdot 4-1=7}\)
\(\displaystyle{ r, s=3}\)
\(\displaystyle{ 3 \cdot 3 \ge 9, 2 \cdot 2=4}\)
\(\displaystyle{ n=6, r=3,r=4}\)
\(\displaystyle{ 3 \cdot 4 \ge 11, 2 \cdot 3=6}\)
\(\displaystyle{ n=7, r=3,s=5 \vee r=4, s=4}\)
Nie spełniony jest tylko mój warunek w konfiguracji:
\(\displaystyle{ n=5, s=3,r=3}\)
Teraz rozumowanie nasze przeniesie się na:
\(\displaystyle{ n \ge 8}\)
Sprawdzimy kiedy:
\(\displaystyle{ 1+ \frac{n}{x-1} \le \frac{2n-1}{x} }\)
lub:
\(\displaystyle{ x^2-nx+2n-1 \le 0}\)
\(\displaystyle{ x \in \left\langle \frac{n- \sqrt{(n-2)^2-4} }{2}; \frac{n+ \sqrt{(n-2)^2-4} }{2}\right\rangle }\)
Dla: \(\displaystyle{ n \ge 8}\) sytuacja się stabilizuje ponieważ:
\(\displaystyle{ x_{1} \le 2, x_{2} \ge n-2}\)
Co łatwo sprawdzić
Więc ten "mój" warunek jest dla: \(\displaystyle{ n \ge \wedge r, s >2}\) nawet "mocniejszy niż warunek z zadania,
Lecz to i tak nic nie zmienia ponieważ największa różnica (między warunkami) dla:
\(\displaystyle{ x= \frac{n}{2} }\) i tak nie zawiera całkowitych liczb.
Więc reasumując mój warunek jest równoznaczny z warunkiem zadaniowym dla:
\(\displaystyle{ n \ge 8, \wedge r,s>2}\)
Ale warunek z zadania jest spełniony dla:
\(\displaystyle{ r=2}\), wtedy \(\displaystyle{ s=n}\) - co widać gołym okiem
Na piechotę sprawdziliśmy dla.: \(\displaystyle{ n=2,3,4,5,6,7}\) też warunek zadaniowy praktycznie pokrywa się z moim więc jest spełniony...
Mój nie jest spełniony dla:
\(\displaystyle{ n=5, r=s=3}\)
Ale łatwo sprawdzić sprawdzić na piechotę nawet, że zawsze jakieś odległości w takich zbiorach: A i B trójelementowych
muszą się pokryć, a więc warunek z zadania jest dobry...
cnd...
-
- Użytkownik
- Posty: 22207
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3754 razy
Re: iloczyn zbiorów
Ten zapis oznacza, że `A` jest podzbiorem `B` lub odwrotnie (w zależności od relacji między `r` i `s`). A to zbyt grube założenie.arek1357 pisze: ↑23 paź 2021, o 15:26 Może spróbuję tu troszkę pozmieniać, namieszać...
Łatwo zauważyć, że nie musimy się wysilać i liczyć wszystkie wartości \(\displaystyle{ A-A}\), możemy ograniczyć się do wartości dodatnich...
niech moce zbiorów: A i B będą odpowiednio równe: \(\displaystyle{ r, s}\), oba zbiory zawierają się w zbiorze:
\(\displaystyle{ \left\{ 1,2,3,...,n\right\} }\)
Idąc za ciosem interesują nas tylko odległości w zbiorze A lub B...
Niech:
\(\displaystyle{ A=\left\{ n_{1},n_{2},...,n_{r} \right\} , B=\left\{ n_{1},n_{2},...,n_{s} \right\} }\)
...
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: iloczyn zbiorów
Wiem wiem zapis niefortunny powinno być:
\(\displaystyle{ A=\left\{ n_{1},...,n_{r}\right\} }\)
\(\displaystyle{ B=\left\{ m_{1},...,m_{s}\right\} }\)
Dodano po 2 minutach 20 sekundach:
Zbiory te mogą mieć co najwyżej jeden punkt wspólny...
\(\displaystyle{ A=\left\{ n_{1},...,n_{r}\right\} }\)
\(\displaystyle{ B=\left\{ m_{1},...,m_{s}\right\} }\)
Dodano po 2 minutach 20 sekundach:
Zbiory te mogą mieć co najwyżej jeden punkt wspólny...