Multipli di 5

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Qual'è la cardinalità minimale in modo tale che comunque scelto un sottoinsieme di \( \mathbb{N} \), di tale cardinalità, contenga sicuramente almeno 5 numeri che sommati danno un multiplo di 5.

[gio73]

9

[axpgn]

@gio73

Come ci sei riuscita? Finora non sono riuscito a "smontarlo"

Otto non sono sufficienti, vedi per esempio $5, 10, 15, 20, 1, 6, 11, 16$

Pensavo ne occorresse qualcuno in più …

Cordialmente, Alex

[gio73]

@alex
Aspettiamo Conferme o smentite

ho considerato solo le cifre delle unità e ho fatto dei tentativi, tra l altro ti bastano 01234, perché poi la situazione si ripete.

[axpgn]

@gio73

… mmm … non la vedo così facile, la casistica è decisamente GRANDE
Anch'io son partito dai resti e da quelli si stabilisce velocemente un "upper bound" di $20$ dato che non possono esserci più di quattro occorrenze per ogni resto e un "lower bound" di $8$ dato che con quattro $0$ e quattro $1$ (come resti intendo) non puoi ottenere un multiplo di cinque.
Però, poi, un modo "semplice" di dimostrare che quella è la soluzione non l'ho ancora trovato (anche se facendo diversi conti non ho trovato un controesempio).

[gio73]

@alex

proviamo così
Notiamo che la massima variabilità ce l abbiamo con coppie di resti uguali e un singoletto. Quel caso soddisfa la richiesta di 5 numeri somma 5. Sempre quale che sia il singoletto. Ok?
Passiamo alle triplette?
Anche qui tre triplette Cmq prese soddisfano il caso.
2 triplette e altri liberi? Avanzano 3 posti e 3 numeri. O tutti diversi e si continua a verificare il caso. O mettendo una coppia ne devi escludere 1. Anche qui però quale escludi per evitare il caso?
Le quaterne si verificano più velocemente.

[axpgn]

@gio73

Infatti son partito dalle quaterne
La tua "schematizzazione" è più efficiente della mia però mi sono accorto che, comunque, rimane sempre un po' di lavoro da fare, infatti mi sono stufato prima di arrivare in fondo

Cordialmente, Alex

[gio73]

perchè un po' di lavoro da fare?
Devi solo verificare i casi che potrebbero verosimilmente negare la congettura iniziale.

[axpgn]

Non sono così pochi come credevo ... mi sono stufato presto, sarà il caldo

[gio73]

aspetto sempre conferme (o smentite) da parte di shivering

[axpgn]

Di chi?

Io comunque son convinto dal primo momento che l'ho vista (la tua risposta) che sia giusta

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"gio73":

9

Corretto!
Come dice axpgn i casi non sono pochissimi ragionando in combinatoria. Io ho ragionato in modo "geometrico" diminuendo i casi a 2. In questo modo
Ho modificato perché c'era un imprecisione nel caso con 3 classi. Desolato.
Attenzione soluzione:

Costruiamo un cerchio ed iscriviamoci un pentagono regolare, e partendo da un vertice qualunque in senso orario numeriamo i vertici nel seguente ordine: 0,1,2,3,4. I vertici rappresentano dunque le classi di congruenze del 5. Tracciamo anche gli assi di simmetria che lasciano invariato il pentagono e passanti per un vertice. Abbiamo 5 simmetrie e 5 assi. Un asse passa per un vertice e per il centro del lato opposto al vertice, prolunghiamo il segmento per arrivare sulla circonferenza.
Bene.
Proprietà 1) Si può facilmente verficare che data una coppia di numeri distinti la somma di essi è congrua alla somma di una coppia di numeri che giace sul vertice il cui asse di simmetria rende i numeri della coppia uno il simmetrico dell'altro.
Ad esempio prendiamo il (2,3), sommati danno 5 che è congruo a 0. Prendiamo (0,3), sommati danno 3. 0 è simmetrico a 3 se l'asse di simmetria passa per 4. E verifichiamo che 4+4=8 che è congruo a 3.
Vale il viceversa.
Proprietà 2) Data una coppia di numeri uguali la loro somma è congrua alla somma dei numeri delle coppie di cui uno è il simmetrico dell'altro rispetto all asse di simmetria che passa dal vertice passante per il numero che forma la coppia uguale. Ad esempio 1+1 = 2+0 = 3 + 4.
Diremo dunque che una coppia di numeri \( (a,b) \sim (c,d) \) se e solo se $a+b \equiv c+d \mod 5 $
È facile verificare che è una relazione di equivalenza.
-Supponiamo che per formare il nostro insieme dobbiamo utilizzare tutte e 5 le classi di congruenza, è immediato verificare che dati 5 numeri qualunque in modo che c'è almeno un numero per ognuno delle 5 classi, la loro somma è un multiplo di 5.
-Supponiamo che per formare il nostro insieme dobbiamo utilizzare esclusivamente 1 sola classe di congruenza, è immediato verificare che dati 5 numeri qualunque appartenenti a questa classe, la loro somma è un multiplo di 5.
-Supponiamo che per formare il nostro insieme dobbiamo utilizzare esclusivamente 2 classi di congreunza, è immediato verificare che dati 9 numeri qualunque appartenenti a queste due classi, in modo tale che ve ne sia almeno uno appartenete a ciascuna delle due classi, la loro somma è un multiplo di 5.

Più delicato il caso se dobbimo utilizzare esclusivamente 3 o 4 classi di congruenza.
Caso 1) Partiamo dal caso di 3 classi di congruenza. Mostriamo che con 3 classi di equivalenza e un insieme $A$ di cardinalità 9, in modo tale che in $A$ possiamo trovare almeno un elemento per ognuna delle 3 classi, allora possiamo sempre trovare 5 numeri che sommati danno un multiplo di 5.
Siano $\bar{a}, \bar{b}, \bar{c} $ le tre classi in questione.
Dal momento che abbiamo tre classi di equivalenza le tre classi formano un triangolo (isoscele) i cui vertici appartengono al pentagono. Supponiamo senza perdità di generalità che $\bar{c} $ è il vertice da cui partono i due lati di lunghezza uguale. Abbiamo che $\bar{a} $ è il simmetrico di $\bar{b} $ (e viceversa) rispetto all'asse di simmetria passante per $\bar{c}$. Chiamiamo con $ n_a, n_b, n_c$ la cardinalità degli elementi che appartengono sia ad $A$ e rispettivamente sia alla classe di equivalenza $\bar{a}, \bar{b}, \bar{c} $.
Risulta chiaro che se $n_i \geq 5$ per almeno un $i \in \{ a,b,c\} $ allora possiamo trovare 5 numeri che sommati danno un multiplo di 5.
Consideriamo dunque che $\forall i \in \{ a,b,c\} $ abbiamo $1 \leq n_i \leq 4$. Comunque ordiniamo questi nove numeri sui vertici del triangolo. Le terne di numeri che sommati danno 9 che soddisfano quanto appena detto sono $(1,4,4), (2,3,4),(3,3,3)$.
Se \( n_c = \max\limits_{i \in \{a,b,c \} } n_i \) allora
Per le proprietà 1) e 2) possiamo trovare almeno una coppia di numeri $(\alpha, \beta)$ in modo tale che \( (\alpha, \beta) \sim ( \gamma, \xi) \) con $ \gamma, \xi \in \bar{c} $.
Se \( n_c < \max\limits_{i \in \{a,b,c \} } n_i \) allora abbiamo solo 3 casi possibili (a meno di simmetrie).
1.1) $ n_c = 1$, $n_a=n_b=4$
1.2) $n_c= 2$, $n_a=3$ e $n_b=4$
1.3) $n_c=3$, $n_a=2$ e $n_b=4$
Nel caso 1) trasformiamo le 4 coppie di \( (\alpha_i, \beta_i) \), con \( \alpha_i \in \bar{a}, \beta_i \in \bar{b} \) per ogni $i=1,2,3,4$ in una coppia congruente \( (\alpha_i, \beta_i) \sim (\gamma_i, \gamma_i) \) con \( \gamma_i \in \bar{c} \) per ogni \( i=1,2,3,4 \).
Nel caso 2) trasformiamo due coppie di \( (\alpha_i, \beta_i) \), con \( \alpha_i \in \bar{a}, \beta_i \in \bar{b} \) per ogni $i=1,2$ in due coppie congruenti \( (\alpha_i, \beta_i) \sim (\gamma_i, \gamma_i) \) con \( \gamma_i \in \bar{c} \) per ogni \( i=1,2 \).
Nel caso 3) trasformiamo una coppie di \( (\alpha, \beta) \), con \( \alpha \in \bar{a}, \beta \in \bar{b} \) in una coppia congruente \( (\alpha, \beta) \sim (\gamma, \gamma) \) con \( \gamma \in \bar{c} \).

