Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 26-11-2013 13:25:40

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Enigme des Chaussrues

Jacques a [latex]n[/latex] paires de chaussures.

Il veut les disposer les unes à côté des autres sans qu'il existe un intervalle de [latex]2k[/latex] chaussures contenant autant de chaussures gauches que de droites.

Pour quelles valeurs de [latex]n[/latex] et [latex]k[/latex] peut-il y arriver ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 26-11-2013 18:29:03

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Enigme ddes Chaussures

On ne peut pas empêcher, si l'intervalle n'occupe que la moitié au plus du total, d'avoir 1 fois au moins une égalité (cf l'explication dans l'énigme précédente). En fait, si toutes les chaussures hors intervalles sont au moins aussi nombreuses que celles de l'intervalle.
Pour n'avoir jamais l'égalité, il faut:
2k>=n+3 si n impair
2k>=n+2 si n pair.
pour tenir compte de la parité.

Exemple n=7
---+++++++----
Pour que l'intervalle soit tjs +, il faut prendre au moins 10 éléments.

 #3 - 26-11-2013 18:41:33

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

enigme des chayssures

Ça c'est une conjecture faite par gwen, sans aucune explication.

Si tu veux tenter une démonstration...

 #4 - 26-11-2013 19:54:58

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Enigme des Chaussurees

Ah, si j'ai expliqué. (dans le post précédent ma modification) Sur un intervalle plus petit que la moitié (le premier écart étant positif) , en le décalant on tombe obligatoirement sur un nombre nul vu qu'il en existe un négatif dans l'autre partie.

Ce qui n'est pas le cas si les deux intervalles se recouvrent partiellement.

 #5 - 26-11-2013 21:23:22

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Enime des Chaussures

Donc, ton raisonnement est le suivant :
(en reprenant les définitions de nodgim)
On regarde le premier intervalle. Il est positif par exemple. Dans l'autre partie, il existe forcément un intervalle négatif.

Ma question est : Pourquoi dis-tu qu'il existe forcément un intervalle négatif dans l'autre partie ?

 #6 - 26-11-2013 21:40:09

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Enigme des Chasusures

Bah parce que si on accole ces intervalles au lieu de les décaler.

[1 2 3][ 4 5 6] 7 8 ...

Et qu'ils sont tous positifs, le dernier (même avec moins d'éléments) est négatif de la somme de tous les premiers.

 #7 - 26-11-2013 21:45:12

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Enigme des Chasusures

Le dernier est l'opposé de la somme de tous les premiers ?

Oui, si le dernier intervalle a la place d'entrer... donc lorsque k divise n.
Mais sinon ?

EDIT : Tu fais un dernier intervalle avec moins d'éléments ? Alors là oui il est négatif, mais le reste de la démo pour le passage par 0 ne tient plus alors.

 #8 - 26-11-2013 22:21:35

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3308

enigle des chaussures

Il suffit que [latex]n[/latex] et [latex]2k[/latex] soient premiers entres eux non ?


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #9 - 26-11-2013 22:34:49

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

enigme des cjaussures

Si parce que dans mon exemple (OK, j'en ai mis un nombre impair et pas pair, mais ça ne change rien)

[6 7 8 ] est forcément impair, pas seulement [7 8 ]

Et même [5678] négatif ou nul car il y a 2 intervalles positifs avant.

 #10 - 26-11-2013 23:12:46

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Enigme des Chaussurres

@shadock : Donc, d'après toi, c'est possible avec n=5 et k=3 ?

@gwen : Je ne comprends pas pourquoi tu fais un exemple avec des intervalles de 3 alors que les intervalles sont de longueur paire. Peux-tu détailler ton raisonnement complètement ?

 #11 - 26-11-2013 23:33:42

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

enigme drs chaussures

Il y a des fois où je me dis que tu te forces pour ne pas comprendre (ou alors tu en fais exprès car tu attends un truc précis en réponse... mais c'est limite irritant)

On prend l'intervalle initial et l'intervalle final.

1) on passe de +x à -y : on passera par 0 de pas en pas.
2) on pase de -x à +y : idem

3) on passe de +x à +y : on n'est pas obligé de passer par 0 mais la somme globale est positive (incompatible avec l'énoncé)

4) on passe de -x à -y : idem

