Espace disponible pour enchérir (corrigé)

Exercice d’échauffement:
Q1.  la distance entre les paliers 2P et 3SA est: 6: [2P,2SA],[2SA,3T],… [3P,3SA]
Q2. La distance est un entier compris entre 0 et 35.
Q3. On prend 2 couples d’enchères séparés par la même distance; par une translation, on établit une bijection de l’ensemble des séquences dans un cas sur l’ensemble des séquences dans l’autre cas. Par exemple, avec les couples (2P, 3C) et (3K, 4T), la translation de 3 paliers de longueur assure cette bijection; à une séquence comme 2P 3T 3K 3C, elle associe pour l’autre couple, la séquence 3K 3P 3SA 4T. Puisqu’il y a bijection, ces ensembles finis ont même cardinal.

Initialisation:
Q4.  Une seule séquence entre 3K et 3C, c’est: « … 3C »
Q5.  2 séquences entre 3K et 3P, qui sont: « 3C 3P » et « 3P »
Q6.  1 séquence entre 3K et 3K: « Passe »

Récurrence:
Q7.  S(n+1) = 2S(n), il y a, par définition, S(n) séquences (de la forme E(1),E(j),E(k),…E(n+1)) qui commencent par l’enchère la plus basse E(1) (celle située juste au-dessus du palier inférieur E(0)) et S(n) autres qui commencent par une des n autres enchères E(j) que la plus basse (de la forme E(j),E(k),…E(n+1)).
Q8. S(n)=2n-1  (voir en quoi le cas n=0 est pathologique)

Exercice sur les séquences-relais

Q9.  1 séquence-relais entre 3K et 3C:  « 3C »
Q10.  2 séquences-relais entre 3K et 3P: « 3C 3P » et « 3P »
Q11.  1 séquence-relais entre 3K et 3K: » Passe »
Q12.  3 séquences-relais entre 3K et 3SA: « 3C 3P 3SA », « 3P 3SA » et « 3SA »

Récurrence:
Q13. R(n+1) = R(n)+R(n-1), il y a R(n-1) séquences-relais qui commencent par l’enchère la plus basse (celle située juste au-dessus du palier inférieur) et R(n) autres qui commencent par les n autres enchères que la plus basse.
Plus précisément: E(0) et E(n+1) sont les bornes de l’intervalle d’enchères séparées par la distance n+1. La 1e enchère de l’émetteur est E(1), E(2)… ou E(n+1).
Si c’est E(1), le récepteur relaie, par force, avec E(2) et cela ouvre un ensemble de séquences-relais dans l’intervalle [E(2),E(n+1], dont le nombre est par définition R(n-1)
Si c’est E(2), E(3) ou plus haut (jusqu’à E(n+1)), tout se passe comme si on considérait les séquences engendrées par un relais préliminaire fait à E(1) et le nombre de ces séquences est celui correspondant à l’intervalle [E(1),E(n+1)], soit R(n)
On reconnaît la propriété des suites de Fibonacci et comme R est initialisé par les valeurs 1 pour n=1 et 2 pour n=2, R(n) est le n+1ème nombre de Fibonacci.
Il existe une formulation analytique des nombres de Fibonacci (démonstration hors-sujet):formule1qui est bien toujours un nombre entier!

Synthèse:
Q14.tab3

Q15.  R ⊂ S

….

….
Retour à l’énoncé

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s