Cavolo,questo problema è assolutamente magnifico! La soluzione che alla fine mi è uscita fuori(sperando di non aver cannato da qualche parte)è estremamente semplice,ma il lavoro e l'euristica dietro è stata una vera sgroppata. Inizio a scrivere la soluzione,poi dopo,se non escono buchi, faccio qualche commento sul resto.
1)Dico $ (a_1,..,a_k) $ assume il valore di $ a_i $ se $ f(a_1,..,a_k)=f(a_i,...,a_i) $.E' facile trovare dalle ipotesi che un $ a_i $ così ci deve essere.
2)Ora diciamo che $ (a_1,..,a_k) $ è del tipo j,se essa assume il valore di $ a_i $ e $ a_i $ compare j volte nella stringa.
3)Dimostro che il tipo,$ j_m $ di lunghezza minima è 1. Supponiamo $ j_m>1 $. Consideriamo $ (b_1,...,b_k) $ la stringa relativa,che assume il valore $ b_g $. Eseguiamo la seguente sostituzione:dove non compare $ b_g $ mettiamo $ b_g $;nella zona dove compare $ b_g $ mettiamo a caso un totale di almeno 2 valori distinti tutti diversi da $ b_g $:questo è possibile farlo perchè |S|>2 e per l'ipotesi di assurdo. Per costruzione questa k-upla non ha mai un valore in comune con la nostra, ma allo stesso tempo dove compariva $ b_g $ compaiono cose che hanno meno ripetizioni di $ j_m $ per poter essere il valore assunto da f. Ossia assurdo.
4) Quindi prendiamo una k-upla minimale,con,dunque, $ b_g $ che compare solo in posizione g,e che assume il valore $ b_g $. Dalle ipotesi segue che le k-uple che hanno $ b_g $ in tutte le entrate tranne g e in g una cosa diversa da $ b_g $ debbono assumere il valore della posizione g. Da qua,si trova facilmente che questo è vero per tutte le k-uple con questa struttura:tutte cose uguali fuori da g e un valore diverso in g(essenzialmente questo passaggio è il problema con k=2).
5)Consideriamo una k-upla $ (n_1,..n_k) $ in cui un valore,h, non compare. Allora costruiamo la seguente:fuori da g mettiamo h, al posto di g mettiamo qualunque cosa diversa da $ n_g $. Da quanto stabilito in 4) e dalle ipotesi deduciamo che n non può che assumere il valore $ n_g $
6)Sia n generica. Costruiamo la seguente: prendiamo un q diverso da $ n_g $,e un r diverso da q. Se un entrata di n contiene q allora noi mettiamo r altrimenti mettiamo q. Per quanto stabilito in 5), e poichè |S|>2 quindi la nostra k-upla rientra in 5),dunque assume il valore in g che per costruzione è q, ma allora poichè scatta l'ipotesi la nostra n-upla non può assumere altro valore che quello della posizione g.
abbiamo trovato che una funzione generica assume il valore della sua componente g-esima. In altri termini la possiamo scrivere come una proiezione composta per una permutazione di S,che sono sempre effettivamente soluzione. Quindi abbiamo $ k(|S|!) $ funzioni belle.
Puff pant
Ciao
p.s:se fosse stato postato oggi,avrei aspettato ancora qualche giorno,ma poichè sono già passati un pò di giorni ho deciso di postare,se preferite che aspetto di più,o che aspetto infinitamente di più(per questioni di età
),ossia non posto,fatemelo sapere,che la prossima volta al massimo amndo un mp all'autore per sapere se gli torna.
p.ps:messa così come l'ho messa la soluzione è assolutamente ridicola:nel senso che ho iniziato con i concetti che mi sono venuti in mente solo alla fine dell'euristica e dei tentativi;quindi ad un lettore estraneo può sembrare del tutto innaturale, e infatti lo è. Dopo aver avuto l'ok dellOP,magari posto un pò come può uscire in modo naturale la soluzione.
