Livre Francois G233

[franco]

Sull'esempio dei "problemi scozzesi" proposti da Gianfranco, vi propongo un problema che mi sembra intrigante (per quel poco che capisco di francese).
Se qualcuno si folesse cimentare in traduzione e risoluzione ...

Les suites universelles
Soit un entier naturel n. On dit que S(n,k), suite de k nombres entiers naturels (avec k>n), est universelle d’ordre n si on peut obtenir n’importe quelle des n ! permutations des entiers {1,2,….,n} en supprimant k – n de ses termes. Par exemple, la suite de 3 termes (1,2,1) est universelle d’ordre 2 car on peut obtenir les 2 permutations (1,2) et (2,1) en supprimant respectivement le troisième chiffre qui est égal à 1, ce qui donne (1,2,*) et le premier chiffre lui aussi égal à 1, ce qui donne (*,2,1). A l’inverse (1,2,2) ne l’est pas car il est impossible d’obtenir (2,1).
On désigne par L(n) la longueur de la suite universelle d’ordre n la plus courte possible. On a par exemple L(2) = 3.
1) Démontrez que L(3) = 7 et L(4) = 12.
2) A partir de suites universelles S(3,7) et S(4,12) d’ordres 3 et 4 et de longueur minimale, donnez et justifiez un mode de construction de suites universelles d’ordre 5, 6, 7,….n dont la longueur vous paraît minimale.

ciao

[delfo52]

per n intero naturale.
chiamiamo S (n,k) la sequenza di k numeri naturali (con k>n), e la si dice "universale" di ordine n, se si può ottenere qualsiasi delle sue n! permutazioni, sopprimendo k-n termini.
es.: (1,2,1) è sequenza di tre termini universale di ordine 2 perchè si possono ottenere (1,2) e (2,1)
mentre (1,2,2) non va bene

Chiamiamo L(n) la lunghezza della sequenza universale di ordine n più corta possibile
L(2) = 3 (vedi sopra)
dimostrare che
L(3) = 7
L(4) = 12
e trovare il sistema per andare oltre

(traduzione veloce)

[giobimbo]

Tutto quello che son riuscito a trovare finora è questo:
(1) Se $\displaystyle S_n$ è una sequenza universale di ordine n allora $\displaystyle S_{n+1} \,=\, (S, \,n+1, \,S)$ è una sequenza universale di ordine n+1. Usando tale ricorrenza abbiamo
S(1, k) = (1) = S(1, 1);
S(2, k) = (1, 2, 1) = S(2, 3);
S(3, k) = (1, 2, 1, 3, 1, 2, 1) = S(3, 7);
S(4, k) = (1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1) = S(4, 15);
...

(2) Sia $\displaystyle S = (S_1, \,S_2, \,..., \,S_n)$, dove $\displaystyle S_i$ (per i = 1, 2, ..., n) è una sequenza formata dai numeri da 1 a n disposti in un qualsiasi ordine, allora $\displaystyle S = S(n, \,n^2)$ è una sequenza universale, difatti se P è una permutazione dei numeri da 1 a n, il primo termine di P sta in $\displaystyle S_1$, il secondo termine di P sta in $\displaystyle S_2$, ecc. Stavolta
S(1, k) = S(1, 1);
S(2, k) = S(2, 4);
S(3, k) = S(3, 9);
S(4, k) = S(4, 16);
S(5, k) = S(5, 25) mentre nel caso (1) si ha k = 31 e via crescendo, 63 invece di 36, ecc.

(3) Sia S come nel caso (2) ma con $\displaystyle S_1 \,= \,S_2 \,= \,... \,= \,S_n \,= \,(1, \,2, \,..., \,n)$, se la permutazione $\displaystyle P = (p_1, \,p_2, \,..., \,p_n)$ ha due termini successivi $\displaystyle p_r$ e $\displaystyle p_{r+1}$ con $\displaystyle p_r < p_{r+1}$ allora ambedue stanno nella sequenza $\displaystyle S_r$. Proseguendo, $\displaystyle p_{r+2}$ sta in $\displaystyle S_{r+1}$, ..., $\displaystyle p_n$ sta in $\displaystyle S_{n-1}$, quindi la sequenza $\displaystyle S' \,= \,(S_1, \,S_2, \,..., \,S_{n-1})$ contiene tutte le permutazioni dei numeri da 1 a n tranne la permutazione P' = (n, n-1, n-2, ..., 1). Per eliminare quest'unico caso sfavorevole basta aggiungere un termine ad S', ottenendo la sequenza universale $\displaystyle S'' \,= \,(S_1, \,S_2, \,..., \,S_{n-1}, \,1)$. Infine
S(1, k) = (1) = S(1, 1);
S(2, k) = (1, 2, 1) = S(2, 3);
S(3, k) = (1, 2, 3, 1, 2, 3, 1) = S(3, 7);
S(4, k) = (1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1) = S(4, 13);
S(5, k) = (1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1) = S(5, 21)
...
e, in generale, dato n si ha k = n(n-1)+1. Qui mi sono bloccato, altre idee?