iloczyn zbiorów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
ann_u
Użytkownik
Użytkownik
Posty: 138
Rejestracja: 14 wrz 2018, o 18:56
Płeć: Kobieta
Lokalizacja: Brak
Podziękował: 31 razy
Pomógł: 4 razy

iloczyn zbiorów

Post autor: ann_u »

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.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: iloczyn zbiorów

Post autor: arek1357 »

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...
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: iloczyn zbiorów

Post autor: a4karo »

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\} }\)

...
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.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: iloczyn zbiorów

Post autor: arek1357 »

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...
ODPOWIEDZ