Somma di quadrati
Ciao a tutti!
Vorrei proporvi questo quesito che ho trovato navigando sul web.
Determinare il massimo intero, minore od uguale a 300, che si può scrivere come somma di due
quadrati di numeri interi.
Non saprei proprio da dove partire se non provando le varie combinazioni. Qualche metodo/idea/accorgimento da poter utilizzare?
Vorrei proporvi questo quesito che ho trovato navigando sul web.
Determinare il massimo intero, minore od uguale a 300, che si può scrivere come somma di due
quadrati di numeri interi.
Non saprei proprio da dove partire se non provando le varie combinazioni. Qualche metodo/idea/accorgimento da poter utilizzare?
Risposte
Dovrebbe venire anche a te il numero 288 giusto?
288 non puo venire per una questione di resti, forse volevi scrivere 298?
anche a me torna 298 e sono sicuro che sia giusto perchè il quesito era a crocetta e 298 era il valore piu alto.
$17^2+3^2=298$
avete proceduto per tentativi o avete seguito un metodo?
Cosa significa che 288 non può venire per una questione di resti?
$17^2+3^2=298$
avete proceduto per tentativi o avete seguito un metodo?
Cosa significa che 288 non può venire per una questione di resti?
Scusate, mi è scappato l'8 al posto del 9.
In ogni caso, 288 è comunque la somma di due quadrati: $12^2+12^2$.
In ogni caso, 288 è comunque la somma di due quadrati: $12^2+12^2$.
perche un quadrato ha resto o 0 oppure 1 diviso per 3, ed anche per 4
quindi 288, che è divisibile sia per 3 che per 4, essendo somma di due quadrati ,entrambi i quadrati devono avere resto 0 divisi per 3 e 4, gli unici quadrati minori di 300 che rispettano queste condizioni sono 144 e 36, che sommati non fanno 288.
se conosci le congruenze tutto cio è scontato, se non le conosci puoi dimostrare che un quadrato ha resto o 0 o 1 diviso 4 e 3 cosi:
\(\displaystyle x=4n+r \) ,elevare al qudrato, \(\displaystyle (4n)^2+8n+r^2 \) e vedere che se dividiamo questo polinomio per 4, abbiamo che il resto dipende solo da \(\displaystyle r^2 \),cioè,da r (il resto) che puo assumere i valori 0,1,2,3 che elevati al quadrato, danno resto o 1 o 0.
ora poniamo \(\displaystyle a^2=4n_1+r_1 \ , b^2=4n_2+r_2 \) per qualche \(\displaystyle n_1,r_1,n_2,r_2 \) naturali.
vedi che il resto del polinomio somma \(\displaystyle a^2+b^2=4n_1+r_1+4n_2+r_2 \) ha resto \(\displaystyle r_1+r_2 \) diviso per 4, tornando al problema,288 ha resto 0 diviso per 4, quindi \(\displaystyle r_1+r_2 \) ha resto 0 diviso per 4, quindi entrambi sono divisibili per 4, dato che i resti sono nulli, anche \(\displaystyle a^2 \ e \ b^2 \) sono divisibili per 4.
tutto cio è analogo per 3.
sempre con questi trucchetti (un po diversamente) si dimostra che anche 300 e 299 non vanno bene,rimane allora 298.
quindi 288, che è divisibile sia per 3 che per 4, essendo somma di due quadrati ,entrambi i quadrati devono avere resto 0 divisi per 3 e 4, gli unici quadrati minori di 300 che rispettano queste condizioni sono 144 e 36, che sommati non fanno 288.
se conosci le congruenze tutto cio è scontato, se non le conosci puoi dimostrare che un quadrato ha resto o 0 o 1 diviso 4 e 3 cosi:
\(\displaystyle x=4n+r \) ,elevare al qudrato, \(\displaystyle (4n)^2+8n+r^2 \) e vedere che se dividiamo questo polinomio per 4, abbiamo che il resto dipende solo da \(\displaystyle r^2 \),cioè,da r (il resto) che puo assumere i valori 0,1,2,3 che elevati al quadrato, danno resto o 1 o 0.
ora poniamo \(\displaystyle a^2=4n_1+r_1 \ , b^2=4n_2+r_2 \) per qualche \(\displaystyle n_1,r_1,n_2,r_2 \) naturali.
vedi che il resto del polinomio somma \(\displaystyle a^2+b^2=4n_1+r_1+4n_2+r_2 \) ha resto \(\displaystyle r_1+r_2 \) diviso per 4, tornando al problema,288 ha resto 0 diviso per 4, quindi \(\displaystyle r_1+r_2 \) ha resto 0 diviso per 4, quindi entrambi sono divisibili per 4, dato che i resti sono nulli, anche \(\displaystyle a^2 \ e \ b^2 \) sono divisibili per 4.
tutto cio è analogo per 3.
sempre con questi trucchetti (un po diversamente) si dimostra che anche 300 e 299 non vanno bene,rimane allora 298.
"Luca":
In ogni caso, 288 è comunque la somma di due quadrati: $12^2+12^2$.
hai ragione, ho sbagliato pure io, non so come ho fatto a pensare che dovessero essere distinti.
"wall98":
perche un quadrato ha resto o 0 oppure 1 diviso per 3, ed anche per 4
quindi 288, che è divisibile sia per 3 che per 4, essendo somma di due quadrati ,entrambi i quadrati devono avere resto 0 divisi per 3 e 4, gli unici quadrati minori di 300 che rispettano queste condizioni sono 144 e 36, che sommati non fanno 288.
se conosci le congruenze tutto cio è scontato, se non le conosci puoi dimostrare che un quadrato ha resto o 0 o 1 diviso 4 e 3 cosi:
\(\displaystyle x=4n+r \) ,elevare al qudrato, \(\displaystyle (4n)^2+8n+r^2 \) e vedere che se dividiamo questo polinomio per 4, abbiamo che il resto dipende solo da \(\displaystyle r^2 \),cioè,da r (il resto) che puo assumere i valori 0,1,2,3 che elevati al quadrato, danno resto o 1 o 0.
ora poniamo \(\displaystyle a^2=4n_1+r_1 \ , b^2=4n_2+r_2 \) per qualche \(\displaystyle n_1,r_1,n_2,r_2 \) naturali.
vedi che il resto del polinomio somma \(\displaystyle a^2+b^2=4n_1+r_1+4n_2+r_2 \) ha resto \(\displaystyle r_1+r_2 \) diviso per 4, tornando al problema,288 ha resto 0 diviso per 4, quindi \(\displaystyle r_1+r_2 \) ha resto 0 diviso per 4, quindi entrambi sono divisibili per 4, dato che i resti sono nulli, anche \(\displaystyle a^2 \ e \ b^2 \) sono divisibili per 4.
tutto cio è analogo per 3.
sempre con questi trucchetti (un po diversamente) si dimostra che anche 300 e 299 non vanno bene,rimane allora 298.
Capito tutto ! Grazie mille
In effetti ci si arriva anche a logica !
Una soluzione elementare, senza l'uso dei resti, potrebbe essere la seguente.
Se i due numeri sono uguali allora, indicandoli con x, deve essere:
$x^2+x^2<300$ da cui \(\displaystyle x<\sqrt{150} \sim 12.25 \)
Una prima soluzione è quindi data dalla coppia $12,12$ con $12^2+12^2=288$ che però non è il massimo possibile.
Infatti, se i numeri sono differenti allora, indicandoli con (x,y), deve aversi :
$x^2+y^2<300$
Da qui si ha :
\(\displaystyle 0
$17^2+1^2=290<300$
$17^2+2^2=293<300$
$17^2+3^2=298<300$
$17^2+4^2=305>300$
Ne segue che il massimo richiesto vale 298 e si ottiene con la coppia $x=17,y=3$ o equivalentemente con $x=3,y=17$
Se i due numeri sono uguali allora, indicandoli con x, deve essere:
$x^2+x^2<300$ da cui \(\displaystyle x<\sqrt{150} \sim 12.25 \)
Una prima soluzione è quindi data dalla coppia $12,12$ con $12^2+12^2=288$ che però non è il massimo possibile.
Infatti, se i numeri sono differenti allora, indicandoli con (x,y), deve aversi :
$x^2+y^2<300$
Da qui si ha :
\(\displaystyle 0
$17^2+1^2=290<300$
$17^2+2^2=293<300$
$17^2+3^2=298<300$
$17^2+4^2=305>300$
Ne segue che il massimo richiesto vale 298 e si ottiene con la coppia $x=17,y=3$ o equivalentemente con $x=3,y=17$
Beh, penso che sia stato solo per fortuna che ti sono capitati pochi casi...
Prova infatti a determinare il massimo intero, minore od uguale a $315$, che si può scrivere come somma di due
quadrati di numeri interi.
Se ho capito il tuo procedimento, qui ci vorranno molti più casi da analizzare!
Prova infatti a determinare il massimo intero, minore od uguale a $315$, che si può scrivere come somma di due
quadrati di numeri interi.
Se ho capito il tuo procedimento, qui ci vorranno molti più casi da analizzare!
Mi sono attenuto al testo. Non è colpa mia se nel quesito il limite massimo è 300 ...
L'osservazione di Milizia mi fa venire in mente un vecchio detto:
"Se Giuseppe Garibaldi non moriva a quest'ora sarebbe ancora vivo" !!
L'osservazione di Milizia mi fa venire in mente un vecchio detto:
"Se Giuseppe Garibaldi non moriva a quest'ora sarebbe ancora vivo" !!
A me non pare che il $315$ complichi il ragionamento di ciromario: il massimo quadrato in esso contenuto è sempre $x=17$, quindi si ha
$y^2<=315-17^2=26$
e quindi il massimo valore possibile si ha per $y=5$; e infatti $5^2+17^2=314$, che davvero è il massimo.
Piuttosto, nego che la massima somma si abbia sempre in corrispondenza al massimo quadrato in essa contenuto. Ad esempio, $9^2+16^2=337$ ma se cerchiamo il numero, minore o uguale di $337$, che si può scrivere come somma di quadrati, col ragionamento di ciromario dovremmo porre $x=18$, da cui ricaviamo $y=3$ ed avremmo $18^2+3^2=333$.
$y^2<=315-17^2=26$
e quindi il massimo valore possibile si ha per $y=5$; e infatti $5^2+17^2=314$, che davvero è il massimo.
Piuttosto, nego che la massima somma si abbia sempre in corrispondenza al massimo quadrato in essa contenuto. Ad esempio, $9^2+16^2=337$ ma se cerchiamo il numero, minore o uguale di $337$, che si può scrivere come somma di quadrati, col ragionamento di ciromario dovremmo porre $x=18$, da cui ricaviamo $y=3$ ed avremmo $18^2+3^2=333$.
Insisto col dire che il metodo da me indicato è riferito al valore 300[size=150] e che non ho scritto che quel metodo sia generalizzabile... [/size] La generalizzazione la state cercando voi !!
E speriamo che non venga un altro ...generalizzatore a tutti i costi
E speriamo che non venga un altro ...generalizzatore a tutti i costi
E' vero che non l'hai scritto, ma la tua soluzione lascia aperto il dubbio "Con $x<17$ non si potrà ottenere una somma più alta?". Infatti la soluzione parte da un presupposto che non è vero in generale.
io sono un altro generalizzatore a tutti i costi,ora pero tralasciando la correttezza dell'algoritmo applicato a 300,qualcuno è riuscito a trovare una formula che in funzione di n determina i valori a e b?se si potrebbe postare un hint?
oppure è un problema non polinomiale?
oppure è un problema non polinomiale?
Beh, seguendo il nostro controllore ciromario, è \(\sqrt{315}=17.7\cdots\), quindi \(x=17\) ed \(x^2=289\); d'altra parte è \(315-289=26\), ed il quadrato più vicino a \(26\) è \(25=5^2\); perciò \(y=5\) e la soluzione dovrebbe essere \(314\) (anche perché non mi pare che \(315\) sia esprimibile come somma di quadrati).
Secondo me 17 e 5 non vanno bene perché la somma dei loro quadrati supera 300. Come invece è richiesto.
Sempre in ordine al mio metodo ho scelto di partire da x=17 perché in tal modo ci si avvicina il più possibile a 300 , senza peraltro superarlo. Viste le condizioni imposte dal quesito mi pare una ipotesi ragionevole ma se a qualcuno non piace ...pazienza. Col 300 si può fare e ...non ricominciamo
Sempre in ordine al mio metodo ho scelto di partire da x=17 perché in tal modo ci si avvicina il più possibile a 300 , senza peraltro superarlo. Viste le condizioni imposte dal quesito mi pare una ipotesi ragionevole ma se a qualcuno non piace ...pazienza. Col 300 si può fare e ...non ricominciamo
Una volta mi è successo che nel risolvere un problema di geometria un allievo utilizzasse un teorema inesistente e privo di validità generale; per caso otteneva però il giusto risultato. Ho cercato di spiegargli che era un errore perché il risultato non sarebbe venuto con altri numeri, ma continuava a sostenere che in quel caso andava bene perché il risultato veniva. Se volete, potete schierarvi con quell'allievo; io continuo a sostenere che aveva sbagliato.
Mah... Inutile battibeccare, avete ragione entrambi.
Giammaria fa giustamente notare che la soluzione è incompleta, ed è vero: se non avessimo modo di controllare il risultato con un software, ciromario non avrebbe dimostrato nulla (nel senso che non avrebbe risolto l'esercizio).
Tuttavia, ciromario non ha mai detto di aver usato un teorema o un metodo generale (come lo studente di giammaria); piuttosto, ha intuito che si potesse risolvere il problema in esame facendo alcune considerazioni qualitative, come si fa sempre facendo ricerca, trovandone conferma "a posteriori" (cosa che è di per sé sbagliata).
E, come tutti i risultati di ricerca (o pseudo-ricerca), esso solleva la questione: se volessimo codificare quell'intuizione in un metodo, come dovremmo fare? E quali sarebbero i suoi limiti?
Giammaria fa giustamente notare che la soluzione è incompleta, ed è vero: se non avessimo modo di controllare il risultato con un software, ciromario non avrebbe dimostrato nulla (nel senso che non avrebbe risolto l'esercizio).
Tuttavia, ciromario non ha mai detto di aver usato un teorema o un metodo generale (come lo studente di giammaria); piuttosto, ha intuito che si potesse risolvere il problema in esame facendo alcune considerazioni qualitative, come si fa sempre facendo ricerca, trovandone conferma "a posteriori" (cosa che è di per sé sbagliata).
E, come tutti i risultati di ricerca (o pseudo-ricerca), esso solleva la questione: se volessimo codificare quell'intuizione in un metodo, come dovremmo fare? E quali sarebbero i suoi limiti?
"wall98":
... qualcuno è riuscito a trovare una formula ...?
Io no e posso solo dirti i miei modestissimi risultati; mi riferisco al problema generale:
Nell'ambito dei numeri naturali, trovare il più grande numero minore o uguale ad un numero $n$ dato ed esprimibile nella forma $x^2+y^2$.
Penso che l'unico modo sia andare per tentativi, che possono essere molto limitati dall'ottima idea di ciromario (poi integrata sia da me che da gugo82, citati in ordine di tempo): prendo come $x$ il più grande intero tale che $x^2<=n$ e come $y$ il più grande intero tale che $y^2<=n-x^2$; il numero $n_1=x^2+y^2$ è un buon candidato ad essere la risposta.
Potrebbe però esserci una risposta migliore $m$, con $n_1
1 - Divisibilità per 3.
Se un numero $x$ è divisibile per $3$, possiamo scrivere $x=3a->x^2=9a^2$, quindi il quadrato è divisibile per $9$.
In caso contrario il resto di $x:3$ può valere $1$ o $2$:
nel primo caso abbiamo $x=3a+1->x^2=9a^2+6a+1=3(3a^2+2a)+1$
e nel secondo $x=3a+2->x^2=9a^2+12a+4=9a^2+12a+3+1=3(3a^2+4a+1)+1$
quindi in entrambi i casi il resto di $x^2:3$ è $1$
Sommando due numeri vengono sommati anche i loro resti quindi, detto $r_3$ il resto di $m:3$ abbiamo i seguenti casi:
1a - $r_3=0$: può verificarsi solo se $x,y$ sono entrambi divisibili per 3, quindi $m$ deve essere divisibile per $9$; inoltre, posto $x=3a,y=3b$ deve valere $a^2+b^2=m/9$:
1b - $r_3=1$: uno solo fra $x,y$ è divisibile per $3$;
1c - $r_3=2$: nessuno dei due è divisibile per $3$.
2 - Divisibilità per 4.
Se un numero $x$ è pari, possiamo scrivere $x=2a->x^2=4a^2$, quindi il quadrato è divisibile per $4$.
Se è dispari, $x=2a+1->x^2=4a^2+4a+1=4(a^2+a)+1$, quindi il resto di $x^2:4$ è $1$.
Sommando due numeri vengono sommati anche i loro resti quindi, detto $r_4$ il resto di $m:4$ abbiamo i seguenti casi:
2a - $r_4=0$: può verificarsi solo se $x,y$ sono entrambi pari, quindi $m$ deve essere divisibile per $4$; inoltre, posto $x=2a,y=2b$ deve valere $a^2+b^2=m/4$:
2b - $r_4=1$: uno solo fra $x,y$ è pari;
2c - $r_4=2$: entrambi sono dispari;
2d - $r_4=3$: impossibile.
Vediamo l'applicazione nel caso $n=300$, in cui (come visto nei post precedenti) $n_1=298$ ed esaminiamo gli altri $m$ possibili:
- $m=299$ va scartato per la 2d: si ha $r_4=3$;
- $m=300$ va scartato per la 1a: si ha $r_3=0$ ma $m$ non è divisibile per 9.
Quindi $n_1=298$ è davvero la miglior risposta possibile.
Se però fosse stato $n=301$, non mi sentirei di escluderlo a priori ed farei molti tentativi, cercando in qualche modo di sfruttare il fatto che uno fra $x,y$ è divisibile per 3 ed uno è pari. Terrei anche conto della cifra finale, ricordando che un quadrato non può terminare con una fra le cifre 2, 3, 7, 8.
Accidenti... prima dovevo scrivere $313$ invece di $315$...
In questo caso infatti la soluzione corretta è $12^2 + 13^2 = 313$ a cui non si arriva proprio immediatamente seguendo il metodo proposto.
Il fatto è che non avevo controllato se $314$ o $315$ fossero esprimibili come somma di quadrati, quindi giusto per "arrotondare a un multiplo di $5$" ho rischiato mettendo come upper bound $315$, sbagliando
In questo caso infatti la soluzione corretta è $12^2 + 13^2 = 313$ a cui non si arriva proprio immediatamente seguendo il metodo proposto.
Il fatto è che non avevo controllato se $314$ o $315$ fossero esprimibili come somma di quadrati, quindi giusto per "arrotondare a un multiplo di $5$" ho rischiato mettendo come upper bound $315$, sbagliando
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo