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 des Chaussurees

@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 : 3168

enugme des chaussures

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

ebigme des chaussures

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 : 3168

znigme des 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,679E+3

Enigme dse 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 dess Chaussures

@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,679E+3

enifme des chaussures

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 Chaussrues

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,679E+3

Enigme des Caussures

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 es 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 : 3168

Enigm edes Chaussures

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 à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
P2T
Enigme chaussures par Sasorii
20-11-2013 Enigmes Mathématiques
P2T
22-07-2011 Enigmes Mathématiques
P2T
L'île parfaite. par Promath-
26-09-2011 Enigmes Mathématiques
P2T
Concours Griego 1&2. par Promath-
24-02-2012 Enigmes Mathématiques
11-09-2008 Enigmes Mathématiques
P2T
Gâteau 17 par Vasimolo
28-07-2010 Enigmes Mathématiques
08-10-2010 Enigmes Mathématiques
19-10-2010 Enigmes Mathématiques
P2T
09-02-2011 Enigmes Mathématiques

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