Problema di logica dalla prova INdAM 2017/2018
Come scrivevo proprio ieri rispondendo al mio thread su un interessante Problema di geometria dalla prova INdAM 2017/2018, di questa mi rimane l'ultima dimostrazione da completare definitivamente. Vi riporto il testo del problema:
"Un mazzo è formato da un numero di $N$ di carte. Su ciascuna carta sono presenti $8$ diversi simboli. Si sa che, prendendo una qualsiasi coppia di carte dal mazzo, esse hanno esattamente un simbolo in comune. Tuttavia, non esiste un simbolo che sia presente in tutte le carte.
(a) Dimostrare che nessun simbolo può essere presente in più di $8$ carte.
(b) Dimostrare che $N\leq57$.
(c) Dimostrare che i simboli complessivamente utilizzati sono almeno $N$.
(d) Dimostrare che, se $N\geq50$, allora i simboli utilizzati sono complessivamente $57$."
Sono riuscito a fare senza troppi problemi (credo) i punti (a) e (b) ma agli ultimi due non riesco proprio a trovare una soluzione. Vorrei quindi chiedervi se la mia dimostrazione dei primi due punti è valida e se riuscite a trovare una soluzione agli ultimi che mi sfuggono.
Scrivo qui sotto la soluzione del punto (a)
Qui la soluzione al punto (b)
Qui mi sono bloccato, anche se sono riuscito a trovare qualcosa di interessante circa il punto (c), anche se non direttamente utile per la dimostrazione definitiva... Ho notato che se $3\leqN\leq9$, per il numero di simboli vale $S\geq \frac{(17-N)N}2>N$: questo limite minimo l'ho ottenuto costruendo carte "riciclando" i simboli non ancora condivisi con quelle precedenti. Vi riporto uno schemino di questa situazione
Ho tentato di estendere questo ragionamento ma non funziona oltre le nove carte e per quanto sono sicuro che sia una mezza cavolata, ancora non trovo la risoluzione finale per (c) e tantomeno per (d)... Avete qualche idea in merito?
"Un mazzo è formato da un numero di $N$ di carte. Su ciascuna carta sono presenti $8$ diversi simboli. Si sa che, prendendo una qualsiasi coppia di carte dal mazzo, esse hanno esattamente un simbolo in comune. Tuttavia, non esiste un simbolo che sia presente in tutte le carte.
(a) Dimostrare che nessun simbolo può essere presente in più di $8$ carte.
(b) Dimostrare che $N\leq57$.
(c) Dimostrare che i simboli complessivamente utilizzati sono almeno $N$.
(d) Dimostrare che, se $N\geq50$, allora i simboli utilizzati sono complessivamente $57$."
Sono riuscito a fare senza troppi problemi (credo) i punti (a) e (b) ma agli ultimi due non riesco proprio a trovare una soluzione. Vorrei quindi chiedervi se la mia dimostrazione dei primi due punti è valida e se riuscite a trovare una soluzione agli ultimi che mi sfuggono.
Scrivo qui sotto la soluzione del punto (a)
Qui la soluzione al punto (b)
Qui mi sono bloccato, anche se sono riuscito a trovare qualcosa di interessante circa il punto (c), anche se non direttamente utile per la dimostrazione definitiva... Ho notato che se $3\leqN\leq9$, per il numero di simboli vale $S\geq \frac{(17-N)N}2>N$: questo limite minimo l'ho ottenuto costruendo carte "riciclando" i simboli non ancora condivisi con quelle precedenti. Vi riporto uno schemino di questa situazione
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 |
| 15 | 16 | 17 | 18 | 19 | 20 | 2 | 9 |
| 21 | 22 | 23 | 24 | 25 | 3 | 10 | 16 |
| 26 | 27 | 28 | 29 | 4 | 11 | 17 | 22 |
| 30 | 31 | 32 | 5 | 12 | 18 | 23 | 27 |
| 33 | 34 | 6 | 13 | 19 | 24 | 28 | 31 |
| 35 | 7 | 14 | 20 | 25 | 29 | 32 | 34 |
Ho tentato di estendere questo ragionamento ma non funziona oltre le nove carte e per quanto sono sicuro che sia una mezza cavolata, ancora non trovo la risoluzione finale per (c) e tantomeno per (d)... Avete qualche idea in merito?
Risposte
Sia $q\ge 1$. Sia $S$ un insieme di 'punti’ e sia $R$ una famiglia di 'rette’ con le seguenti proprieta’:
-- Ogni retta in $R$ consiste in $q+1$ punti di $S$.
-- Nessun punto sta su tutte le rette.
-- Due rette distinte hanno esattamente un punto di intersezione.
L’ultima condizione implica che per ogni due punti distinti in $S$ c’e’ al massimo
una retta in $R$ passante per entrambi, ma non e’ detto che la retta esiste.
Se prendiamo $q=7$ e se invece di 'retta’ leggiamo 'carta’ e invece di 'punto’ leggiamo 'simbolo’,
ritroviamo il problema dell’INDAM. L’insieme dei 'simboli complessivamente usati’
e’ il nostro insieme $S$ di punti. Usiamo la stessa notazione e scriviamo $N$ per $\#R$.
(a) Dimostrare che il numero di rette in $R$ passanti per un punto di $S$ e’ $\le q+1$.
(b) Dimostrare che $N\le q^2+q+1$.
(c) Dimostrare che $\#S\ge N$.
(d) Dimostrare che se $N\ge q^2+1$, allora $\#S=q^2+q+1$.
Dimostrazione:
(a) Sia $P$ un punto e sia $\Phi_P$ il fascio delle rette in $R$ passanti per $P$.
Sia $m=\#\Phi_P$. Per ipotesi esiste una retta $r\in R$ che non passa per $P$.
Questa retta $r$ ha $m$ punti di intersezione distinti con le rette in $\Phi_P$.
Poiche’ $r$ ha $q+1$ punti, abbiamo che $m\le q+1$.
(b) Scegliamo una retta $r\in R$. Allora ogni retta in $R$ diversa da $r$ ha un punto
di intersezione $P$ con $r$ e appartiene quindi a $\Phi_P$. Poiche’ $r$ ha $q+1$ punti,
per la parte (a), ci sono $\le 1 +(q+1)q$ rette. (Notare che $r\in \Phi_P$ per ogni $P\in r$).
(c) Consideriamo l’insieme $W=\{(P,r)\in S\times R:\ \ P\in r\}$.
Poiche’ ogni retta ha $q+1$ punti, la cardinalita’ di $W$ e’ $N(q+1)$.
Per la parte (a), per un punto passano $\le q+1$ rette.
La cardinalita’ di $W$ e’ quindi anche $\le \#S(q+1)$. Ne segue che $\#S\ge N$.
(d) Sia $r$ una retta. Poiche’ ogni retta ha un punto di intersezione con $r$,
l’unione $\cup_{P\in r}\Phi_P$ e’ l’insieme di tutte le rette in $R$.
Per la parte (a) sappiamo che $\#\Phi_P\le q+1$ per ogni $P\in r$.
Osserviamo che c’e’ almeno un punto $P\in r$ con $\#\Phi_P$ uguale a $q+1$.
Infatti se non fosse cosi’, allora $\cup_{P\in r}\Phi_P$ conterebbe
$\le 1 +(q+1)(q-1)=q^2$ rette, contraddicendo l’ipotesi che $N\ge q^2+1$.
Ora, sia $r$ una retta e $P\in r$ un punto con $\#\Phi_P=q+1$. Ci sono esattamente
$1 +(q+1)q$ punti sull’unione delle rette in $\Phi_P$. Affermiamo che ogni punto
in $S$ sta su una delle rette in $\Phi_P$ e quindi $\#S=q^2+q+1$, come richiesto.
Infatti, se $Q\in S$ non appartenesse a nessuna retta in $\Phi_P$, consideriamo una
retta $r$ passante per $Q$. Allora $r\notin \Phi_P$ e quindi $r$ ha un unico punto di
intersezione con ogni retta in $\Phi_p$. Poiche’ ci sono $q+1$ rette in $\Phi_P$, ci sono
$q+1$ punti di intersezione distinti. Siccome $r$ ha esattamente $q+1$ punti,
per forza $Q$ e’ uno dei punti di intersezione. E quindi $Q$ sta su una retta di $\Phi_P$.
Contraddizione.
---------
Sia $F_q$ un campo di $q$ elementi.
Allora un esempio di questa struttura combinatorica e’ una qualsiasi famiglia $R$
di rette nel piano proiettivo $P_2(F_q)$. L’insieme $S$ consiste nei punti sulle rette in $R$.
L’unica condizione e’ che le rette non passano tutte per lo stesso punto.
Notiamo che $\#P_2(F_q)=q^2+q+1$ e che $N\le q^2+q+1$.
-- Ogni retta in $R$ consiste in $q+1$ punti di $S$.
-- Nessun punto sta su tutte le rette.
-- Due rette distinte hanno esattamente un punto di intersezione.
L’ultima condizione implica che per ogni due punti distinti in $S$ c’e’ al massimo
una retta in $R$ passante per entrambi, ma non e’ detto che la retta esiste.
Se prendiamo $q=7$ e se invece di 'retta’ leggiamo 'carta’ e invece di 'punto’ leggiamo 'simbolo’,
ritroviamo il problema dell’INDAM. L’insieme dei 'simboli complessivamente usati’
e’ il nostro insieme $S$ di punti. Usiamo la stessa notazione e scriviamo $N$ per $\#R$.
(a) Dimostrare che il numero di rette in $R$ passanti per un punto di $S$ e’ $\le q+1$.
(b) Dimostrare che $N\le q^2+q+1$.
(c) Dimostrare che $\#S\ge N$.
(d) Dimostrare che se $N\ge q^2+1$, allora $\#S=q^2+q+1$.
Dimostrazione:
(a) Sia $P$ un punto e sia $\Phi_P$ il fascio delle rette in $R$ passanti per $P$.
Sia $m=\#\Phi_P$. Per ipotesi esiste una retta $r\in R$ che non passa per $P$.
Questa retta $r$ ha $m$ punti di intersezione distinti con le rette in $\Phi_P$.
Poiche’ $r$ ha $q+1$ punti, abbiamo che $m\le q+1$.
(b) Scegliamo una retta $r\in R$. Allora ogni retta in $R$ diversa da $r$ ha un punto
di intersezione $P$ con $r$ e appartiene quindi a $\Phi_P$. Poiche’ $r$ ha $q+1$ punti,
per la parte (a), ci sono $\le 1 +(q+1)q$ rette. (Notare che $r\in \Phi_P$ per ogni $P\in r$).
(c) Consideriamo l’insieme $W=\{(P,r)\in S\times R:\ \ P\in r\}$.
Poiche’ ogni retta ha $q+1$ punti, la cardinalita’ di $W$ e’ $N(q+1)$.
Per la parte (a), per un punto passano $\le q+1$ rette.
La cardinalita’ di $W$ e’ quindi anche $\le \#S(q+1)$. Ne segue che $\#S\ge N$.
(d) Sia $r$ una retta. Poiche’ ogni retta ha un punto di intersezione con $r$,
l’unione $\cup_{P\in r}\Phi_P$ e’ l’insieme di tutte le rette in $R$.
Per la parte (a) sappiamo che $\#\Phi_P\le q+1$ per ogni $P\in r$.
Osserviamo che c’e’ almeno un punto $P\in r$ con $\#\Phi_P$ uguale a $q+1$.
Infatti se non fosse cosi’, allora $\cup_{P\in r}\Phi_P$ conterebbe
$\le 1 +(q+1)(q-1)=q^2$ rette, contraddicendo l’ipotesi che $N\ge q^2+1$.
Ora, sia $r$ una retta e $P\in r$ un punto con $\#\Phi_P=q+1$. Ci sono esattamente
$1 +(q+1)q$ punti sull’unione delle rette in $\Phi_P$. Affermiamo che ogni punto
in $S$ sta su una delle rette in $\Phi_P$ e quindi $\#S=q^2+q+1$, come richiesto.
Infatti, se $Q\in S$ non appartenesse a nessuna retta in $\Phi_P$, consideriamo una
retta $r$ passante per $Q$. Allora $r\notin \Phi_P$ e quindi $r$ ha un unico punto di
intersezione con ogni retta in $\Phi_p$. Poiche’ ci sono $q+1$ rette in $\Phi_P$, ci sono
$q+1$ punti di intersezione distinti. Siccome $r$ ha esattamente $q+1$ punti,
per forza $Q$ e’ uno dei punti di intersezione. E quindi $Q$ sta su una retta di $\Phi_P$.
Contraddizione.
---------
Sia $F_q$ un campo di $q$ elementi.
Allora un esempio di questa struttura combinatorica e’ una qualsiasi famiglia $R$
di rette nel piano proiettivo $P_2(F_q)$. L’insieme $S$ consiste nei punti sulle rette in $R$.
L’unica condizione e’ che le rette non passano tutte per lo stesso punto.
Notiamo che $\#P_2(F_q)=q^2+q+1$ e che $N\le q^2+q+1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo