Funzione con valore diverso se le componenti sono distinte

[dario2994]

Sia $S$ un insieme finito con $|S|>2$ e $k\ge 1$ un intero. Una funzione $f:S^k\to S$ la definisco bella sse $\forall u,v\in S^k$ tali che non hanno componenti uguali vale $f(u)\neq f(v)$. (i vettori (1,2,3) (2,3,1) non hanno componenti uguali mentre i vettori (1,23,456) e (1001,23,789) sì)
Quante sono le funzioni belle?

Bonus da giorno di pioggia:
E se $|S|=2$ ?

p.s. piazzate anche solo pezzi di soluzione

[Carlein]

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.

[dario2994]

Prima di tutto nessuno ce l'avrà con te se hai risposto Inoltre la mia soluzione e la tua sono identiche (e quindi la tua è giusta sse lo è la mia ), e intendo proprio UGUALI spiccicate (il che mi stupisce non poco), tranne che per il punto 3... il mio era più intricato, molto meglio il tuo

p.s. la fonte è il TST Iran 2005 problema 6

[Carlein]

Prima di tutto nessuno ce l'avrà con te se hai risposto Inoltre la mia soluzione e la tua sono identiche (e quindi la tua è giusta sse lo è la mia ), e intendo proprio UGUALI spiccicate (il che mi stupisce non poco), tranne che per il punto 3... il mio era più intricato, molto meglio il tuo

p.s. la fonte è il TST Iran 2005 problema 6

E infatti il punto 3) ero anch'io sulla strada di imboccare una strada molto più contorta,e dopo un pò mi sono accorto di quella là.
Più in generale dunque vorrei fare qualche commento sull'euristica,che nel caso di questo problema è rimasta sotterrata,o meglio capovolta dalla forma finale della soluzione,che la rende forse poco naturale,a meno che non si abbiano pensato cose simili:
Ho iniziato con l'idea di trovare un insieme che fungesse da "base":ossia molto più piccolo e tale che ogni funzione bella fosse determinata dai valori su di lui. Dopo un pò,mi sono deciso a fare i casi bassi. Per 2=k uno trova che è tutto determinato dalle cose del tipo (a,a) ed una scelta del tipo (a,b) con a diverso da b. Quindi il problema diventava come generalizzare questo quantomeno a 3. La prima cosa ovvia da considerare è (a,a,b). Alchè se uno prova a capire su questo caso facile quand'è che una scelta di un (a,a,b) determina tutte le cose con 2 uguali e uno diverso, trova che quando (a,a,b) assume il valore di b. Quindi l'attenzione si sposta su questa cosa trovare un (a,a,..,a,b,a..,a) che assume il valore di b; aggiustando il lavoro di 3=k si vede che questo determina tutto(essenzialmente così vengono in mente 5 e 6). E qui si arriva al punto 3) della mia soluzione:per una buona oretta io ho provato a seguire questa osservazione promettente,che il tutto è ovvio per k<|S| difatti qui posso mettere cose tutte diverse(e qui c'era alla lontana il concetto del punto 3)) e si vede facilmente che sono impossibilitate dal fatto che tutti gli elementi del tipo (a,...a,b,a,...,a) assumono il valore di a. Questo approccio però non può funzionare per k>|S|, perchè per Pigheonole ci sono ripetizioni forzate e sembra necessario scendere alle cose del tipo (a,...,a,b,b,a,...) ossia 2 di un tipo e k-2 di un altro. Dunque il problema diventava come si mettevano gerarchicamente le cose del tipo (a,...,a,b,...a) condizionava quelle del tipo (a,...,b,b,a,...a) e così via. Mi è parso di non controllare più il problema pure perchè prima ce l'avevo in buona parte sotto controllo,dunque ho fatto un passo indietro, e sono tornato all'esempio delle cose senza ripetizioni. Il concetto fondamentale dunque sembrava essere il fatto di contare il numero di volte in cui compariva l'entrata di cui f assumeva il valore(che nel caso di cose tutte diverse doveva essere per forza 1),e soprattutto quanto potesse essere basso ossia il suo minimo qual'è:dunque quello che volevo dimostrare sulle cose del tipo (a,a,...,b,a,...a) era che ce n'è una che assume il valore dell'entrata che compare una sola volta. Dunque se io penso che questo è vero,in particolare debbo dedurre che questo minimo è 1,il che si è rivelato molto più facile ed è il passo 3), e soprattutto si è rilevato che questo insieme al resto delle ipotesi implicava facilmente la configurazione che cercavo(questa sembra essere una tecnica generale:si cerca una configurazioni su cui si punta tutto che esista,si deduce qualcosa da quella configurazione,e questa proposizione dedotta dalle ipotesi si rivela cosa molto più semplice di quella che cercavamo, dopodichè si prende la proposizione e le ipotesi e si trova la configurazione, http://www.tricki.org/article/Prove_a_consequence_first questo è un articolo bellino che ho letto al proposito).
CiaoCiao!