Pagina 1 di 1

Marinada 2022

Inviato: 02/10/2022, 19:30
da ronny
Ho provato qualche problema della Marinada 2022

https://www.skoljka.org/marinada22/

I primi di algebra e geometria erano abbastranza facili. Anche i primi di combinatoria. In teoria dei numeri ho trovato difficoltà, forse sono scarso io in questo argomento. Vi propongo 2 problemi dove mi sono arenato e poi uno preso dall'ultima catena (non so se questo significhe che era la catena con i problemi più difficili):

1) Find the smallest natural number $k$ so that between any $k$ natural numbers we can always choose a couple of them so that their sum is divisible by $100$.

Qualcosa non mi torna. Mi sembra che si possano trovarte infiniti numeri congrui ad 1 modulo 100 e che quindi presi a coppie non diano mai un numero multiplo di 100

2) Find the largest natural number $k$ such that there are natural numbers $a_1 < a_2 < ... < a_k \leq 100000$ such that none of them divides the product of the others

Saranno tutti i primi tra 2 e 100000 ??? Ma come si fa a contarli??

3) How many numbers $x \in \{1, 2, \ldots, 7^{100} \}$ satisfy $7^{100} \mid x^3-6?$

Quindi trovare tutti i numeri che elevati al cubo diano resto 6 se divisi per $7^{100} $. Non mi sono venute idee...

Re: Marinada 2022

Inviato: 18/11/2022, 14:58
da afullo
Eccomi, meglio tardi che mai: :mrgreen:
ronny ha scritto: 02/10/2022, 19:30 1) Find the smallest natural number $k$ so that between any $k$ natural numbers we can always choose a couple of them so that their sum is divisible by $100$.

Qualcosa non mi torna. Mi sembra che si possano trovarte infiniti numeri congrui ad 1 modulo 100 e che quindi presi a coppie non diano mai un numero multiplo di 100
Ho provato a prendere il testo in croato e a tradurlo con Google Translate, mi risulta:

Trova il più piccolo numero naturale k tale che tra tutti i k numeri naturali possiamo sempre sceglierne diversi la cui somma è divisibile per 100.

Così ha molto più senso: non si considerano soltanto le coppie di due addendi, ma anche quelle di un numero arbitrario di essi.
La risposta è 100, ed in effetti è facile verificare che non può essere inferiore, proprio prendendo numeri congrui ad 1 modulo 100: la somma di [tex]m[/tex] di loro è congrua a [tex]m[/tex] modulo 100, e non può essere divisibile per 100 se [tex]m \leq 99[/tex].
Resta da provare che non può essere superiore, ovvero che presi 100 numeri qualunque esiste un loro sottoinsieme (eventualmente coincidente con l'insieme stesso) che ha come somma un multiplo di 100, ma non dovrebbe essere difficile (pigeonhole?)
ronny ha scritto: 02/10/2022, 19:30 2) Find the largest natural number $k$ such that there are natural numbers $a_1 < a_2 < ... < a_k \leq 100000$ such that none of them divides the product of the others

Saranno tutti i primi tra 2 e 100000 ??? Ma come si fa a contarli??
La risposta è 9592, che sono proprio i numeri primi compresi tra 2 e 100000.
Conosco formule per approssimare tale conteggio, per esempio [tex]\dfrac{n}{\ln(n)-1.084}[/tex], tenuto conto che [tex]\ln(n) = \ln(10) \cdot \log_{10}(n) \approx 2.303 \cdot \log_{10}(n)[/tex], ma effettivamente non per fornirlo esattamente, preciso all'unità.

ronny ha scritto: 02/10/2022, 19:30 3) How many numbers $x \in \{1, 2, \ldots, 7^{100} \}$ satisfy $7^{100} \mid x^3-6?$

Quindi trovare tutti i numeri che elevati al cubo diano resto 6 se divisi per $7^{100} $. Non mi sono venute idee...
Il fatto che il titolo del problema sia il gioco di parole p-ride and p-rejudice (facilitato dal fatto che anche in croato le due parole iniziano con la lettera p) mi fa pensare di utilizzare i numeri p-adici...

Re: Marinada 2022

