Staffetta combinatoria.

[paga92aren]

Era una prima impressione che ho avuto...ho limitato i valori possibili di N(n).
Forse era un po' banale...

Testo nascosto:

Inoltre ho trovato che $N(n)<\frac{2n}{3}+1$ perché sommando tutte le terne possibili e sapendo che $\sum{a_i}\leq\sum{(i-1)}=\frac{i(i-1)}{2}$
$3*\sum{a_i}=in$
da cui la relazione di sopra

[ndp15]

Era una prima impressione che ho avuto...

Ah ok, credevo pensassi concluso il problema!
Comunque solitamente sul forum non si postano soluzioni parziali o idee, a meno che il problema non sia stato postato da molto e nessuno è riuscito a rispondere. D'altro canto non credo ci sia nulla che lo vieti espressamente, quindi al massimo parlane con un moderatore (il tutto per evitare che qualcuno si trovi già in bella mostra metà soluzione, o che in staffetta ci sia metà soluzione di un utente e metà di un altro non sapendo poi chi deve andare avanti con il problema successivo ).

[Anér]

@paga92aren: puoi spiegare meglio come sei arrivato a dire che N(n)< (2n)/3 +1 ?

@dario2994: è un problema di tua invenzione? Hai a disposizione una soluzione?

Io sono solo riuscito a trasformare il problema: Dato un triangolo equilatero con un reticolo di punti a caselle sempre triangolari (faccio un disegno qui sotto, anche se non viene un triangolo equilatero), trovare quanti punti del reticolo si possono selezionare al massimo senza prenderne due allineati in orizzontale o in una diagonale inclinata a 60 o 120 gradi.

.
. .
. . .
. . . .
. . . . .
. . . . . .

In più ogni punto ha 2n nemici, ovvero scegliere una terna impedisce di sceglierne altre 2n.

[dario2994]

Non me lo sono inventato io ma almeno questo l'ho risolto

[paga92aren]

@paga92aren: puoi spiegare meglio come sei arrivato a dire che N(n)< (2n)/3 +1 ?

Double caunting: somma tutte le terne
1) la somma di tre numeri della stessa terna è n (la somma di tutti i numeri è N(n)*n)
2) la somma di tutti gli $a_i$ è minore della somma dei numeri da 0 a N(n)-1 quindi la somma di tutti i numeri è 3/2(N(n)-1)N(n)
da cui la formula che credo sia quella giusta (ho verificato un po' di casi ma non riesco a trovare un modo per cui sia sempre possibile costruire le terne)

[dario2994]

Double caunting: somma tutte le terne

Dabol caunting

[Anér]

2) la somma di tutti gli $a_i$ è minore della somma dei numeri da 0 a N(n)-1

Questo passaggio mi è oscuro, anche se credo che sto perdendo qualcosa di banale. Puoi spiegarlo meglio?

[paga92aren]

Tutti gli $a_i$ sono diversi tra loro e compresi tra 0 e $n$.
Scelgo $a_1$ il più piccolo possibile (quindi uguale a zero), poi $a_2$ uguale a 1 e così via fino a $a_N(n)=N(n)-1$

Attenzione non è detto che scelti così gli $a_i$ sia possibile completare le terzine, ma in qualunque modo li scelgo la loro somma sarà maggiore di quella da 0 a $N(n)-1$.

[Anér]

la loro somma sarà maggiore di quella da 0 a $N(n)-1$.

Maggiore in senso francese! (maggiore o uguale).
Piazzo l'esempio così cambiamo problema. O paga92aren, il prossimo scelgilo tu visto che hai messo l'idea più importante.

Distinguiamo i casi in cui $ n=3k+1,3k,3k-1 $. Nel primo caso devo trovare $ \lfloor \frac{6k+2}{3} +1\rfloor=2k+1 $ terne buone, ma mi basta prendere le stesse che avrei preso nel caso di $ 3k $ e aggiungere 1 a tutti i $ c_i $.
Infatti nel secondo caso devo prendere sempre $ 2k+1 $ terne, e prendo tutte quelle del tipo $ (2i;\quad k-i;\quad 2k-i) $ con $ 0\leq i\leq k $ e quelle del tipo $ (2i+1;\quad 2k-i;\quad k-i-1) $ con $ 0\leq i\leq k-1 $.
Infine nel terzo caso ho bisogno di $ \lfloor \frac{6k-2}{3}+1\rfloor =2k $ terne, e prendo quelle del tipo $ (2i;\quad k-i-1;\quad 2k-i) $ con $ 0\leq i\leq k-1 $ e quelle del tipo $ (2i+1;\quad 2k-i-1;\quad k-i-1) $ con $ 0\leq i \leq k-1 $. È facile vedere che sono tutte disgiunte componente per componente.

