Matematyka.pl

Jakie funkcje \(\displaystyle{ f: \{1,...,n \} \to \{1,...,n \}}\) spelniają nierówność \(\displaystyle{ f(j) < | f^{-1}(j)| }\) (przeciwobraz) dla \(\displaystyle{ j=1,...,n}\)

A co to jest to po prawej stronie? Ilość elementów?

Ilość elementów przeciwobrazu elementu \(\displaystyle{ j}\)

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

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

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.