Il mezzo shift

Polinomi, disuguaglianze, numeri complessi, ...
fph
Site Admin
Messaggi: 3663
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Il mezzo shift

Messaggio da fph » 17 giu 2005, 20:55

Mi e' tornato in mente pensando alla funzionale postata da Matthew, girava qualche anno fa qui a Pisa...

La funzione "shift" è una funzione che prende una sequenza di numeri naturali
$ (a)=(a_1,a_2,\ldots,a_n,\ldots) $ e ritorna la stessa successione privata del primo elemento:
$ S(a)=(a_2,a_3,\ldots,a_{n-1},\ldots) $

Esiste una funzione dalle sequenze di naturali in se' che sia un "mezzo shift", cioè $ f $ t.c.
$ f(f(a))=S(a) $
?

bye,
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
HumanTorch
Messaggi: 281
Iscritto il: 01 gen 1970, 01:00
Località: Tricase

Messaggio da HumanTorch » 17 giu 2005, 23:09

Vorrei chiedere qualcosa se non dispiace, dato che in funzioni (come nel resto del resto) sono una schiappa: se ad esempio la successione è una successione aritmetica, è possibile definire una sorta di "funzione casello"?:

cioè se il primo termine è maggiore dell'unità, lo elevo alla $ -1 $; se è minore lo cancello; o (nel caso la funzione sia definita $ \mathbb{N}\rightarrow\mathbb{N} $) se abbiamo una prograssione aritmetica di ragione $ b $, maggioriamo di $ k\neq 0 $ il primo termine se esso rispetta la progressione mentre lo scartiamo se non la rispetta..insomma definire una sorta di funzione che prenda un bivio o un trivio (come il simbolo di Legendre, anche se non so se l'esempio calzi perfettamente) alternante.

