Serrature e chiavi

[giapippa]

La Scuola Superiore Sant’Anna custodisce con estrema cura
in una cassaforte gli elaborati dei concorsi di ammissione. Per
motivi di sicurezza la Direzione ha deciso di dotare la
cassaforte di un certo numero di serrature e 4 impiegati
custodiscono ciascuno un certo numero di chiavi.
Qual è il numero minimo di serrature di cui deve essere
dotata la cassaforte affinché per la sua apertura sia
necessaria e sufficiente la presenza di 3 impiegati?

Non ho capito molto sto problema (gli impiegati possono avere dei doppioni tra loro?) però mi è venuta l'intuizione così senza pensarci troppo... 2 serrature? (se ogni impiegato ha almeno una chiave allora 2 saranno necessariamente uguali)

[Iceman93]

Mi permetto di intervenire... il problema si fonda su quel "necessaria e sufficiente" che compare all'ultimo rigo.
Se fosse 2, certamente la presenza di 3 impiegati non sarebbe quantomeno necessaria: basterebbero infatti al più 2 impiegati, ammesso che qualche impiegato abbia la chiave della serratura A e qualche impiegato quella della serratura B.
Ci penso un po', ma sono convinto che 2 non sia la risposta esatta.
PS. è chiaro che gli impiegati debbano avere dei doppioni tra di loro: se tra di loro circolasse una copia di ogni chiave, sarebbe necessaria la presenza di tutti e quattro.

[giapippa]

se sono 2 non c'è la possibilità che abbiano entrambi la stessa chiave no? Fammi sapere che ti viene in mente

[Iceman93]

Se le serrature sono due, le chiamiamo A e B (A e B sono anche i nomi delle chiavi corrispondenti, non fa differenza parlare di chiavi o serrature).
Ora, il testo dice che ciascuno custodisce un certo numero (diverso da 0) di chiavi: quindi ciascuno dei quattro guardiani custodisce o una o due chiavi.
Se uno di quei 4 custodisse entrambe le chiavi, sarebbe lui solo sufficiente ad aprire la cassaforte: ciò va contro la richiesta del problema.
Dunque, con 2 serrature, ogni guardiano custodisce una sola chiave.
Il testo ci dice che devono essere sufficienti 3 guardiani per aprire le porte: dunque non può accadere che tutti i guardiani abbiano solo la chiave A e nessuno la chiave B, e viceversa. Dunque un certo numero di impiegati ha la chiave A, e un certo numero la chiave B.
Detto ciò, è ovvio che possono essere sufficienti due guardiani, uno con la chiave A e uno con la B, per aprire la cassaforte.
La risposta dunque non è 2.

In realtà il problema non è proprio di immediata risoluzione... se ho capito bene la traccia, si deve fare in modo che siano necessari e sufficienti 3 guardiani qualsiasi, non 3 guardiani da noi opportunamente scelti. Questo però deve valere sempre, mentre nel caso in cui le serrature sono 2 capita che i guardiani sufficienti siano 2.

[petroliopg]

3 impiegati sono necessari. Dunque scelti due impiegati a caso, ci sarà almeno una serratura la cui chiave non appartiene ad ambi gli impiegati, ma che necessariamente appartiene ad entrambi gli altri due impiegati. Dunque le serrature totali sono tutte le combinazioni secondo cui è possibile scegliere i due impiegati a cui è impossibile da soli aprire le serrature, tra i 4 a disposizione. Le serrature sono dunque $\displaystyle S=C_2^4= \binom{4}{2}= 6$

Bonus 1: quante chiavi può avere al massimo un impiegato
Bonus 2: generalizzare il numero minimo di serrature ed il numero massimo di chiavi per impiegato sapendo che $\ n$ sono gli impiegati totali e $\ k$ sono gli impiegati necessari e sufficienti.

[Iceman93]

Ci credi che mi accingevo a scrivere che la soluzione era 6? XD

[Iceman93]

Onestamente stavo generalizzando il medesimo ragionamento, dopo aver riempito "a mano" la seguente tabella, avente le lettere dei guardiani e i numeri delle chiavi:
A B C D
1 1 2 3
2 4 4 5
3 5 6 6
che poi è la trasformazione nella pratica di ciò che hai detto tu, petroliopg.