Re: Multipli di 5

Messaggioda axpgn » 18/07/2019, 13:33

Di chi?

Io comunque son convinto dal primo momento che l'ho vista (la tua risposta) che sia giusta :-D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13827 di 14006
Iscritto il: 20/11/2013, 23:03

Re: Multipli di 5

Messaggioda 3m0o » 18/07/2019, 15:38

gio73 ha scritto:
Testo nascosto, fai click qui per vederlo
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:
Testo nascosto, fai click qui per vederlo
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.
Ultima modifica di 3m0o il 18/07/2019, 16:38, modificato 1 volta in totale.
3m0o
Junior Member
Junior Member
 
Messaggio: 393 di 413
Iscritto il: 02/01/2018, 16:00

Re: Multipli di 5

Messaggioda axpgn » 18/07/2019, 16:21

Bello, notevole :smt023

Mi rimane però il dubbio che anche facendo i conti non ci si metteva molto di più :-D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13828 di 14006
Iscritto il: 20/11/2013, 23:03

Re: Multipli di 5

Messaggioda 3m0o » 18/07/2019, 16:47

axpgn ha scritto:Bello, notevole :smt023

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

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 :-D
Stavo provando ora a riflettere se era generalizzabile sostituendo al 5 un qualunque numero primo. Chiaramente cambia anche la cardinalità minimale.
3m0o
Junior Member
Junior Member
 
Messaggio: 394 di 413
Iscritto il: 02/01/2018, 16:00

Re: Multipli di 5

Messaggioda 3m0o » 18/07/2019, 19:02

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$.

Testo nascosto, fai click qui per vederlo
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.
3m0o
Junior Member
Junior Member
 
Messaggio: 395 di 413
Iscritto il: 02/01/2018, 16:00

Precedente

Torna a Giochi matematici

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti