Exercice 2 — construction d'un jeu de cartes

Sujet

Manon et Julien veulent construire un jeu de cartes respectant les règles suivantes :

• \(\quad R_{1}\) : «Sur chaque carte sont dessinés \(n\) symboles différents »
• \(R_{2}\) : «Deux cartes distinctes ont toujours un et un seul symbole en commun»
• \(\quad R_{3}\) : «Aucun symbole n'est commun à toutes les cartes »
• \(\quad R_{4}\) : « Chaque symbole doit apparaître sur au moins deux cartes»

Pour jouer, on présente deux cartes et le premier qui identifie le symbole commun à ces deux cartes remporte le pli.

On appellera « carte 1 », « carte 2 », ..., « carte \(c\) » les \(c\) cartes constituant le jeu, et on notera « a », «b », « c », ... les différents symboles utilisés.

1. Pour commencer, ils envisagent de réaliser un jeu simplifié qui ne contient que 3 cartes.

Manon prétend qu'en dessinant 2 symboles sur chaque carte, 3 symboles différents en tout sont suffisants.
Proposer un tel jeu en donnant pour chaque carte les symboles qui y sont dessinés.
2. Ils veulent maintenant réaliser un jeu de 7 cartes, dans lequel chaque symbole n'est partagé que par une seule paire de cartes.
a. Justifier qu'une carte de ce jeu doit contenir 6 symboles.
b. Combien de symboles différents seront nécessaires ?
c. Avec 300 symboles différents, de combien de cartes le jeu aurait-il été constitué ?
3. N'étant pas satisfaits du résultat, ils tentent de construire un jeu de 7 cartes contenant chacune 3 symboles et rajoutent la règle suivante :
\(R_{5}\) : « Chaque symbole apparaît sur 3 cartes exactement»
Justifier qu'un tel jeu nécessite 7 symboles distincts.
4. Après plusieurs tentatives infructueuses, ils ont finalement réussi à réaliser un tel jeu à l'aide de l'algorithme suivant :

Pour i allant de 1 à 7 a
Pour j allant de 1 à 7
Si il y a déjà 3 « 1 » dans la ligne i
ou il y a déjà 3 « 1 » dans la colonne j,
ou il existe \(\mathrm{k}<\mathrm{i}\) et \(\mathrm{I}<\mathrm{j}\) tel que il y ait des « 1 » dans les cases \((\mathrm{k} ; \mathrm{j}),(\mathrm{k} ; \mathrm{I})\) et ( \(\mathrm{i} ; \mathrm{I}\) ).
Alors, écrire 0 dans la case (i ; j)
Sinon, écrire 1 dans la case (i ; j)

Fin Si-Sinon Fin Pour Fin pour permis de compléter un tableau à 7 lignes et 7 colonnes dans lequel une ligne correspond à une carte et une colonne à un symbole.
La case ( \(\mathrm{i} ; \mathrm{j}\) ) désigne la case située à l'intersection de la ligne i et de la colonne j.
a. Que signifie l'écriture d'un « 1 » dans la case ( \(\mathrm{i} ; \mathrm{j}\) ) ?