Pertanto possiamo sempre trovare 5 numeri la cui somma è un multiplo di 5.

Caso 2) Passiamo al caso di 4 classi di congruenza. Mostriamo che con 4 classi di equivalenza e un insieme $A$ di cardinalità 9, in modo tale che in $A$ possiamo trovare almeno un elemento per ognuna delle 4 classi, allora possiamo sempre trovare 5 numeri che sommati danno un multiplo di 5.
Siano $\bar{a}, \bar{b}, \bar{c}, \bar{d} $ le quattro classi in questione.
Dal momento che abbiamo quattro classi di equivalenza i vertici associati alle classi formano un trapezio regolare i cui vertici appartengono al pentagono. Chiamiamo con $ n_a, n_b, n_c, n_d$ la cardinalità degli elementi che appartengono sia ad $A$ e rispettivamente sia alla classe di equivalenza $\bar{a}, \bar{b}, \bar{c}, \bar{d} $.
Risulta chiaro che se $n_i \geq 5$ per almeno un $i \in \{ a,b,c,d\} $ allora possiamo trovare 5 numeri che sommati danno un multiplo di 5.
Consideriamo dunque che $\forall i \in \{ a,b,c,d\} $ abbiamo $1 \leq n_i \leq 4$. Le quaterne di numeri che sommati danno 9 che soddisfano quanto appena detto sono $ (1,1,3,4), (1,2,2,4), (1,2,3,3), (2,2,2,3)$.
Supponiamo senza perdità di generalità che il trapezio formato dai vertici $\bar{a}, \bar{b}, \bar{c}, \bar{d} $, sia in modo tale che la lunghezza dei lati $\bar{a}\bar{b} = \bar{b}\bar{c}=\bar{c}\bar{a}$ e inoltre $\bar{a}\bar{b}$ è parallelo al segmento $\bar{c}\bar{d}$. Con la lunghezza dei lati $\bar{a}\bar{b}< \bar{c}\bar{d}$.
Abbiamo dunque che:
- $\bar{a}$ è il simmetrico di $\bar{d}$ (e viceversa) rispetto all'asse passante per $\bar{c}$.
- $\bar{b}$ è il simmetrico di $\bar{c}$ (e viceversa) rispetto all'asse passante per $\bar{d}$.
- $\bar{a}$ è il simmetrico di $\bar{c}$ (e viceversa) rispetto all'asse passante per $\bar{b}$.
- $\bar{b}$ è il simmetrico di $\bar{d}$ (e viceversa) rispetto all'asse passante per $\bar{a}$.
Per le proprietà 1) e 2) possiamo trovare al più $k$ coppie di numeri $(\alpha_1, \beta_1); \ldots; (\alpha_k,\beta_k)$ in modo tale che \( k:= \min\limits_{i \in \{a,b,c,d \} } n_i \leq 2 \) e $\alpha_j \in \bar{k}$ e $\beta_j$ è il simmetrico di $\alpha_j$ rispetto ad un asse passante per uno dei quattro vertici del trapezio, diciamo $\bar{m}$; in modo tale che \( (\alpha_j, \beta_j) \sim ( \gamma_j, \xi_j) \) con $ \gamma_j, \xi_j \in \bar{m} $ per tutti $j=1,\ldots, k$
In modo tale da ricondurci al caso con 3 classi di congruenze.
Pertanto possiamo sempre trovare 5 numeri la cui somma è un multiplo di 5.
C.V.D.

