Nierówność dla f
- mol_ksiazkowy
- Użytkownik
- Posty: 11417
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Nierówność dla f
Jakie funkcje \(\displaystyle{ f: \{1,...,n \} \to \{1,...,n \}}\) spelniają nierówność \(\displaystyle{ f(j) < | f^{-1}(j)| }\) (przeciwobraz) dla \(\displaystyle{ j=1,...,n}\)
Ostatnio zmieniony 25 paź 2023, o 12:36 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- mol_ksiazkowy
- Użytkownik
- Posty: 11417
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Nierówność dla f
Żadne, gdyż gdyby istniała taka funkcja, i nazywa się \(\displaystyle{ f,}\) to z definicji takich funkcji, dla dowolnego \(\displaystyle{ a \in \left\{ 1,2,\ldots, n\right\},}\) mamy \(\displaystyle{ f\left( a\right) \in \left\{ 1,2,\ldots,n\right\} }\); a zatem, ponieważ moc zbioru jest tutaj liczbą naturalną, więc: \(\displaystyle{ \left| \stackrel{ \rightarrow }{f ^{-1} } \left( a\right)\right| > f(a) \ge 1}\), a zatem \(\displaystyle{ \left| \stackrel { \rightarrow }{f ^{-1} } \left( a\right) \right| \ge 2}\), i to zachodzi dla każdego elementu \(\displaystyle{ a \in \left\{ 1,2,\ldots,n\right\}.}\) Ponieważ przeciwobrazy zbiorów jednoelementowych są rozłączne, i ich suma daje tutaj zbiór \(\displaystyle{ \left\{ 1,2,\ldots, n \right\}}\), więc otrzymujemy sprzeczność, gdyż suma takich \(\displaystyle{ n,}\) co najmniej dwuelementowych zbiorów, ma co najmniej \(\displaystyle{ (2n)>n}\) elementów-sprzeczność. Wobec czego taka funkcja nie istnieje.\(\displaystyle{ \square}\)mol_ksiazkowy pisze: ↑25 paź 2023, o 11:56 Jakie funkcje \(\displaystyle{ f: \{1,...,n \} \to \{1,...,n \}}\) spelniają nierówność \(\displaystyle{ f(j) < | f^{-1}(j)| }\) (przeciwobraz) dla \(\displaystyle{ j=1,...,n}\)
-
- Użytkownik
- Posty: 48
- Rejestracja: 14 sie 2010, o 12:29
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 3 razy
Re: Nierówność dla f
Nie zdążyłem pierwszy, ale oto mój alternatywny dowód.
Przypuśćmy, że taka funkcja \(\displaystyle{ f}\) istnieje i rozważmy 2 przypadki:
1) \(\displaystyle{ f}\) jest różnowartościowa
Wtedy dla pewnego \(\displaystyle{ i \in \left\{ 1, \dots, n\right\}}\) musiałoby zachodzić: \(\displaystyle{ \left| \vec{ f^{-1} }\left( i\right) \right| \gt f\left( i\right) = n}\), czyli przeciwobraz \(\displaystyle{ \vec{ f^{-1} }\left( i\right)}\) musiałby być zbiorem o co najmniej \(\displaystyle{ n+1}\) elementach, co nie jest możliwe dla żadnej funkcji \(\displaystyle{ f}\) spełniającej warunki zadania, a w szczególności gdy \(\displaystyle{ f}\) jest różnowartościowa, bo wtedy rozpatrywany przeciwobraz jest zbiorem jednoelementowym.
2) \(\displaystyle{ f}\) nie jest różnowartościowa
Wtedy dla pewnych 2 różnych argumentów funkcja \(\displaystyle{ f}\) przyjmuje tę samą wartość, a w konsekwencji (na mocy zasady szufladkowej Dirichleta) istnieje \(\displaystyle{ j \in \left\{ 1, \dots, n\right\}}\) takie, że dla każdego \(\displaystyle{ i \in \left\{ 1, \dots, n\right\}}\) \(\displaystyle{ f\left( i\right) \neq j }\), czyli musiałoby zachodzić: \(\displaystyle{ 0 = \left| \vec{ f^{-1} }\left( j\right) \right| \gt f\left( j\right)}\), a to niemożliwe, bo \(\displaystyle{ f}\) nie przyjmuje wartości ujemnych.
Przypuśćmy, że taka funkcja \(\displaystyle{ f}\) istnieje i rozważmy 2 przypadki:
1) \(\displaystyle{ f}\) jest różnowartościowa
Wtedy dla pewnego \(\displaystyle{ i \in \left\{ 1, \dots, n\right\}}\) musiałoby zachodzić: \(\displaystyle{ \left| \vec{ f^{-1} }\left( i\right) \right| \gt f\left( i\right) = n}\), czyli przeciwobraz \(\displaystyle{ \vec{ f^{-1} }\left( i\right)}\) musiałby być zbiorem o co najmniej \(\displaystyle{ n+1}\) elementach, co nie jest możliwe dla żadnej funkcji \(\displaystyle{ f}\) spełniającej warunki zadania, a w szczególności gdy \(\displaystyle{ f}\) jest różnowartościowa, bo wtedy rozpatrywany przeciwobraz jest zbiorem jednoelementowym.
2) \(\displaystyle{ f}\) nie jest różnowartościowa
Wtedy dla pewnych 2 różnych argumentów funkcja \(\displaystyle{ f}\) przyjmuje tę samą wartość, a w konsekwencji (na mocy zasady szufladkowej Dirichleta) istnieje \(\displaystyle{ j \in \left\{ 1, \dots, n\right\}}\) takie, że dla każdego \(\displaystyle{ i \in \left\{ 1, \dots, n\right\}}\) \(\displaystyle{ f\left( i\right) \neq j }\), czyli musiałoby zachodzić: \(\displaystyle{ 0 = \left| \vec{ f^{-1} }\left( j\right) \right| \gt f\left( j\right)}\), a to niemożliwe, bo \(\displaystyle{ f}\) nie przyjmuje wartości ujemnych.