Πέμπτη 6 Αυγούστου 2015

$f(f(f(x))) = f(f(x))$

Πόσες συναρτήσεις $f$ με πεδίο ορισμού το σύνολο $\{1, 2, 3, 4, 5\}$ και σύνολο τιμών το $\{1, 2, 3, 4, 5\}$, όχι απαραίτητα $1- 1$ ή $1- 1$ και επί, ικανοποιούν την ισότητα 
$f(f(f(x))) = f(f(x))$ 
για κάθε $x\in\{1, 2, 3, 4, 5\}$?
Από μαθηματικό διαγωνισμό του Πανεπιστημίου Στάνφορντ (Η.Π.Α)
 Διασκεδαστικά Μαθηματικά    www.eisatopon.blogspot.com     
Αναρτήθηκε από στις 6.8.15
Ετικέτες ,

1 σχόλιο:

  1. papadim9 Αυγούστου 2015 στις 12:03 μ.μ.

    Για να ικανοποιείται η f(f(f(x))) = f(f(x)) θα πρέπει να συντρέχουν οι εξής προϋποθέσεις:

    α). Να υπάρχει ένα τουλάχιστον στοιχείο α του συνόλου Ω={1,2,3,4,5} για το οποίο f(α)=α. Ονομάζουμε κάθε τέτοιο στοιχείο ταυτοτικό.

    β). Εάν στο Ω υπάρχουν μη ταυτοτικά στοιχεία, να υπάρχει ανάμεσά τους ένα τουλάχιστον στοιχείο β, του οποίου η εικόνα f(β) να ταυτίζεται με ταυτοτικό στοιχείο. Ονομάζουμε κάθε τέτοιο στοιχείο ημιταυτοτικό.

    γ). Εάν στο Ω υπάρχουν μη ταυτοτικά ή μη ημιταυτοτικά στοιχεία γ, οι εικόνες τους να ταυτίζονται με ημιταυτοτικά στοιχεία. Ονομάζουμε κάθε τέτοιο στοιχείο ελεύθερο.

    Διακρίνουμε επομένως τις εξής περιπτώσεις:

    1. Υπάρχει 1 ακριβώς ταυτοτικό στοιχείο, οπότε τα ημιταυτοτικά θα είναι από 1 τουλάχιστον έως 4 το πολύ και τα απομένοντα θα είναι ελεύθερα. Το πλήθος των συναρτήσεων αυτής της μορφής είναι C(5,1)*[C(4,1)*1^3+C(4,2)*2^2+C(4,3)*3^1+C(4,4)*4^0]= 5*(4+24+12+1) = 205.

    2. Υπάρχουν 2 ακριβώς ταυτοτικά στοιχεία, οπότε τα ημιταυτοτικά θα είναι από 1 τουλάχιστον έως 3 το πολύ και τα απομένοντα θα είναι ελεύθερα. Το πλήθος των συναρτήσεων αυτής της μορφής είναι C(5,2)*[C(3,1)*2^1*1^2+C(3,2)*2^2*2^1+C(3,3)*2^3*3^0] = 10*(6+24+8) = 380.


    3. Υπάρχουν 3 ακριβώς ταυτοτικά στοιχεία, οπότε τα ημιταυτοτικά θα είναι από 1 τουλάχιστον έως 2 το πολύ και τα απομένοντα θα είναι ελεύθερα. Το πλήθος των συναρτήσεων αυτής της μορφής είναι C(5,3)*[C(2,1)*3^1*1^1+C(2,2)*3^2*2^0] = 10*(6+9) = 150.

    4. Υπάρχουν 4 ακριβώς ταυτοτικά στοιχεία, οπότε τα ημιταυτοτικά θα είναι 1 ακριβώς και τα ελεύθερα κανένα. Το πλήθος των συναρτήσεων αυτής της μορφής είναι C(5,4)*C(1,1)*4^1*1^0 = 5*4 = 20.


    5. Υπάρχουν 5 ακριβώς ταυτοτικά στοιχεία, ημιταυτοτικά κανένα και ελεύθερα κανένα. Το πλήθος των συναρτήσεων αυτής της μορφής είναι C(5,5) = 1 (η ταυτοτική συνάρτηση f(x)=x).

    Συνολικά υπάρχουν 205+380+150+20+1 = 756 συναρτήσεις.

    ΑπάντησηΔιαγραφή

Εγγραφή σε: Σχόλια ανάρτησης (Atom)