[axpgn]

Bello, notevole

Mi rimane però il dubbio che anche facendo i conti non ci si metteva molto di più

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":Bello, notevole

Mi rimane però il dubbio che anche facendo i conti non ci si metteva molto di più

Si molto bello, mi è piaciuto un sacco da risolvere questo indovinello!
Non ho idea di quanto ci si metteva con i conti, non mi piacciono troppo i conti
Stavo provando ora a riflettere se era generalizzabile sostituendo al 5 un qualunque numero primo. Chiaramente cambia anche la cardinalità minimale.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Non sono sicuro minimamente, anche perché ad un certo punto è diventato un po' lunghino. Ma credo che con il $7$ funzioni.
Rammento il problema: trovare la cardinalità minimale in modo tale che comunque si scegli un sottoinsieme dei numeri naturali si abbia la certezza di trovare almeno $7$ numeri la cui somma è un multiplo di $7$.

In modo analogo al problema con il $5$ abbiamo le stesse proprietà, stavolta però iscriviamo un ettagono.
Come prima diremo che due coppie di numeri sono congruenti \( (a,b) \sim_7 (c,d) \) se e solo se \( a+b \equiv c+d \mod 7 \)
-Con elementi esclusivamente di 1 classe abbiamo che un qualunque insieme di 7 elementi da come somma un multiplo di 7
- Se nell'insieme ci sono elementi di ogni classe, abbiamo che un qualunque insieme di 7 elementi da come somma un multiplo di 7.
- Se nell'insieme ci sono elementi di 2 classi, abbiamo che un qualunque insieme di 13 elementi da come somma un multiplo di 7.

Caso 1)
Consideriamo un insieme $A$ i cui vi sono elementi di sole 3 classi. Denotiamo le classi $ a,b,c$ (non ho voglia di fare il \bar{}) e come prima $n_a,n_b,n_c$ rispettivamente la cardinalità degli insiemi $A \cap a$, $A \cap b$, $A \cap c$.
Per delle ragioni analoghe a prima consideriamo solamente $ 1 \leq n_j \leq 6$, per tutti i $j = \{a,b,c \}$. Sia $ (n_1,n_2,n_3)$ una terna di 13, che soddisfi le condizioni. Abbiamo che le terne possibili sono $(6,6,1),(6,5,2),(6,4,3),(5,5,3),(5,4,4) $. Supponiamo formino un triangolo isoscele. Siccome \[ \lfloor \frac{n_{\sigma(1)}+ n_{\sigma(2)}}{2}\rfloor + n_{\sigma(3)} \geq 7 \] per tutti i $ \sigma \in S_3 $ e per tutte le terne elencate abbiamo che è sempre possibile formare un nuovo insieme $A'$ sostiuendo un numero sufficiente di coppie di elementi di $A$ con lo stesso numero di coppie congruente, in modo tale che $A'$ contenga almeno 7 numeri appartenenti di una stessa classe di equivalenza.
Se i vertici che corrispondono alle classi di equivalenza non formano un triangolo isoscele allora se esistono $n_a = n_b$ gli scegliamo per formare delle coppie congruenti in modo che otteniamo un insieme di $A'$ i cui elementi appartengono a 2 classi, la classe $c$ e la classe $d$ che corrisponde al vertice in cui passa l'asse di simmetria che rende $a$ il simmetrico di $b$ ed abbiamo terminato in quanto $ 2n_a \geq 7 $. Se non esistono $n_a=n_b$. Scegliamo $n_a$ ed $n_b$ in modo tale che $n_a > n_b > n_c$ in questo siamo certi che possiamo formare un insieme di cardinalità 3, che denoterò con $A''$ formato da elementi esclusivamente delle classi $a,c,d$ dove $d$ è la classe corrispondente al vertice in cui passa l'asse di simmetria che rende $a$ il simmetrico di $b$. E $d\geq 7$ per tutte le terne di 13 con queste carratteristiche.

