Défi (problème d'arrangements)

[invited056d314]

J'ai vraiment besoin d'aide....svp. Est-ce que quelqu'un peut me donner un indice ? Tout ce que j'ai déterminé, c'est que f(7, 3) = 7.



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
-----

[Médiat]

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.

Bonjour,

Inutile de mettre défi dans le titre, surtout pour un problème sans réelle difficulté, pour motiver les lecteurs, cela peut avoir l'effet inverse !

Pour cette question, il te suffit de "distinguer" une des n places et de te demander :
1) Dans combien de configurations cette place n'a pas de cadeau
2) Dans combien de configurations cette place a un cadeau (et si elle a un cadeau ...)

La somme des deux devrait donner la totalité des configurations ...

[invited056d314]

Avant de dire que ce problème n'est pas un défi, est-ce que tu as regardé la partie C) ?

[invited056d314]

Selon Médiat, je devrais changer mon titre à "Petit problème facile d'arrangements".

Si le problème est si facile, pourquoi se fait-il qu'après une heure de travail, je n'ai pas encore complété la partie (C).

(J'ai un bacc. en mathématiques)

[A voir en vidéo sur Futura]

[invited056d314]

Si je comprend bien, il n'y a personne qui comprend comment résoudre ce problème. C'est bien ce que je croyais.... au moins, maintenant, je me sens moins con !

[acx01b]

salut

si je ne me suis pas trompé:

f(n,k) = 0 si n < 2k
f(n,1) = n
f(2k,k) = 2
f(n+1,k) = f(n,k) + f(n-2,k-1)

[acx01b]

pour la C)

on a f(2k+1,k) = f(2k,k) + f(2k-1,k-1) = f(2k,k) + f( 2(k-1) + 1, k-1)

comme f(2k,k) = 2 et f(3,1) = 3

on a par récurrence f(2k+1,k) = 2*(k-1) + 3 = 2k+1

et donc f(2009,1004) = 2009

[invited056d314]

Merci....Accro !

Ton raisonnement semble juste, mais je doute que ce soit assez rigoureux comme démonstration.

[acx01b]

pouquoi tu vas me mettre une mauvaise note si je te rends pas une démo bien rédigée ?

et y'a toujours le problème de montrer que (2009,1004) c'est le plus petit couple d'entier (plus petit n+k) tel que f(....) = 2009

[invited056d314]

Oui, c'est ça le problème.

Merci pour ton aide.