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 dzs 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 : 3587

enigme des chaussurzs

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

enigmr 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 : 3587

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

enigme des chaussured

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

enifme des 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,852E+3

enogme 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 Chaaussures

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

Eniggme des Chaussures

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

Eingme des 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 : 3587

enihme des 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 (numériquement) à la petite énigme suivante : 

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

Sujets similaires

Sujet Date Forum
P2T
Enigme chaussures par Sasorii
20-11-2013 Enigmes Mathématiques
P2T
Equilibrio1 par Promath-
10-10-2010 Enigmes Mathématiques
05-12-2010 Enigmes Mathématiques
P2T
L'age de la mère par louloulepou
21-12-2011 Enigmes Mathématiques
P2T
Découpage d'un disque. par titoufred
18-09-2012 Enigmes Mathématiques
P2T
Architecte par juju59360
09-12-2013 Enigmes Mathématiques
P2T
Dés 7 par Vasimolo
13-07-2012 Enigmes Mathématiques
08-03-2008 Enigmes Mathématiques
P2T
Show 4 You - Part 3 par langelotdulac
15-12-2010 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