énigme logique...

[invite6f044255]

Salut,

j'ai une petite énigme dont j'ai la réponse mais que je n'arrive pas vraiment à me démontrer...

Quel est le nombre minimum de cassures à faire pour séparer tous les carrés d'une tablette de chocolat de 4*8 carreaux? de p*q carreaux?
-----

[shokin]

Salut Ixi,

a priori, je dirais...

j'ai 1 morceau de p*q carreaux et je veux obtenir p*q morceaux de 1 carreau, soit p*q-1 morceaux de plus. Il me faudra donc p*q-1 cassures.

A moins que ce soit comme une feuille de papier rectangulaire que je veux découper sans plier. Je fais p-1 coups de cutter horizontaux et q-1 coups de cutter verticaux pour obtenir p lignes et q colonnes, donc (p-1)(q-1) cassures.

Dommage, soit le chocolat est dur et on peut difficilement faire de même, soit il est fondu...

là tu m'as mis l'eau à la bouche, demain je vais acheter des plaques de chocolats...

dis-moi si j'ai bien compris la question.

Shokin

[invite6f044255]

salut shokin,

la question que je me pose est "pourquoi il faut p*q-1 cassures?"
Parce que si je casse la tablette en 2 morceaux de taille égale, j'ai l'impression de faire beaucoup plus de travail que pour les cassures de la fin où je sépare un morceau 2*1 en 2 fois 1*1.....

A mon avis, mon problème est pas bien compliqué, mais je n'arrive pas à formaliser de manière claire....

[shokin]

Il y a le raisonnement simple que j'ai fait :

j'ai 1 morceau et je veux avoir au final p*q morceaux donc je veux rajouter p*q-1 morceaux, et comme chaque cassure rajoute 1 et 1 seul morceau. Pour rajouter n morceaux, je dois faire n cassures. Pour rajouter p*q-1 morceaux, je dois donc faire p*q-1 cassures.

Quand tu coupes au milieu, les deux moitiés sont très "grandes", mais la somme des nombres des carreaux reste p*q.

Admettons que tu coupes en p lignes, tu feras p-1 cassures. Tu as alors p morceaux. Si chacun de ces morceaux, tu le coupes en verticales, tu fais q-1 cassures pour chacun de ces p morceaux, donc tu fais p*(q-1) cassures. Au total donc p-1+p*(q-1)=p*q-1

Idem si tu coupes d'abord en colonnes, puis en ligne. Tu obtiens q-1+q*(p-1) cassures, soit p*q-1 cassures.

Quand tu fais une cassure, où qu'elle soit, tu ne rajoutes qu'un morceau.

C'est comme si tu as n boules dans une boîte A et que tu veux mettre ces n boules dans une boîte B. Que t'en prenne une à la fois ou plusieurs, tu devras prendre les n boules.

Shokin

[A voir en vidéo sur Futura]

[invite6f044255]

Ok, merci, shokin, j'ai bien compris le truc maintenant...
En fait, je suis bête de pas y a avoir pensé...

J'étais parti sur un mauvais raisonnement: le nombre de liens entre les carreaux....

Mais avec ta solution, tout devient plus clair...