OliForum Matematico

Cercherò di essere il più chiaro possibile:
I due amici hanno già mangiato $ 2+3+...+70=35\cdot 71-1 $ ostriche, quindi il numero iniziale $ n $ sarà certamente maggiore.
Prima di verificare che il numero di ostriche rimaste non sono divisibili per $ k $ si sono mangiate $ 2+3+...+(k-1) = \frac{k(k-1)}{2} -1 $ ostriche... Se $ k $ è dispari questa quantità è congrua a $ -1 $ mod $ k $ altrimenti per $ k $ pari questa quantità è congrua a $ k/2-1 $ mod $ k $. Quindi scritto un poco meglio:
$ n \neq -1 (\hbox{mod } 2k+1) $
$ n \neq k-1 (\hbox{mod } 2k) $
per $ 1 \leq k \leq 35 $
Proprio perché fino a $ 71 $ il numero rimasto di ostriche non è divisibile per il numero che ci interessa (qui l'ho messa giù veloce spero si capisca).
Ricavare $ n+1 $ diventa molto più semplice nel sistema di congruenze...
$ n+1=d2^j $ dove $ d $ è un qualsiasi numero dispari. Dalla prima condizione abbiamo che $ d\geq 73 $ e dalla seconda abbiamo che $ j\geq 6 $ (altrimenti per un qualche $ k $ la congruenza sarebbe rispettata).
Il più piccolo numero maggiore di $ 35\cdot 71-1 $ (come detto all'inizio) scrivibile in questa forma è $ 4096 $ ($ k=12 $, $ d=1 $)...
Pertanto $ n= 4095 $.

Spero sia comprensibile e soprattutto spero sia giusto

Non è possibile risolverlo senza matematica modulare?

Beh per capire quello che ho scritto basta sapere che $ a \equiv b (\hbox{mod } c) $ quando $ a $ e $ b $ danno lo stesso resto se divisi per $ c $. Ti consiglio comunque di darti una veloce guardata su qualche dispensina semplice sui moduli... Ci metti mezzoretta e anche meno e ti impari qualcosa di utile

Ad esempio non so cosa significa "congrua". Ma quindi alle olimpiadi é necessario conoscere anche un po' di algebra modulare ? Puoi linkarmi qualche dispensa ?

Quando una quantità intera $a$ è congrua ad un'altra quantità intera $b$ modulo un certo $c$ si scrive $a \equiv b \; (mod \; c)$. E ti riallacci a quello che ha scritto simone.
Per le olimpiadi è necessario conoscere principalmente il programma scolastico, ma non fa certo male conoscere qualche extra. In linea di massima qui trovi l'elenco di tutto ciò che bisogna sapere.
Qui trovi un'ottima dispensa utile per chi è ad un primo approccio con la "teoria olimpionica" e qui la lista di altro materiale.

Però, (solo per curiosità), questo quesito (olimpico) è risolvibile solo se si conosce un po' di algebra modulare?

L'"aritmetica modulare" è soltanto un modo per rappresentare cose intuitive, a cui uno puo' pensare senza studiare teoria, magari in modo piu' veloce, guardando solo cosa ti interessa. Detto cio', puoi benissimo risolvere tutti i problemi che ti vengono proposti senza manco citare una congruenza, le idee di fondo che devi avere sono fondamentalmente le stesse.

Conclusione: Non è necessario che tu la sappia. Ma potrebbe esserti utile a velocizzare i conti. Ti faccio un esempio:
"Qual è il piu' intero positivo n tale che 201520152015.....2015 (scritto n volte di fila) è un quadrato?"

Ci sarebbero due modi di procedere:
1. Supponiamo che esista un tale n, e qual numero è pari a $x^2$. Allora $x$ deve essere dispari. Bene, allora $x$ è della forma $2k+1$, per qualche intero $k$. Allora quel quadrato sarà
$$\underbrace{ 201520152015.....2015}_{\text{n volte}}=x^2=(2k+1)^2=4k^2+4k+1=4\left(k^2+k\right)+1.$$
Ora, sottriamo $1$ a entrambi i membri, otteniamo che $201520152015.....20152014$ è un multiplo di $4$. E' possibile?

2. Se $x$ è pari allora $x^2\equiv 0 \pmod 4$. Se $x$ è dispari allora puo' essere soltanto $x\equiv 1 \pmod 4$ oppure $x\equiv 3\pmod 4$. In entrambi i casi $x^2 \equiv 1 \pmod 4$. Ma il numero di partenza è $\equiv 3\pmod 4$.

Spero sia abbastanza chiaro per capire che l'idea è identica..

Capito. Come ultimo sforzo mi potete presentare il quesito che ho postato in modo da non dover richiamare l'aritmetica modulare?

Dovresti essere in grado di farlo da te:

Prova a parafrasare a parole tue cio' che dice simone sopra, vediamo se e dove ti blocchi

[Ti assicuro che non è per pigrizia, altrimenti non avrei risposto sopra xd]

Ma non è per me, faccio ripetizione di matematica a ragazzi del Liceo, ed un ragazzo che vuole cimentarsi alle olimpiadi mi ha segnalato questo esercizio, ma gli ho risposto subito che secondo me richiedeva conoscenze di algebra modulare. Per questo ho chiesto conferma qui, se però è possibile porglielo in modo semplice attraverso un linguaggio che non richieda algebra modulare mi fareste una grande cortesia, altrimenti vedrò da me e grazie lo stesso per le risposte

karotto ha scritto:Ma non è per me[...]

Fammi fare un riassunto: proponi un esercizio, ti viene data una soluzione che "richiede" la definizione di congruenza, che poi ti viene resa esplicita; ti viene anche mostrato che tale definizione non è necessaria, nel senso che è solo un strumento per "velocizzare" perchè semplicemente lavorare con direttamente con i resti "funziona bene" (meh, quasi sempre); come risposta richiedi una soluzione esplicita che non menzioni le congruenze. Bene, l'obiettivo del forum sarebbe quello di condividere e far imparare qualcosa a tutti quelli che partecipano. Ti viene quindi chiesto di provarci di persona e vedere insieme dov'è il problema, ammesso che ci sia un problema. La risposta è che l'hai chiesto perchè serviva a un ragazzo a cui fai ripetizione, a cui hai detto che era necessario l'aritmetica modulare per la sua soluzione.

E' tutto corretto?

La situazione è questa: domani mattina ho la consegna della tesi, e avrei impiegato decisamente meno tempo a scriverti direttamente la soluzione "senza congruenze", se non fosse che ho speso abbastanza tempo su questo forum da rendermi conto che quello che si vuole raggiungere è qualcosa di meglio rispetto a "ultimo supporto per studenti/relativi tutor in difficoltà". Ora, potresti spenderci dieci minuti anche te?

Chiedo scusa. Evidentemente non sono in linea con la "sensibilità" di questo forum. Avevo chiesto a voi persone più competenti di dare una soluzione (se è possibile) al quesito che potessi spiegare in modo semplice ad un ragazzo senza usare strumenti che non vengono studiato di solito al liceo. Cmq grazie di tutto, chiedo di nuovo scusa per l'affronto e vedrò di sintetizzare la soluzione da solo. Buona fortuna per la tesi amico mio

Grazie mille, appena consegnata Non c'è da scusarsi comunque, è solo che avresti potuto provare da solo, visto che non si finisce mai di imparare.

Soluzione senza congruenze.

Chiamiamo $x$ l'intero cercato. Le condizioni che abbiamo sono equivalenti alla seguenti:

(i) $x$ è dispari.
(ii) $x-2$ non è divisibile per $3$; $x-2-3$ non è divisibile per $3$; $x-2-3$ non è divisibile per $4$; ....; $x-2-3-...-70$ non è divisibile per $71$.
(iii) $x$ è un intero positivo, maggiore o uguale a $2+3+...+70$.

Nient'altro, giusto?

L'unica condizione che ci dà fastidio è la (ii): che si puo' fare? La dobbiamo riscrivere in qualche modo che sia piu' facile da "mettere insieme" alle altre due. In generale quella condizione dice che
$$x-(2+3+...+(k-2)+(k-1))\text{ } \text{ non è divisibile per }\text{ }k.$$
per parecchi interi, precisamente ogni volta che $k=3,4,\ldots,71$. Ora
$$2+3+...+(k-2)+(k-1)=[2+(k-1)]+[3+(k-2)]+[4+(k-3)]+... = (k+1)\cdot (\text{numero di coppie})=\frac{(k+1)(k-2)}{2}.$$

Quindi, la condizione di sopra si puo' riscrivere come
$$x-\frac{(k+1)(k-2)}{2}\text{ } \text{ non è divisibile per }\text{ }k.$$

Poco meglio di prima. Cosa di farebbe comodo? Se avessimo "$x-2$ non è divisibile per $k$", per esempio..

Ora, fissiamo un intero $y$ a caso. Siamo d'accordo che
$$x-\frac{(k+1)(k-2)}{2}\text{ } \text{ non è divisibile per }\text{ }k\text{ }\text{ se e solo se }\text{ }x-\frac{(k+1)(k-2)}{2}+yk\text{ } \text{ non è divisibile per }\text{ }k ?$$


Caso 1. Supponiamo che $k$ sia dispari. Allora $\frac{k+1}{2}$ e $\frac{k-1}{2}$ sono interi. Vogliamo un $y$ da sostituire lì sopra di modo che ci venga qualcosa di comodo. Proviamo $y=\frac{k-1}{2}$. Cosa esce?
$$x-\frac{(k+1)(k-2)}{2}\text{ } \text{ non è divisibile per }\text{ }k\text{ }\text{ se e solo se }\text{ }x-\frac{(k+1)(k-2)}{2}+k\frac{k-1}{2}\text{ } \text{ non è divisibile per }\text{ }k $$

Quindi: se $k$ è dispari la condizione è equivalente a richiedere "$x+1$ non è multiplo di $k$"


Caso 2. Supponiamo che $k$ sia pari. Allora $\frac{k}{2}$ è intero. Scegliamo proprio $y=k/2$, e facciamo come prima.

$$x-\frac{(k+1)(k-2)}{2}\text{ } \text{ non è divisibile per }\text{ }k\text{ }\text{ se e solo se }\text{ }x-\frac{(k+1)(k-2)}{2}+k\frac{k}{2}\text{ } \text{ non è divisibile per }\text{ }k $$

Otteniamo che se $k$ è pari allora la condizione è equivalence a richiedere "$x-\left(\frac{k}{2}-1\right)$ non è multiplo di $k$."


Ora, torniamo al problema originale: la condizione (i) ci dice che $x=2^nd-1$ per qualche interi positivo $n$ e qualche intero positivo dispari $d$. Mettiamola insieme alla (ii):

"$x+1$ non è multiplo di $k$" per ogni $k$ dispari di quelli che ci interessano, in particolare $3,5,7,\ldots,71$. Quindi $d=1$ (da non saltare) oppure $d \ge 73$ (o meglio, se $d>1$ allora il piu' piccolo primo che lo divide è almeno $73$.).

In piu' $x+1-k/2$ non è multiplo di $k$, per ogni $k$ pari. Quindi $2^nd - k/2 $ non è multiplo di $k$. Sappiamo che $n\ge 1$.Scegliendo $k=4$ abbiamo $n\ge 2$. Scegliendo $k=8$ abbiamo $n\ge 3$. $\ldots$. Scegliendo $k=64$ abbiamo $n\ge 6$.

Ora $2^{12}$ funziona (mi fido ). Se è la piu' piccola potenza di due che funziona in questo problema, allora deve essere il numero cercato, perchè altrimenti sarebbe almeno $2^6\cdot 73 > 2^6 \cdot 2^6$.

Grazie mille. Sei stato molto gentile, non me lo aspettavo dopo ciò che ho scritto. Per curiosità in cosa ti stai laureando (credo matematica) e in quale università?