Voici le défi 4 de noël !!!
Vous souhaitez décorer votre maison avec des frises d'une certaine longueur et qui sont constituées des deux motifs ci-contre : une boule rouge et une étoile dorée.
Par exemple un frise de longueur 4 peut être réalisée par la suite : 'boule' ; 'boule', 'étoile', 'boule'.
Une frise est bien proportionnée lorsqu'elle contient autant de boules que d'étoiles : c'est le cas de la première frise (de longueur 6) ci-dessous. Une frise est complètement disproportionnée lorsque aucune des sous-frises (en partant du début) n'est bien proportionnée : c'est le cas de la seconde ci-dessous.
Décorons votre maison avec une frise de longueur 2014.
Défi 4 en deux questions : combien peut-on fabriquer de frises bien proportionnées différentes ? Et combien de frises complètement disproportionnées ?
Tentez votre chance : postez une ou deux réponses en commentaire ; le défi est limité dans le temps jusqu'au 24 décembre à minuit.
10 réactions
1 De Valentin Thirion - 09/12/2014, 20:14
Je ne suis pas sur d'avoir exactement compris la question. Demande-t-on le nombre de frises bien proportionnées (ou disproportionnées) de 2014 motifs différentes ?
Ou est-ce le nombre de frises bien proportionnées (ou disproportionnées) d'un nombre quelconque de motifs différentes qu'on peut réaliser avec 2014 motifs au total ? (Ex: Avec 6 motifs je peux réaliser une frise de 6 motifs, mais également 1 frise de 4 motifs et 1 frise de 2 motifs, ou 3 frises de 2 motifs...)
2 De Romain Validire - 09/12/2014, 20:59
Les frises sont réalisées avec des motifs de deux sortes : boules (o) ou étoiles (*). Le nombre de motifs c'est la longueur de la frise.
Par exemple, avec 4 motifs (donc longueur 4) :
Et en considérant une longueur de 2014 ? Ce sont les questions du défi 4.
3 De Valentin Thirion - 09/12/2014, 21:38
Après plusieurs essais sur des frises de petites longueur, il me semble que le nombre de frises bien proportionnées différentes est pour une frise de longueur n est la somme des k parmi n/2 au carré pour k allant de 0 à n/2 (càd la somme des termes au carré de la (n/2)+1 ième ligne du triangle de Pascal):
En appliquant ce raisonnement pour n=2014, je trouve toutefois un nombre trop grand pour être affiché en Python, ce qui me laisse penser que j'ai fais une erreur... Ou alors qu'il y a un moyen plus simple d'écrire ce nombre.
4 De Romain Validire - 10/12/2014, 09:13
Sans rien dire sur la validité de la solution que vous avez proposée, je peux au moins affirmer que le nombre cherché peut être calculé et affiché (en base 10) par Python puis recopié ici-même.
Mais ça tombe bien... Jeudi on parle de complexité des algorithmes.
5 De Valentin Thirion - 11/12/2014, 15:51
J'ai remarqué que ce que j'avais écris dans mon message précédent en italique est en réalité égal à n/2 parmi n pour une frise de longueur n (Avec n pair bien entendu).
Cette relation ne me semble pas illogique dans la mesure où on doit avoir n/2 éléments identiques pour avoir une frise de longueur n bien proportionnée. On demande donc le nombre de façon possible d'avoir n/2 éléments identiques sur les n éléments de la chaîne.
Cela fonctionne au moins pour 2 (1 parmi 2 = 2), pour 4 (2 parmi 4 = 6), pour 6 (3 parmi 6 = 20, ce que j'ai bien retrouvé en écrivant les frises à la main) et cela semble également fonctionner pour 8 (4 parmi 8 = 70, je n'ai pas eu le courage de tout écrire mais ce que j'ai trouvé semblait indiquer ce nombre). Evidemment, cela devient fastidieux pour de plus grandes frises, donc je n'ai pas poussé mes essais plus loin...
Après plusieurs essais pour trouver un programme python pouvant donner un résultat affichable pour 1007 parmi 2014, je suis finalement parvenu à celui-ci:
def CoeffBinom(n, k):
Coeff = 1 for j in range(1, k+1): Coeff = Coeff * (n-j+1) // j return CoeffEn l'utilisant je trouve une valeur assez... grande :
33440109139727336238389126578332605354222544866538778008156877616242647902540140891037287241075508810325026409216813829145638949835383318837409995156192718059082430562723496812588052915029275583516886259958909207866772232906925163882103108035353382110953914204306942288826448019043810683529235098537439607097049997798548711208479544533844268055144146131020059705167514282049779087608124607924109499451754282735700404398220305067187559956114475217389866747569564770389041134189592172661730885555135294878554464382919977741541795471415826425141352991090708701090311690159944760491075477284784276384502627840
Mais compte tenu de la définition des coefficients binomiaux cela ne me paraît pas absurde... En supposant évidemment que la relation que j'ai trouvé est bien valable et que ce n'est pas juste une coïncidence si elle fonctionne pour les premières valeurs de n.
6 De Romain Validire - 11/12/2014, 19:51
La réponse pour les frises bien proportionnées est enregistrée. Il reste à dénombrer les frises totalement disproportionnées.
Tout le monde peut encore participer et proposer une valeur : résultats à partir du 25 décembre.
7 De Bourgeade Adrien - 18/12/2014, 21:11
étrangement ça me rappelle un programme que l'on devait faire pendant les longues soirées d'hiver si ma mémoire est bonne.^^
8 De Romain Validire - 20/12/2014, 09:05
... Et pourtant ce n'est pas du tout le même dénombrement. Mais rassurez-vous, celui-ci va aussi (sous une autre forme) vous occuper un peu pendant ces vacances.
9 De thierno Laye - 21/12/2014, 19:18
Pour la première question je pense que:
on prend 1007 boules parmi 1007 et 1007 étoiles parmi 1007
puis on cherche l'anagramme de 2014 éléments avec autant de boules que d'étoiles.
donc l'opération est:2014!/1007!*1007! c'est à dire l'anagramme vu que les combinaisons valent 1.
10 De Romain Validire - 12/01/2015, 13:43
Félicitations à Valentin et Thierno pour vos réponses. La première réponse juste donnée étant celle de Valentin, c'est lui qui remporte le point.
Valentin + 1 point.
Rappel du classement à cette date :
Valentin : 5 points
Antoni : 1 point