Se non erro si potrebbe usare un concetto del genere anche per la funzionale proposta da EuLEr tempo fa (o magari possono centrare altre funzioni particolari, come totienti o strutture del genere, dopo aver ricondotto ogni variabile a valori dati? Aspetto delucidazioni, grazie in anticipo :D

EDIT: Grazie a EvaristeG e a fph per i chiarimenti
Ultima modifica di HumanTorch il 18 giu 2005, 13:43, modificato 3 volte in totale.

EvaristeG
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 17 giu 2005, 23:23

Puoi definire una funzione come più ti pare...

Una funzione è una regola per associare ad ogni elemento del dominio uno e un solo elemento del codominio.
In termini insiemistici, una funzione $ f:X\to Y $ è un sottoinsieme $ F\subseteq X\times Y $ tale che, comunque preso x in X e y_1, y_2 in Y, se $ (x,y_1)\in F,\ (x,y_2)\in F $ allora $ y_1=y_2 $.
Ad esempio, la funzione di Dirichlet $ f:\mathbb{R}\to\mathbb{R} $ è il seguente mostro :
$ f(x)=\left\{\begin{array}{ll}1& \textrm{ se } x\in\mathbb{Q}\\0&\textrm{ se } x\notin\mathbb{Q}\end{array}\right. $
Questa cosa vale 1 se il numero x è razionale e 0 se è irrazionale.
Basta che ad ogni elemento del dominio sia associato uno ed un solo elemento del codominio.

fph
Site Admin
Messaggi: 3663
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 18 giu 2005, 08:29

Qui trovi due parole in piu' su "che cos'e' una funzione", ma in pratica EvaristeG ti ha gia' risposto esaurientemente...
ciao,
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

fph
Site Admin
Messaggi: 3663
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 22 giu 2005, 15:46

up!

non vi interessa o e' troppo difficile? Se siamo nel caso (2) vi posso dare un hint, oppure potete postare qualche tentativo e vi rispondo "acqua" o "fuochino..." :-)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 23 giu 2005, 14:18

Io ci sto provando da un po' e più ci penso più mi convinco che non esiste il 'mezzo shift'. Ma non ho idea di come dimostrarlo :oops:

fph
Site Admin
Messaggi: 3663
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 23 giu 2005, 14:50

Sisifo ha scritto:Io ci sto provando da un po' e più ci penso più mi convinco che non esiste il 'mezzo shift'.
acqua, molta acqua allora... :-D

hint: prova a considerare l'insieme 0,1,2,...,99, al posto dei naturali...

EDIT: specificato meglio "insieme finito", con molti "insiemi finiti" il problema e' decisamente piu' incasinato del caso $ \mathbb N $ :-D
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 23 giu 2005, 20:40

Ok. Allora dato che non sono capace di contare fino a 99, mi fermo prima. Diciamo che mi fermo a 0. Allora l'unica sequenza a valori in {0} è la sequenza costante (0, 0, 0, ...) [sai che allegria!!]

L'unica funzione possibile è la funzione identità che manda l'unica sequenza in sé, quindi se prendo f = id., f^2 = Shift, quindi l'identità è il mezzo shift cercato.

Evvai, il primo caso è mio!!! :mrgreen:

Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

LB
Messaggi: 72
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da LB » 23 giu 2005, 23:08

Sia S l'insieme degli elementi della sequenza e sia H tale che $ |H \times H| = |S| $ e g una funzione bigettiva $ g: S \to H \times H $.

H esiste sse S è infinito (H = S) o S ha cardinalità quadrata e g esiste per la definizione di cardinalità.

Allora la funzione di mezzo shift si puo costruire splittando in due ogni elemento della sequenza usando g, shiftando la sequenza risultante e infine mergiando gli elementi due a due usando g^-1.

Il caso di S insieme finito con cardinalità non quadrata rimane aperto.

MindFlyer

Messaggio da MindFlyer » 24 giu 2005, 01:23

Qui è nostro dovere citare l'immenso Roberto Zunino, meritevole di aver inventato questo problema. E la sua generalizzazione all'n-esimo di shift...
Mi spiace di non aver visto prima questo thread!

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 24 giu 2005, 09:11

@LB: Sì, funziona. "Splittando", "mergiando", "shiftando". Bleah! Ma un modo umano di parlare, no, eh?

La mia sol invece è un po' più complicata, e fa uso dell'Assioma di Scelta, però si generalizza a qualunque insieme di base S.

Ok. Rilancio: dimostrare che il mezzo shift esiste per qualunque S finito. Pane e nutella offerti dal sottoscritto se qualcuno ci riesce senza la Scelta.

Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

LB
Messaggi: 72
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da LB » 24 giu 2005, 11:59

Mi sembra di avere dimostrato l'impossibilità nel caso 2...

La dimostrazione è la seguente.

Consideriamo tutte le soluzioni di S(S(x)) = x. Si vede facilmente che sono le sequenze periodiche con periodo di lunghezza 1 o 2.

Dunque ce ne sono 4, che chiamamo a = 010101..., b = 101010..., z = 000000..., u = 111111...

Chiaramente S(a) = b, S(b) = a, S(z) = z e S(u) = u.

Quindi ovviamente f(a) != a e f(b) != b.

Inoltre f(a) != b poichè altrimenti deve essere f(b) = b e analogamente f(b) != a.

Quindi esiste c diverso da a e b tale che f(a) = c e f(c) = b.

Analogamente esiste d diverso da a e b tale che f(b) = d e f(d) = a.

Inoltre c != d perchè altrimenti a = f(d) = f(c) = b.

Ma allora S(c) = f(f(c)) = d ed S(d) = f(f(d)) = c.

Quindi S(S(c)) = c ed S(S(d)) = d e inoltre S(c) != c e S(d) != d.

Ma a, b sono le uniche soluzioni di S(S(x)) = x tali che S(x) != x ed essendo c != a, c != b, d != a, d != b si ottiene un assurdo.

Questo sembra generalizzabile alla dimostrazione che la cardinalità deve essere della forma 4k o 4k + 1.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 24 giu 2005, 14:06

Mannaggia alla fretta!! E sia. Mi sono allargato troppo.

Ecco i miei risultati [modulo altre stupidaggini]:

Claim: Se S è finito, il mezzo shift esiste sse #S=0,1 (mod.4). Se S è infinito il mezzo shift esiste. Se invece consideriamo solo le sequenze non periodiche, allora il mezzo shift esiste sempre, salvi i casi banali.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

fph
Site Admin
Messaggi: 3663
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 24 giu 2005, 14:54

Bene, sono i risultati a cui erano arrivati anche Zunino e Mamino (già silver medal IMO '99) qui in Normalao. :-D

Bene bene...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 24 giu 2005, 15:09

E allora, nel caso finito generico, la Scelta ci vuole, oppure basta ZF?

Rispondi