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 - 30-07-2018 17:16:38

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 878
Lieu: Seahaven island

qtockage intelligent

Hello les gens!

C'est le moment de sortir un peu ses neurones. Votre job c'est de stocker des objets!

Supposons un instant que je vous donne une bande de cases et que je vous demande de stocker des objets parmi 2 types, A et B, tout en stockant de manière continue sur cette bande les objets d'un même type. Une évidence arrive à l'esprit pour bien faire les choses: disposer un des types à un extrémité de la bande, l'autre de l'autre coté et remplir l'espace progressivement par les 2 bouts, au fur et à mesure des arrivées, pour finir optimalement avec la bande remplie à la fin avec tous les objets d'un type d'un coté et ceux du second type de l'autre.

http://www.prise2tete.fr/upload/Clydevil-StoragePNG.png

Et la ce qu'on va se demander, c'est comment se passent les choses avec plus de 2 types! On a qu'à dire des objets de uniquement 3 types: A B et C.

On vous file à la chaîne de tels objets et vous ignorez le nombre et l'ordre d'arrivée de chaque type: ça peut être uniquement des A ou une alternance de B et C par exemple.

Vous avez un espace de stockage, ie un ensemble de cases, certaines adjacentes entres elles (Un graphe quoi pour les intimes).
Une case stocke un objet et un seul, elle devient inutilisable après. Lorsqu'on stocke un objet on est obligé, si son type est déjà présent quelque part, de le stocker sur une case qui touche une case contenant un des ces précédents semblables. Ie l'espace de stockage dédié à un type en particulier est connexe à tout instant.

On considère que vous êtes bon, si, quelque soit l'ordre d’arrivée des objets, vous
ne pouvez plus suivre ces règles QUE dans le cas ou il n'y a plus du tout de place. C'est à dire que si votre espace n'est pas plein vous devez pouvoir accueillir des objets de n'importe quel type en leur assurant d’être voisins avec les objets du même type déjà présent.

Votre job est de concevoir, pour 3 types d'objets A, B et C:
- votre espace de stockage
- sa stratégie d'utilisation

Pour le moment il s'agit d'un problème assez ouvert alors il n'y a pas de restrictions, mais j'ai personnellement les préférences suivantes:

1) Quid d'un réseau de cases identiques pouvant être dessiné sur le plan (les voisins étant les cases qui se touchent) Y a t il un solution pour un nombre arbitrairement grand de cases au total?

2) Si 1 est impossible, quid d'un graphe planaire? (c'est moins contraignant car on peut déclarer voisin des cases pourtant physiquement très éloignées les unes des autres)

Et toute caractérisation intéressante est la bien venue!

Bonne chance!



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 31-07-2018 18:09:06

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1577

Stockage intellignet

Constat #1: la dernière case doit être connexe aux 3 catégories, puis qu’aléatoirement on va avoir ensuite A ou B ou C et que les trois doivent convenir.

Constat #2, dit « le chat noir »: à la différence du cas à deux types, où la distance se réduit mathématiquement à chaque objet ajouté quel qu’il soit, là les catégories B et C peuvent rester inchangées au profit de A si on a le malheur de ne piocher que ça.
Du coup, pour pouvoir valider le constat #1, il faudrait démarrer les rangements en plaçant les premiers éléments « assez proches »  les uns des autres. L’essentiel étant qu’a tout moment (y compris au début), il y ait une case qui valide le #1

Fort de ces remarques, je m’en vais réfléchir smile

 #3 - 31-07-2018 20:28:33

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1577

Sotckage intelligent

De manière plus générale, on peut dire que:
- la partie vide n'est pas forcément espace connexe
- mais si on la découpe en espaces connexes, alors chacun d'eux est connexe aux 3 catégories.

Démonstration: si une partie n'est pas connexe à un élément, disons A, et qu'on ne tire que des A, on sera bien embêté. Ca c'est pour la 2nde partie.

Pour la première, on verra pour trois catégories, mais pour deux ça marche, et c'est assez peu intuitif. Par exemple, on a un cercle de stockage, on commence A et B où on veut (donc deux zones vides en général), et rien qu'en plaçant les objets à côté d'un de leur pairs alors on fera un bon remplissage.

Du coup, pour un espace de stockage plan, aucune catégorie ne peut séparer le plan en deux paries non vides, sauf éventuellement sur le dernier objet

 #4 - 01-08-2018 10:07:13

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 878
Lieu: Seahaven island

syockage intelligent

@scarta: très bonnes remarques et caractéristiques smile le schmilblick avance

 #5 - 03-08-2018 10:40:08

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 878
Lieu: Seahaven island

stockage intrlligent

@Tous le monde: Une sous question plus empiriquement abordable: trouver le graphe planaire le plus gros possible qui satisfait la condition.

Quelques éléments de réponse perso
(similaire à des idées de @scarta):

i)A un moment donné, un chemin parmi les plus courts, d'au moins une case vide, reliant 2 zones de couleurs différentes, doit faire maximum une case. (et donc exactement une case) Autrement dit: pour 2 zones de couleur différente il y a toujours une case libre qui doit être voisine commune de 2.
Démo: si ce chemin dans la partie libre était de N cases avec N>1 alors il suffirait de jouer l'autre couleur que les 2 en question jusqu’à avoir au total N-1 cases libres et du coup une partie (qui est non nulle) de ces N-1 cases libres serait inaccessible à une des deux couleurs.

ii)
Toute sous partie connexe et vide du graphe doit être relié au reste par au minimum 3 de ses nœuds. 
Démo: sinon il suffit de jouer couleur A jusqu’à ce qu'on remplisse un nœud de cette partie puis de jouer couleur B jusqu’à ce qu'on remplisse un autre nœud de cette partie (si c'est possible) et du coup on viendrait d'isoler l’intérieur de cette partie a la 3eme couleur C.

 

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 : Pim, Pam et ?

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