Défi (permutations)

[invited056d314]

J'ai vraiment besoin d'aide....svp.

Supposons qu'il y a "n" assiettes espacées également autour d'une table circulaire. Michel veut placer un cadeau identique dans chacune de "k" assiettes de manière que 2 assiettes voisines ne puissent contenir chacune un cadeau. Soit f(n, k) le nombre de façons possibles de répartir les cadeaux. Par exemple, f(6, 3) = 2.

a) Déterminer la valeur de f(7, 3).

b) Démontrer que f(n, k) = f(n - 1, k) + f(n - 2, k - 1) pour tous les entiers tels que n est supérieur ou égal à 3 et k est supérieur ou égal à 2.

c) Déterminer la plus petite valeur possible de n + k parmi tous les couples possibles d'entiers (n, k) pour lesquels f(n, k) est un multiple strictement positif de 2009 (où n est plus grand ou égal à 3 et k est plus grand ou égal à 2).


merci
-----

[invitea3eb043e]

M'étonnerait que cette question ait été posée en lycée ou collège, enfin...
Pour la question a, on voit avec quelques petits dessins que les possibilités sont 1-3-5 , 1-3-6 , 1-4-6 , 2-4-6 , 2-4-7 , 2-5-7 , 3-5-7, soit f(7,3) = 7
Après, la récurrence. Il faut déjà y regarder de plus près.
On part avec n assiettes et k cadeaux, soit f(n,k) possibilités.
On enlève une assiette. De 2 choses l'une : elle est vide ou elle est pleine.
Si elle est vide, il y a f(n-1,k) arrangements
Si elle est pleine, nécessairement les 2 voisines sont vides. On enlève alors une de ces voisines vides et on reconstitue une configuration possible (n-2,k-1) d'où la récurrence :
f(n,k) = f(n-1,k)+f(n-2,k-1)

Pour la suite, je demande un délai.

[invited056d314]

Il s'agit d'une question facultative pour laquelle on peut recevoir des points bonis. Étant donné que je suis très perspicace, je veux essayer de la résoudre. J'avais obtenu 7 aussi pour la partie A.

Merci pour ton aide.