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
[+]

 #26 - 30-11-2013 13:56:47

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

Enigme es Chaussures

@nodgim : Peut-être bien oui, mais cela ne donne toujours pas le critère. Certains d'entre vous ne sont plus très loin de le trouver. Je rajoute un peu de temps.

Je vous propose de vous concentrer d'abord sur le cas particulier [latex]n=15[/latex], qui vous permettra, si vous le résolvez, d'extrapoler directement au cas général.

Dans l'énigme initiale proposée par Sasorii, nodgim a montré que c'était impossible pour [latex]k=5[/latex]. Et sa démonstration s'applique lorsque [latex]k[/latex] est un diviseur de [latex]n[/latex]. Donc pour [latex]k=1, 3, 5, 15[/latex].

Au contraire, comme l'a expliqué gwen, on peut facilement y arriver pour [latex]9 \leq k \leq 14[/latex].

Mais que se passe-t-il pour les autres valeurs de [latex]k[/latex] ?

1) Est-ce possible d'y arriver avec [latex]k=8[/latex] ? Si oui comment ? Sinon pourquoi ?

2) Est-ce possible d'y arriver avec [latex]k=7[/latex] ? Si oui comment ? Sinon pourquoi ?

3) Est-ce possible d'y arriver avec [latex]k=6[/latex] ? Si oui comment ? Sinon pourquoi ?

4) Est-ce possible d'y arriver avec [latex]k=4[/latex] ? Si oui comment ? Sinon pourquoi ?

5) Est-ce possible d'y arriver avec [latex]k=2[/latex] ? Si oui comment ? Sinon pourquoi ?

#0 Pub

 #27 - 30-11-2013 19:35:49

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

Enigme des Chaussurs

Je propose ce double critère (pour que ça marche):
R(2n/2k)>=n-(k-1)*[n/k]<=k-1.
où R() est reste de division et []partie entière.

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

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

Enigme des Chaussuers

Oui nodgim c'est bien ça bravo !!!!

Peux-tu partager ton raisonnement ?

 #29 - 01-12-2013 09:42:55

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

enigme fes chaussures

Pour faire le plus simple possible:

GGG.....GGG.....GGG....GGG.....

Si G est minoritaire dans l'intervalle 2k, il occupe k-1 emplacements dans chaque intervalle, D en occupant k+1 (on a tout intérêt à mettre le plus de G possibles dans 2k). 
Le nombre d'intervalles distincts est [2n/2k]. Le nombre de G qu'on peut mettre est donc (k-1)*[2n/2k]. Mais il faudra bien mettre tous les G, au nombre de n.
Le restant des G à placer à la fin est donc n-(k-1)*[2n/2k]. Et il faut les placer dans le reste de la division R(2n/2k). Mais ce R étant <2k, on ne peut donc  placer que au plus (k-1) G.

D'où
R(2n/2k)>=n-(k-1)[2n/2k]<=k-1.

 #30 - 01-12-2013 10:47:28

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

EEnigme des Chaussures

Je pense qu'un k donné permet de gagner pour tous les n compris entre (2k)i et (2k-1)(i+1) avec i entier de 1 à (2k-1)
Le premier n possible pour un k donné est 2k
Le dernier n possible pour un k donné 2k(2k-1)

 #31 - 01-12-2013 11:42:20

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

enigme des chaussires

@nodgim : Ok, tu as raisonné comme moi. Tu ne distingues pas trop les conditions nécessaires et suffisantes, mais l'essentiel est là.

@gwen : c'est valable pour k=1 ? Et pour k=5 et n=11 par exemple ?

 #32 - 01-12-2013 11:50:09

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

Enigme de sChaussures

Non, je suis parti de k=3
Mais ça doit être valable
pour k=1 : (1 2 1)   --> n=2
et pour k=2 : (2 4 2 ) , (3 5 2) , (3 6 3) ,  (2 4 3 4 3) , (3 5 3 4 3)  et (3 4 3 4 3 4 3)
--> n= 4 5 6 8 9 12

Le développement pour 2 exemples :
http://www.prise2tete.fr/upload/gwen27-chauss.JPG

 #33 - 01-12-2013 12:35:39

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

enigme des chayssures

Gwen, tes exemples ne sont pas bons :

par exemple pour k=1 et n=2, sur (1 2 1) ça foire dès le premier intervalle.