Inviato: 22/11/2022, 12:35
da ronny
afullo ha scritto: 18/11/2022, 14:58 Eccomi, meglio tardi che mai: :mrgreen:
ronny ha scritto: 02/10/2022, 19:30 1) Find the smallest natural number $k$ so that between any $k$ natural numbers we can always choose a couple of them so that their sum is divisible by $100$.

Qualcosa non mi torna. Mi sembra che si possano trovarte infiniti numeri congrui ad 1 modulo 100 e che quindi presi a coppie non diano mai un numero multiplo di 100
Ho provato a prendere il testo in croato e a tradurlo con Google Translate, mi risulta:

Trova il più piccolo numero naturale k tale che tra tutti i k numeri naturali possiamo sempre sceglierne diversi la cui somma è divisibile per 100.

Così ha molto più senso: non si considerano soltanto le coppie di due addendi, ma anche quelle di un numero arbitrario di essi.
La risposta è 100, ed in effetti è facile verificare che non può essere inferiore, proprio prendendo numeri congrui ad 1 modulo 100: la somma di [tex]m[/tex] di loro è congrua a [tex]m[/tex] modulo 100, e non può essere divisibile per 100 se [tex]m \leq 99[/tex].
Resta da provare che non può essere superiore, ovvero che presi 100 numeri qualunque esiste un loro sottoinsieme (eventualmente coincidente con l'insieme stesso) che ha come somma un multiplo di 100, ma non dovrebbe essere difficile (pigeonhole?)
Vediamo se ho capito: trovare il naturale k più piccolo tale che [comunque si scelgano k numeri naturali] o [posso scegliere k numeri naturali]?
e poi prosegue: tra questi k esiste un sotto insieme di loro che ha somma divisibile per 100
afullo ha scritto: 18/11/2022, 14:58
ronny ha scritto: 02/10/2022, 19:30 2) Find the largest natural number $k$ such that there are natural numbers $a_1 < a_2 < ... < a_k \leq 100000$ such that none of them divides the product of the others

Saranno tutti i primi tra 2 e 100000 ??? Ma come si fa a contarli??
La risposta è 9592, che sono proprio i numeri primi compresi tra 2 e 100000.
Conosco formule per approssimare tale conteggio, per esempio [tex]\dfrac{n}{\ln(n)-1.084}[/tex], tenuto conto che [tex]\ln(n) = \ln(10) \cdot \log_{10}(n) \approx 2.303 \cdot \log_{10}(n)[/tex], ma effettivamente non per fornirlo esattamente, preciso all'unità.
Allora avevo capito il problema, ma come si faceva a contarli, sono troppi!!
afullo ha scritto: 18/11/2022, 14:58
ronny ha scritto: 02/10/2022, 19:30 3) How many numbers $x \in \{1, 2, \ldots, 7^{100} \}$ satisfy $7^{100} \mid x^3-6?$

Quindi trovare tutti i numeri che elevati al cubo diano resto 6 se divisi per $7^{100} $. Non mi sono venute idee...
Il fatto che il titolo del problema sia il gioco di parole p-ride and p-rejudice (facilitato dal fatto che anche in croato le due parole iniziano con la lettera p) mi fa pensare di utilizzare i numeri p-adici...
Mi sono dimenticato i numeri p-adici. Li riguardo e poi ci penso, grazie.

Re: Marinada 2022

Inviato: 25/11/2022, 20:28
da afullo
1. Direi "comunque si scelgano k numeri naturali", altrimenti se la scelta fosse libera basterebbe scegliere per esempio 47 e 53, che avrebbero somma 100 e quindi renderebbero realizzabile la cosa per k=2...

2. Oltretutto così diventa un problema facilmente automatizzabile (oltre al fatto che fermandosi proprio a 100.000 si trova anche il risultato esatto in diverse fonti ben piazzate nei motori di ricerca), che è proprio ciò da preferibilmente evitare se si vuole fare una gara a distanza cercando di minimizzare il rischio di "aiutini"...

3. Sono Teoria dei Numeri avanzata, in effetti io ho conseguito tre medaglie a Cesenatico negli anni 2000 senza all'epoca conoscerli...