5) on passe de 0 à +/-x ou l'inverse : on a aussi le 0

 #12 - 27-11-2013 00:39:38

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Enigme des Chhaussures

Gwen, j'essaie juste de comprendre ton raisonnement pour te faire mettre le doigt sur ce qui ne va pas.

Pour 1) 2) 5) on est d'accord. C'est sur 3) 4) que je ne te suis plus.

Voilà, pourquoi est-ce que tu dis que quand les intervalles extrêmes sont positifs, on passe forcément par 0 ou que la somme est forcément positive ?

 #13 - 27-11-2013 11:22:11

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Enigme des Chhaussures

Effectivement, on doit pour bloquer jusqu'à ent(n/2)-1 avec une disposition de type

1/3 1/2 1/3 1/2 1/3

Pour 12 : 4 6 4 6 4 = GGGG DDDDDD GGGG DDDDDD GGGG  k=5
Pour 15 : 5 7 5 8 5 = GGGGG DDDDDDD GGGGG DDDDDDDD GGGGG k=6
Pour 17 : 6 9 6 8 5 = GGGGGG DDDDDDDDD GGGGGG DDDDDDDD GGGGG k=7
...

 #14 - 27-11-2013 12:09:39

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

enigme deq chaussures

De la même manière on peut y arriver pour quelques cas même si j'ai du mal à trouver la règle :

n=24 k=7
6 8 6 8 6 8 6

n=40 k=9
8 10 8 10 8 10 8 10 8

...

 #15 - 27-11-2013 18:56:20

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

enigme des chausqures

Oui bravo gwen pour tous ces contre-exemples. Ça devrait peut-être t'aider à trouver la règle générale.

 #16 - 27-11-2013 19:34:59

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

enigmr des chaussures

J'aurais tendance à dire : les cas où n/x et n/(x+1) sont espacés de 2 globalement(il faudrait mettre des parties entières)

Dans ce cas, n/x+1 est solution.

 #17 - 27-11-2013 23:00:02

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Enigme des Chasusures

A tous ceux qui s'intéressent à ce problème, sachez que la conjecture émise par Gwen sur l'autre fil est fausse. Saurez-vous trouver un contre-exemple ?

@Gwen : x c'est k ? Quand tu dis x/n+1 est solution qu'est-ce que tu veux dire ? Tu peux donner un exemple ?

 #18 - 27-11-2013 23:06:18

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Enigm des Chaussures

x est une inconnue distincte de n ou k  qui correspond au cas de figure.

Pour 24 : je cherche 24/x et 24/(x+1) tel que le résultat corresponde à 2 de différence.

Or 24/3=8 et 24/4=6   24/4  +1 = 24/3 -1    = 7 solution.

Vu que je ne suis pas sûr de moi, je prends exprès un cas qui tombe pile pour exemple.

 #19 - 28-11-2013 00:00:47

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

enigme des xhaussures

Je ne pense pas que cette piste donne quoi que ce soit, parce que ça ne donne pas du tout les cas possibles correspondant à ta conjecture.

Il faudrait peut-être prendre le problème à l'envers et commencer par voir dans quels cas c'est impossible. Déjà, en s'inspirant du cas n=15 et k=5 de l'autre fil, voir dans quels cas c'est clairement impossible.

 #20 - 28-11-2013 18:14:16

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Enige des Chaussures

Essayons de simplifier au maximum:
Supposons D tjs majoritaire. Je ne reviens pas sur la simple démo comme quoi l'intervalle doit être supérieur à la moitié, c.a.d. qu'il doit y avoir recouvrement, et bien entendu recouvrement des chaussures majoritaires dans tous les intervalles. Le recouvrement de chaussures minoritaires est à exclure, il ne va pas dans le sens de l'optimisation.
Soit à l'intervalle extrême G n chaussures G. Il faut au minimum n+2 D, donc intervalle de 2n+2 (ce qui confirme la parité de l'intervalle).
A l'intervalle extrême droite, on trouve soit:
-n chaussures G. Donc en tout 4n chaussures. Recouvrement de 2 chaussures D (4n+4)-4n=4
-n-1 chaussures G, donc en tout 4n-2 chaussures. Recouvrement des D:
2(2n+2)=4n+4. Or seulement 4n-2 chaussures, donc recouvrement de 3 D.

Donc tjs un intervalle minimum de 2n+2 chaussures pour un nombre de chaussures total de 4n ou 4n-2.

 #21 - 28-11-2013 19:04:11

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Enigme des Chaussues

nodgim, il est possible d'y arriver avec un intervalle inférieur à la moitié !

Cherche bien...

 #22 - 29-11-2013 18:02:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

enigme des chausdures

J'étais loin du sujet là....
Recommençons.
Soit G les minoritaires dans l'intervalle. Les G doivent être excédentaires aux extrémités.
Prenons un intervalle de n G et n+2 D (différence minimale pour excédent de D)
n,n+2.
reproduisons le k fois
n,n+2,n, n+2, n, n+2,......n r
On finit sur n (G) et un r qui est à définir.
Pour avoir l'égalité D/G:
r=(k+1) n -k(n+2)=n-2k.
On a intérêt à avoir un r minimal, soit 0 soit 1. Dans les 2 cas, k=[n/2]

Donc pour un n donné:
I intervalle=2n+2
T total de chaussures=[n/2]*I+n auquel on ajoute 1 si n impair.

Rapport I/T=1/[n/2] à l'unité près.

Exemple n=5
k=2 I=12 T=30.

séquence: 5,7,5,7,5,1. On peut trouver beaucoup de variantes de cette distribution, le groupement des G et des D n'étant pas impératif. Mais cette présentation est la plus simple.

 #23 - 30-11-2013 01:58:49

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

Enigme des Cahussures

Tout d'abord, si k<n<2k-1, on peut ranger k-1 chaussures gauches, n chaussures droites puis le reste des chaussures gauches (n-k+1 qui vérifie n-k+1<k).

Mais il est possible de trouver un rangement pour n plus grand que 2k-1 :

Pour k donné, on va ranger les chaussures en paquet de k-1 chaussures gauches puis k+1 chaussures droites. Ainsi, tous les intervalles de k chaussures contiennent plus de droites que de gauches. On termine avec k-1-z chaussures gauches où y chaussures droites.
Évidemment pour que ce rangement fonctionne, il faut avoir autant de droites que de gauche. n=i(k+1)+y, nombre de chaussures droites et n=(i+1)(k-1)-z chaussures gauches, où i est le nombre de paquet de k+1 chaussures droites.

Comme y+z>=0, i vérifie i(k+1)<=(i+1)(k-1) donc i>(k-1)/2 : imax = E((k-1)/2).
Nmax sera atteint pour imax et z=0 : Nmax=(k-1)E((k+1)/2)

Mais il faut aussi que l'on ne termine pas le rangement par 1 paquet de droite incomplets suivi par des chaussures gauches : y (que l'on peut montrer <=k) et z ne doivent pas être non nuls simultanément. En d'autre terme, il faut que soit k-1 soit k+1 divisent n.

application pour k=5, on a Nmax=12
n=12, 5-1 divise n : rangement possible 4G6D4G6D4G
n=11, ni 5-1 ni 5+1 ne divisent n : rangement impossible
n=10, ni 5-1 ni 5+1 ne divisent n : rangement impossible
n=9, ni 5-1 ni 5+1 ne divisent n : rangement impossible

n=8, 5-1 divise n : rangement possible 4G6D4G2D (pas unique)
n=7, n>2k-1 : rangement possible 4G7D3G
n=6, n>2k-1 : rangement possible 4G6D2G

problème sympa et bien prise de tête !!!

 #24 - 30-11-2013 11:17:31

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Enigme eds Chaussures

@nodgim : Bravo pour cette famille d'exemples ! Cela devrait sans doute t'aider à trouver le critère général à partir de [latex]n[/latex] et [latex]k[/latex]. (Respecte mes notations chenapan !)

@dylasse : D'après toi c'est possible avec n=2 et k=1 ? Impossible avec n=17 et k=7 ?

 #25 - 30-11-2013 12:51:20

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Enigme des Chausssures

Ok donc pour répondre partiellement à la question posée:
Si k impair, on pourra prendre au max (k²-1)/2 pour n.
Si k pair, on pourra prendre au max k(k-1)/2 pour n.

Reste à savoir quelles valeurs intermédiaires sont correctes...

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

Sujets similaires

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
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete