Problème de l'enfer

[invited056d314]

Problème de l'enfer

--------------------------------------------------------------------------------

Est-ce quelqu'un peut me donner un indice pour les parties B et C ? 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
-----

[God's Breath]

Est-ce quelqu'un peut me donner un indice pour les parties B et C ? Tout ce que j'ai déterminé, c'est que f(7, 3) = 7.

Et la réponse de Médiat ??

[invited056d314]

La solution de Médiat n'est pas suffisament rigoureuse et c'est pour la partie C que j'ai besoin d'aide.

[God's Breath]

La solution de Médiat n'est pas suffisament rigoureuse.

Elle est bien bonne !!

[A voir en vidéo sur Futura]

[God's Breath]

Et la réponse de Jeanpaul qui ressemble furieusement à celle de Médiat... c'est aussi du pipi de chat ?

[invited056d314]

Et pour la partie C, est-ce que tu as une idée ?

[invité576543]

A droite d'une place avec cadeau, il y a un vide. On groupe les deux places. On se retrouve avec k double places avec cadeau à gauche, et n-2k places vides, total n-k.

Prenons une place. Trois possibilités:

Soit elle est vide avec vide à gauche, C(n-k-1,k) cas

Elle est avec cadeau, C(n-k-1,k-1) cas

Elle est vide avec cadeau à gauche, C(n-k-1,k-1) cas

Le nombre de possibilités est donc 2C(n-k-1,k-1) + C(n-k-1,k)

(A vérifier, j'ai la flemme de le faire, si faux, la ligne de raisonnement doit pouvoir se corriger.)

2C(n-k-1,k-1) + C(n-k-1,k) = C(n-k,k) n/(n-k)

Cela évite de s'emmerder avec une récurrence...

Cordialement,

[invited056d314]

C'est bien, mais ce n'est pas suffisament rigoureux.

[invité576543]

C'est bien, mais ce n'est pas suffisament rigoureux.

Avec cette réponse de mauvaise aloi, tu as gagné l'arrêt de toute aide de ma part.

Cordialement,

[invité576543]

Aller, je donne quand même quelque chose : j'ai une solution multiple de 2009 avec n+k plus petit que 100... (si tout du moins la formule que je propose est exacte!)

Cordialement,

[God's Breath]

Aller, je donne quand même quelque chose

Quelle grandeur d'âme.
Et pour une fois, ce sera peut-être suffisamment rigoureux.

[invité576543]

Mouais... (pour la grandeur d'âme )

C'est surtout que le problème (la question C) m'énerve. Je trouve une petite solution par tâtonnement, mais comment prouver que c'est bien le minimum m'échappe...

Cordialement,

[invited056d314]

J'apprécie grandement ton aide.


Merci !

[invité576543]

Si tu as déjà le bac, c'est dans quel contexte cette question?

Cordialement,

[invited056d314]

Je participe à un concours de mathématiques en avril. Il s'agit d'une question pour me préparer à écrire l'examen.

Merci !

[invite6754323456711]

Je participe à un concours de mathématiques en avril. Il s'agit d'une question pour me préparer à écrire l'examen.

Si tu as de telles questions tu as intérêt d'être dans ton assiette le jour de l'examen

Patrick

[invited056d314]

Oui....définitivement !

Il faut dire que toutes les questions ne sont pas aussi difficiles que celle-ci.

[Médiat]

C'est surtout que le problème (la question C) m'énerve. Je trouve une petite solution par tâtonnement, mais comment prouver que c'est bien le minimum m'échappe...

Entre 55 et 60 ?
Si oui, des considérations de divisibilités fonctionnent assez bien, même si je n'exclus pas une erreur de calcul (41 est premier et il y a autant de facteur au dénominateur qu'au numérateur dans C(n, p))

[invité576543]

Entre 55 et 60 ?
Si oui, des considérations de divisibilités fonctionnent assez bien, même si je n'exclus pas une erreur de calcul (41 est premier et il y a autant de facteur au dénominateur qu'au numérateur dans C(n, p))

J'ai plus petit (sauf erreur, et sur la base de la formule que j'ai donnée, qui a l'air de résister aux épreuves), et la démo que c'est le minimum. Effectivement par des considérations de divisibilité.

Avec un petit lemme simple : si p premier, C(n, k) avec n<p², k entre 1 et n, ne peut pas être un multiple de p².

Mais tout compris ma démo n'est pas simple, plusieurs sous-cas à traiter, pas beau.

Cordialement,

[Médiat]

(sauf erreur, et sur la base de la formule que j'ai donnée, qui a l'air de résister aux épreuves)

J'ai trouvé la même et je l'ai lourdement testée.

Avec un petit lemme simple : si p premier, C(n, k) avec n<p² ne peut pas être un multiple de p².

C'est bien à cela que je faisais allusion.

J'ai plus petit , et la démo que c'est le minimum.

On parle bien de la somme n + k ?

Mais tout compris ma démo n'est pas simple, plusieurs sous-cas à traiter, pas beau.

Je pensais avoir une démo (avec 2 sous cas dont un qui s'évacue très facilement), mais ta meilleure solution infirme la mienne.

Cordialement,

[invité576543]

On parle bien de la somme n + k ?

Oui. On va faire plaisir au questionneur, qui va gagner un bonus non mérité : (49,5) --> 602.2009, n+k=54

En espérant ne pas m'être planté

Cordialement,

[invite7863222222222]

Ne peut-on pas utiliser des résultats connus sur la suite de fibonacci ?

[Médiat]

(49,5)

Nos méthodes doivent être identiques, mais au dernier moment j'ai pris le plus petit n-k (et donc j'avais (49, 7)) ce qui n'est pas la meilleure solution pour avoir le plus petit k

[Médiat]

Ayant été sollicité par mp, je donne quelques indications, avec un manque de rigueur évident :
Point de départ : le nombre de positions est
et 2009 = 7².41

Ma remarque, dans un message précédent, que possède autant de facteur au dénominateur qu'au numérateur permet d'affirmer que le nombre de multiples de 7 (par exemple) du numérateur ne peut être supérieur au (nombre de multiples de 7) + 1 du dénominateur, c'est à dire qu'un seul multiple de 7 au plus peut contribuer au résultat (le "petit lemme" de mmy est une conséquence directe de ceci).

Si on suppose que le facteur 41 est fourni par le n de la fraction, il faut n > 41 sinon n-k < 49 (ce qui est impossible à cause de la remarque précédente), donc n et a fortiori (n+k) au moins égal à 82.

Si on suppose que le facteur 41 est fourni par , il faut n-k > 41 (pour que 41 apparaisse au dénominateur, et pas dans le (n-k) de la fraction) et n-2k < 41 (pour que 41 n'apparaissent pas au dénominateur).
De plus il faut que n soit un multiple de 7 supérieur à 43 (puisque k > 2), le plus petit est 49 ce qui tombe bien, puisque nous n'avons plus à nous préoccuper de ce facteur. Les équations deviennent :

n=49
49-k > 41 ou k<8
49-2k < 41 ou k > 4

La plus petite valeur de k qui fonctionne est k = 5 (et c'est là où je m'étais trompé en sélectionnant le plus petit n-k au lieu du plus petit k, ce qui me donnait 56 comme résultat) qui donne un résultat de 54, il est donc inutile de revenir sur la première solution qui ne peut donner que des résultats > 82.

[invited056d314]

Je vous remercie !

[invited056d314]

Médiat,

Est-ce que tu pourrais donner un peu plus de détails svp ?

Merci !

[Médiat]

Est-ce que tu pourrais donner un peu plus de détails svp ?

Je veux bien mais précise ta question, je ne pense pas que tout soit obscur.

[invité576543]

Est-ce que tu pourrais donner un peu plus de détails svp ?

On t'a donné tellement d'éléments que ce serait mieux pour ton entraînement que tu travailles par toi-même, il me semble.

Ce que j'en dis, c'est pour toi : dans ce domaine on apprend en cherchant par soi-même, pas en lisant les solutions écrites par d'autres.

Cordialement,

[invited056d314]

De toute façon, qu'est-ce qui te dit que n + k = 54 est la plus petite valeur possible qui fait en sorte que f(n, k) est un multiple de 2009.
À ce que je sache, il y a bien d'autres multiples de 2009 que 602 x 2009 !!!

[acx01b]

edit: n'importe quoi pardon