Écrire une réponse @ Prise2Tete

perceval · Résumé de la discussion

J'ai une belle collection de 64 cravates mais comme je suis désordonné, elles sont dispersées dans sept tiroirs différents de la manière suivante : 3, 13, 1, 14, 9, 5 et 19. Je souhaite les réunir dans un seul et même tiroir en imposant la règle suivante : si les tiroirs A et B contiennent respectivement a et b cravates avec a b>0, on peut transférer b cravates du tiroir A vers le tiroir B. A contient alors a – b cravates et B en contient désormais 2b.

Puis je parvenir à ranger toutes les cravates dans un seul tiroir en un nombre fini de manipulations. Est il possible d'y parvenir en fixant a priori le numéro du tiroir où doivent se retrouver toutes les cravates, le 7 ème par exemple ?

Généralisation : Je dispose d’une collection de 2^n cravates rangées dans k tiroirs ( n et k entiers naturels quelconques).Chacun d’eux en possède au moins une. En imposant la règle précédente, peut-on réunir toutes les cravates dans un seul et même tiroir en un nombre fini de manipulations ? Y parvenir en fixant a priori le numéro j du tiroir où seront rangées toutes les cravates.

Merci de m'aider a ranger mes affaires.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Collection de cravates Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=scarta]Alors, pour la méthode générale (k tiroirs, 2^n cravates): On pose i=0 1/ Etape 1: Précondition: tous les tiroirs ont un nombre de cravates divisible par 2^i. On prend les tiroirs dont le nombre de cravates ne soit pas divisible par 2^(i+1). Affirmation: Il y en a un nombre pair. Preuve: Supposons que l'on en ait un nombre impair (disons 2p+1). Soit T le nombre total de cravates. On pose T / 2^i = T' Pour chaque tiroir, si on divise le nombre de cravates par 2^i, on obtient (2p+1) résultats impairs et k-(2p+1) résultats pairs. La somme de tous ces nombres est donc impaire, elle vaut par ailleurs T', donc T' n'est pas divisible par 2^(i+1), ce qui est absurde. Postcondition: on a pris un nombre pair de tiroir. 2/ Etape 2: Précondition: on considère un nombre pair de tiroirs ayant un nombre de cravates divisible par 2^i mais pas 2^(i+1). On groupe ces tiroirs en paires, pour chaque paire de tiroirs ayant respectivement a et b cravates, avec par exemple a>b, on déplace b cravates de l'un vers l'autre. Affirmation: Les deux tiroirs comportent un nombre de de cravates divisible par 2^(i+1). Preuve: On pose: a/2^i = 2a'+1 b/2^i = 2b'+1 On a: a-b = (2a'+2b') * 2^i = (a'+b') * 2^(i+1) 2b = (4b'+2) * 2^i = (2b'+1) * 2^(i+1) Postcondition: tous nos tiroirs ont un nombre de cravates divisible par 2^(i+1). Soit i+1=n et on a alors terminé, soit on recommence à l'étape 1 avec i+1 au lieu de i, la précondition de l'étape 1 étant bien respectée. Nombre total maximal d'étapes: on aurait au pire k/2 paires à traiter dans l'étape 2, à répéter n fois. Autrement dit, au maximum de nk/2 opérations sont nécessaires. Concernant le tiroir de destination, vu qu'un tiroir devient vide quand on verse ses cravates dans un tiroir de même contenance, alors on pourrait tout à fait inverser le role du vide et du plei. Vu que k-1 tiroirs finissent vides, le dernier peut-être n'importe lequel. Petite application avec l'exemple des 64 cravates (qu'on va mettre dans le 1er tiroir tiens). 1 3 5 9 13 14 19 => on prend tout sauf 14. 2 2 10 4 26 14 6 => 3 opérations, on prend tout sauf 4 4 0 20 4 16 8 12 => 3 opérations, on prend tout sauf 8 et 16 8 0 8 0 16 8 24 => 2 opérations, on prend tout sauf 16 16 0 0 0 16 16 16 => 2 opérations 32 0 0 0 0 32 0 => 2 opérations 64 0 0 0 0 0 0 => 1 opération: Total: 13 opérations (< à 67/2 = 21).[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez (numériquement) à la petite énigme suivante : Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?* Retour Résumé de la discussion perceval 13-05-2008 13:48:02 J'ai une belle collection de 64 cravates mais comme je suis désordonné, elles sont dispersées dans sept tiroirs différents de la manière suivante : 3, 13, 1, 14, 9, 5 et 19. Je souhaite les réunir dans un seul et même tiroir en imposant la règle suivante : si les tiroirs A et B contiennent respectivement a et b cravates avec a b>0, on peut transférer b cravates du tiroir A vers le tiroir B. A contient alors a – b cravates et B en contient désormais 2b. Puis je parvenir à ranger toutes les cravates dans un seul tiroir en un nombre fini de manipulations. Est il possible d'y parvenir en fixant a priori le numéro du tiroir où doivent se retrouver toutes les cravates, le 7 ème par exemple ? Généralisation : Je dispose d’une collection de 2^n cravates rangées dans k tiroirs ( n et k entiers naturels quelconques).Chacun d’eux en possède au moins une. En imposant la règle précédente, peut-on réunir toutes les cravates dans un seul et même tiroir en un nombre fini de manipulations ? Y parvenir en fixant a priori le numéro j du tiroir où seront rangées toutes les cravates. Merci de m'aider a ranger mes affaires. Pied de page des forums P2T basé sur PunBB Screenshots par Robothumb © Copyright 2002–2005 Rickard Andersson
Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact

Écrire une réponse

Résumé de la discussion

Pied de page des forums