Siamo dunque certi che possiamo trovare 7 numeri che sommati diano un multiplo di 7.

Caso 2) Un insieme $A$ di cardinalità 13 i cui elementi appartengono a 4 classi di congruenze denotate $a,b,c,d$. Abbiamo per tutte le quaterne di 13 $(n_1,n_2,n_3,n_4)$ in cui esistono $i,j \in \{ 1,2,3,4 \} $ tale che $n_i = n_j $ abbiamo già terminato. Poiché si $A$ si trasforma in un insieme $A'$ i cui elementi appartengono a 3 classi di equivalenza e ci siamo ricondotti al caso 1).
Se questi $i,j$ non esistono le uniche quaterne da controllare sono $(6,4,2,1),(5,4,3,1)$.
Abbiamo che i trapezi che si possono formare all'interno di un ettagono sono di 3 tipi.
-Tipo 1) di vertici "successivi", ad esempio il trapezio di vertice "6,2,1,0"
-Tipo 2) un trapezio i cui due coppie di vertici sono formati da vertici successivi, ad esempio il trapezio formato dai vartici "5,2,1,6"
-Tipo 3) da ultimo un trapezio in cui una sola coppia di vertici è formata da vertici successivi, ad esempio di vertici "6,1,3,4".
Chiamiamo il trapezio $T_A$ formato dai vertici $a,b,c,d$ ordinati in questo modo, abbiamo che
- se $T_A$ è un trapezio di tipo 1) allora \( (a,c) \sim_7 (d,d) \) e \( (b,d) \sim_7 (c,c) \)
- se $T_A$ è di tipo 2) allora \( (a,d) \sim_7 (b,b) \) e \( (b,c) \sim_7 (a,a) \)
- se $T_A$ è di tipo 3) allora \( (a,c) \sim_7 (d,d) \) e \( (b,d) \sim_7 (c,c) \)

Possiamo direttamente concludere che è sempre possibile formare trasformare l'insieme $A$ in un insieme $A'$ in modo tale che che $A'$ contenga almeno $7$ elementi appartenenti alla stessa classe di equivalenza.
Il caso 2) è dimostrato.

Qui ho più o meno smesso perché non avevo più voglia di cercare le quinterne o le 6-uple di 13.
Caso 3) Cardinalità di $A$ uguale a 13 ed elementi di 5 classi. Per tutte le quinterne di 13 che possiedono almeno due numeri uguali o che possiede un numero maggiore di 7, abbiamo terminato riconducendoci al caso 2).
Consideriamo solo le quinterne in cui non esistono due numeri uguali. Nei pentagoni i cui vertici sono anche vertici di un ettagono abbiamo (credo) che almeno due coppie di vertici del pentagono sono formati da vertici simmetrici rispetto al quinto vertice. Dunque immagino che in modo analogo a prima si possa dedurre che otteniamo un insieme $A'$ che contenga almeno $7$ elementi appartenenti alla stessa classe di equivalenza.

Se è vero il caso 3) passiamo al caso 4)
Caso 4) Cardinalità di $A$ uguale a 13 ed elementi di 6 classi.
Credo si possa trovare sempre il modo di creare coppie congruenti fino ad ottenere un insieme $ A' $ di cardinalità 13 i cui elementi appartengono a 7 classi. Ma non sono sicuro.

[gio73]

Lo tiro su per metterlo sotto gli occhi di ghira

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"gio73":Lo tiro su per metterlo sotto gli occhi di ghira

??

[axpgn]

Vuole solo RI-metterlo in evidenza, si vede che lo ritiene importante; non sei contento?

[ghira1]

Grazie per il problema.