Idem pour tous les autres exemples.

 #34 - 01-12-2013 12:52:17

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

enigme des chaussires

Effectivement, pas le temps de tout refaire. Je me suis trompé d'un cran.

 #35 - 02-12-2013 23:53:31

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

Enigme dse Chaussures

Bravo à nodgim, le seul à avoir trouvé !

Je reprends son critère et son raisonnement, un peu réarrangé à ma sauce.

On note [latex]q[/latex] et [latex]r[/latex] le quotient et le reste dans la division de [latex]n[/latex] par [latex]k[/latex].

Le critère est le suivant :

Il est possible de disposer les [latex]2n[/latex] chaussures 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 si et seulement si :
[TeX]r \geq q[/latex]   et   [latex]k \geq q+r+1[/latex]



Démonstration :

1) C'est une condition nécessaire :

Supposons que [latex]2n[/latex] chaussures ont été disposées 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. On numérote alors les chaussures d'une extrémité à l'autre, de [latex]1[/latex] à [latex]2n[/latex] et l'on note [latex]G [i,j][/latex] le nombre de chaussures gauches parmi les chaussures dont le numéro est dans l'intervalle [latex][i;j][/latex].

Quitte à échanger les chaussures gauches et droites, on peut supposer que [latex]G[1,2k]\leq k-1[/latex].

On montre alors par récurrence que [latex]G[1+i,2k+i]\leq k-1[/latex], et ce [latex]\forall i \in [0,2n-2k][/latex].

En effet, [latex]G[1+i+1,2k+i+1] \leq G[1+i,2k+i]+1[/TeX]
et [latex]G[1+i+1,2k+i+1]\neq k[/latex].


Rappelons pour la suite que [latex]n=kq+r[/latex] avec [latex]0\leq r <k[/latex].
[TeX]G[2kq+1,2n] = G[1,2n] - G[1,2kq] = n - \sum_{i=1}^{q} G[(i-1)2k+1,i2k] \geq n-q(k-1)[/TeX]
donc [latex]G[2kq+1,2n] \geq r+q[/latex]

Or [latex]G[2kq+1,2n] \leq 2n-2kq = 2r[/latex] ce qui donne [latex]2r \geq r+q[/latex] et donc [latex]r \geq q[/latex].

D'autre part [latex]G[2kq+1,2n] \leq k-1[/latex] ce qui donne [latex]k-1 \geq r+q[/latex] et donc [latex]k \geq q+r+1[/latex].

2) C'est une condition suffisante :

Supposons que [latex]r \geq q[/latex]   et   [latex]k \geq q+r+1[/latex]

On réalise alors la suite de chaussures suivante :
[TeX]\left(G^{k-1}D^{k+1}\right)^{q-1}G^{k-1}D^{k+1+r-q}G^{q+r}[/TeX]
Cette suite convient car :

le nombre de chaussures gauches est :
[TeX](k-1)q+(q+r)=kq+r=n[/TeX]
le nombre de chaussures droites est :
[TeX](k+1)(q-1)+(k+1+r-q)=(k+1)q-q+r=kq+r=n[/TeX]
le dernier groupe de G compte moins de [latex]k-1[/latex] chaussures :
[TeX]k \geq q+r+1[/latex] donc [latex]k-1 \geq q+r[/TeX]
le dernier groupe de D compte plus de [latex]k+1[/latex] chaussures :
[TeX]r \geq q[/latex] donc [latex]k+1+r-q \geq k+1[/TeX]
CQFD


Application Numérique :

Dans l'exemple initial donné par Sasorii avec [latex]n=15[/latex], il y a d'autres longueurs d'intervalles pour lesquelles il est impossible de réaliser une suite de chaussures satisfaisant les conditions imposées.

Il est possible de remplacer [latex]k=5[/latex] par n'importe quel entier [latex]k[/latex] de l'ensemble [latex]\lbrace{1;2;3;4;5;7;8\rbrace}[/latex].

 #36 - 03-12-2013 18:05:36

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

Enigme des Cahussures

J'allais envoyer un petit complément pour une remise en forme plus conviviale des 2 inégalités, tu l'as fait dans la démo, c'est donc parfait !

 

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 : 

Si il y a 63 pommes et que vous en prenez 23, combien en avez-vous ?

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