[dario2994]

Ovviamente giusto
Decidete voi chi posta il prossimo: magari il primo che ne ha uno carino lo piazza

[paga92aren]

Problema 14
Quante sono le funzioni $f$: $A \rightarrow A$ con $A=\mathbb{Q} \{ \sqrt{2},\pi, e, i\}$ tali che:
$$f(x+f(y))=f(x)+y \;\;\;\; \forall x,y\in A$$
La funzionale dovrebbe essere nota, per questo lo considero di combinatoria.
Spero che vada bene come problema e buona fortuna a tutti.

[Anér]

Diamo per buono che i 5 numeri $ \pi, e, i, \sqrt{2}, 1 $ sono linearmente indipendenti su $ \mathbb{Q} $. Allora se scrivo un numero $ x\in A $ come $ x=r_1\pi+r_2e+r_3i+r_4\sqrt{2}+r_5 $ e scelgo un razionale $ k\neq 0 $, posso definire la seguente funzione: $ f(r_1\pi+r_2e+r_3i+r_4\sqrt{2}+r_5)=r_1\pi+r_2e+r_3i+kr_5\sqrt{2}+\frac{1}{k}r_4 $, che è una funzione additiva (e perciò il primo membro dell'equazione diventa f(x+f(y))=f(x)+f(f(y)) ), e involutiva (o involutoria? Comunque intendo dire che f(f(y))=y per ogni y appartenente ad A). Ovviamente k lo posso scegliere in infiniti modi, dunque esistono infinite funzioni siffatte.

[Anér]

Problema 15
Abbiamo una sequenza di $ n $ naturali non necessariamente distinti $ (a_1,a_2,\cdots,a_n) $, tale che esiste almeno un grafo su $ n $ vertici di nome $ v_1,v_2,\cdots,v_n $ e tali che $ \forall 1\leq i\leq n\qquad deg(v_i)=a_i $.
Dimostrare che allora un possibile grafo siffatto si può ottenere con il seguente algoritmo:
1) Scelgo un vertice $ v_i $ a piacere;
2) Considero il valore di $ a_i $ e fra tutti i vertici escluso $ v_i $ prendo gli $ a_i $ di grado maggiore (si intende che scelgo a piacere uno dei più grandi, poi fra i rimanenti uno dei più grandi, e così via fino ad averne presi $ a_i $), e li metto in un insieme $ V $;
3) Collego $ v_i $ con i vertici contenuti in $ V $; riduco di 1 i gradi corrispondenti ai vertici dell'insieme $ V $ e metto da parte $ v_i $;
4) Ora che mi sono ridotto al caso con un vertice in meno riparto dal punto 1, e vado avanti fino a ridurre a 0 tutti gli $ a_i $
In sostanza bisogna dimostrare che al punto 2 non si è mai costretti a scegliere vertici di grado 0.
Buon lavoro!

[Anér]

È passato un po' di tempo e nessuno ha risposto, per cui metto qualche spiegazione in più e un suggerimento nascosto. L'ipotesi è che abbiamo un grafo su n vertici e facciamo su un foglio la lista dei gradi dei vertici, chiamandoli a_1, a_2, a_3.
Ora cancelliamo gli archi del grafo e proviamo a costruirne un altro con gli stessi gradi su ogni vertice, e facciamo così: scegliamo un vertice v_i a piacere, che dovremo collegare con a_i vertici (infatti ha bisogno di a_i collegamenti). Infischiandocene degli a_i collegamenti che aveva nel grafo originale, osserviamo gli altri vertici e scegliamo gli a_i che hanno bisogno di più collegamenti (chiaramente in caso di parità scegliamo a piacere). Poiché questi vertici hanno bisogno di più collegamenti, smorziamo la loro fame di collegamenti collegandoli a v_i, e quindi tracciamo questi archi. Ora v_i è a posto, e i vertici a lui collegati hanno ognuno bisogno di un collegamento in meno; ci siamo insomma ricondotti a un caso con n-1 vertici e con alcuni a_j rimasti uguali, altri diminuiti di 1, uno di essi (a_i) scomparso. Andiamo avanti per questa strada e la tesi è che finisce tutto bene, ossia ogni volta riusciamo a collegare v_i con i suoi a_i vertici (ove a_i è chiaramente ciò che rimane dell'a_i iniziale dopo gli eventuali tagli).
Questo algoritmo serve a verificare l'esistenza di un grafo con gradi assegnati.

Testo nascosto:

Provate a ottenere il grafo finale trasformando gradualmente quello iniziale, anziché cercare disuguaglianze sugli a_i (almeno io l'ho fatto così)

[Anér]

Dato che è passata un'altra buona settimana metto la soluzione e propongo il prossimo problema.

L'idea è di modificare gradualmente il grafo originale G in modo da ottenerne uno che si otterrebbe anche con l'algoritmo. L'algoritmo genera un grafo in cui rinumerando opportunamente i vertici come $ w_1, w_2, \cdots , w_n $ si ha che $ w_1 $ è collegato ai migliori degli altri vertici, $ w_2 $ con i migliori del sottografo in cui escludiamo $ w_1 $, $ w_3 $ deve essere collegato con i migliori dei vertici del sottografo in cui abbiamo tolto $ w_1,w_2 $ (e tutti gli archi associati), e così via, $ w_i $ deve essere collegato con i migliori dei vertici del sottografo che si ottiene togliendo $ w_1,\cdots ,w_{i-1} $ e gli archi associati. Se ci viene dato un grafo che rispetta queste proprietà (e ovviamente con i gradi giusti), questo è il grafo generato dall'algoritmo, dunque l'algoritmo funziona. Visto poi che non cambia nulla se riordiniamo gli indici dei vertici e dei gradi, possiamo supporre che $ v_i=w_i \forall i $, e tornare alle care vecchie v.
Per una banale induzione ci basta dimostrare che basta modificare il grafo G in modo che $ v_1 $ sia collegato con i migliori degli altri; in questo modo infatti si ottiene un nuovo grafo G' in cui tutti i vertici hanno mantenuto il grado e in più $ v_1 $ è collegato ai migliori degli altri, quindi possiamo togliere $ v_1 $ e gli archi associati (ossia considerare il sottografo senza $ v_1 $) e ridurci al caso con un vertice in meno: di nuovo esiste un grafo che rispetta le nuove ipotesi sui grafi (che è ciò che rimane di G') e perciò per induzione si possono cambiare un po' di archi in modo da ottenere il grafo che si otterrebbe seguendo l'algoritmo.
Ora che abbiamo ridotto la tesi a soddisfare la qualità dei collegamenti del solo $ v_1 $, supponiamo che in G il vertice $ v_1 $ sia collegato con $ k<a_1 $ vertici giusti e $ a_1-k $ vertici sbagliati (dunque $ v_1 $ ha dei collegamenti sbagliati); si noti che nello scegliere i vertici di grado maggiore (quelli buoni che dovrebbero essere collegati a $ v_1 $) tra i $ v_i $ escluso $ v_1 $ in caso di pareggio scegliamo a piacere, dunque tutto ciò che sappiamo è che un vertice buono ha grado maggiore o uguale a un vertice cattivo.
Prendamo ora un vertice cattivo collegato erroneamente a $ v_1 $ (sia esso $ v_x $) e un vertice buono erroneamente non collegato a $ v_1 $ (sia esso $ v_y $). Sappiamo che $ a_x\leq a_y $, ma $ v_x $ è già collegato a $ v_1 $, dunque $ a_x-1<a_y $. Se $ v_x $ e $ v_y $ non sono collegati questo significa che esiste un vertice $ v_z $ collegato a $ v_y $ ma non a $ v_x $, con $ z\neq x,y,1 $; ma anche se sono collegati si ottiene lo stesso risultato da $ a_x-2<a_y-1 $. Basta ora sostituire i collegamenti $ v_1v_x $ e $ v_yv_z $ con i collegamenti $ v_1v_y $ e $ v_xv_z $, e ora $ v_1 $ ha un collegamento buono in più, e per induzione si riesce a sistemare tutti i collegamenti di $ v_1 $.
[Respiro di sollievo]
Propongo il nuovo problema da un'altra parte, secondo le recenti direttive della staffetta.
viewtopic.php?f=16&t=15483