Esercizi delle olimpiadi
Salve vi propongo alcuni esercizi delle olimpiadi di matematica che ho svolto.
I 13 nani della compagnia di thorin entrano,uno alla volta,a casa di bilbo, il quale li fa accomodare alla sua grande tavola rotonda che ha proprio 13 posti.Per primo entra Thorin, e poi seguono gli altri 12 in rigoroso ordine di età, dal più vecchio al più giovane.Thorin si siede in un posto qualsiasi, e ogni altro nano si siede sempre vicino a qualcuno che è già arrivato. In quanti modi si possono disporre i nani, contando una volta sola le configurazioni uguali a meno di rotazioni della tavola?
Come è noto, per comodità , gli orchi contano in base 238.Qual è il più grande fattore primo del numero orchesco 143?Dare la risposta in base 10
Gandalf, Bilbo e Thorin si trovano ai vertici di un triangolo rettangolo, in cui l'angolo retto è costituito da Gandalf; quest'ultimo dista 6960 metri da Bilbo e 7308 metri da Thorin.La Montagna Solitaria si trova alla stessa distanza da Bilbo e Thorin, e la sua vetta dista 5046 metri da Gandalf.Quanto è alta al massimo la montagna?
e il più difficile
Bilbo e i suoi compagni si trovano finalmente davanti alla porta segreta della Montagna Solitaria;tuttavia c'è solo un modo per superarla.Detta F una funzione dall'insieme degli interi positivi all'insieme degli interi positivi tale che
- F(n)=n-F(F(n-1)) per ogni n>1;
- F(1) è dispari
La porta si aprirà solo pronunciando ad alta voce il valore F(4198)
Quale numero deve dire Bilbo?
I 13 nani della compagnia di thorin entrano,uno alla volta,a casa di bilbo, il quale li fa accomodare alla sua grande tavola rotonda che ha proprio 13 posti.Per primo entra Thorin, e poi seguono gli altri 12 in rigoroso ordine di età, dal più vecchio al più giovane.Thorin si siede in un posto qualsiasi, e ogni altro nano si siede sempre vicino a qualcuno che è già arrivato. In quanti modi si possono disporre i nani, contando una volta sola le configurazioni uguali a meno di rotazioni della tavola?
Come è noto, per comodità , gli orchi contano in base 238.Qual è il più grande fattore primo del numero orchesco 143?Dare la risposta in base 10
Gandalf, Bilbo e Thorin si trovano ai vertici di un triangolo rettangolo, in cui l'angolo retto è costituito da Gandalf; quest'ultimo dista 6960 metri da Bilbo e 7308 metri da Thorin.La Montagna Solitaria si trova alla stessa distanza da Bilbo e Thorin, e la sua vetta dista 5046 metri da Gandalf.Quanto è alta al massimo la montagna?
e il più difficile
Bilbo e i suoi compagni si trovano finalmente davanti alla porta segreta della Montagna Solitaria;tuttavia c'è solo un modo per superarla.Detta F una funzione dall'insieme degli interi positivi all'insieme degli interi positivi tale che
- F(n)=n-F(F(n-1)) per ogni n>1;
- F(1) è dispari
La porta si aprirà solo pronunciando ad alta voce il valore F(4198)
Quale numero deve dire Bilbo?
Risposte
Provo i primi 3, per vedere se sono ancora capace di risolverli.
Primo:
Secondo:
Terzo:
Primo:
Secondo:
Terzo:
@robb
[ot]messaggio numero 1000.... Mi commuovo
ps: non c'entra un caz*o l'orso, lo metto solo perchè mi piace...[/ot]
[ot]messaggio numero 1000.... Mi commuovo
ps: non c'entra un caz*o l'orso, lo metto solo perchè mi piace...[/ot]
Provo l'ultimo, metto un inizio dato che nessuno lo fa
Mi risulta che il valore della funzione f(n) aumenta di 13 unità ogni 21 passi. f(4200) = 2600, f(4198) = 2599.
Sulle risposte però risulta una soluzione diversa, 2595. Non capisco dov'è l'errore.
Saluti
Sulle risposte però risulta una soluzione diversa, 2595. Non capisco dov'è l'errore.
Saluti
"RobStam":
Mi risulta che il valore della funzione f(n) aumenta di 13 unità ogni 21 passi. f(4200) = 2600, f(4198) = 2599.
Sulle risposte però risulta una soluzione diversa, 2595. Non capisco dov'è l'errore.
Saluti
Io ho notato un'altra regolarità, ma non saprei dimostrarla; l'ho controllata fino a $n=41$.
Detti $q,r$ quoziente e resto di $n:8$, si ha $F(n)=5q+g(r)$. Poiché $r$ può assumere solo 8 valori, la funzione $g(r)$ può facilmente essere data come tabella.
Però in questo modo ottengo $F(4198)=2624$ e non è la risposta ufficiale; inoltre manca la dimostrazione iniziale.
Nei panni di Bilbo pronuncerei al alta voce tutti i numeri da 2590 in poi, fino all'apertura.
Detti $q,r$ quoziente e resto di $n:8$, si ha $F(n)=5q+g(r)$. Poiché $r$ può assumere solo 8 valori, la funzione $g(r)$ può facilmente essere data come tabella.
Però in questo modo ottengo $F(4198)=2624$ e non è la risposta ufficiale; inoltre manca la dimostrazione iniziale.
Nei panni di Bilbo pronuncerei al alta voce tutti i numeri da 2590 in poi, fino all'apertura.
Ritiro la mia risposta: ad un esame più attento non regge.
Miglioro invece quella di RobStam: $F(n)$ è l'arrotondamento ad intero di $13n:21$, ma il suo risultato non cambia. Inoltre anche per lui manca la dimostrazione.
Miglioro invece quella di RobStam: $F(n)$ è l'arrotondamento ad intero di $13n:21$, ma il suo risultato non cambia. Inoltre anche per lui manca la dimostrazione.
Per qualche strana magia stavo notando che ai numeri di fibonacci viene associato il numero di fibonacci precedente (es: $f(21)=13$)... e $4198$ è abbastanza vicino ad un numero di fibonacci... che strano 
Scusate l'approccio empirico e naive: non sono un matematico e sono appannato da decenni di disuso.
Ho calcolato F(4198)=2595 con un programmino. Si noti che 2595/4198=0.618...
Molti elementi per n<610 valgono F(n)=13n/21 e 13/21=0.619...
Per n crescente F(n)/n approssima 0.618...
Sostituendo xn a F(n) nella definizione ottengo $xn=n-x^2(n-1) \rightarrow (n-1)x^2+nx-n=0$.
Per $n \rightarrow\infty$ ho $x^2+x-1=0$ che dà $x=(sqrt(5)-1)/2$.
Nb: $(sqrt(5)-1)/2=0.6180399...$ è l'inverso della sezione aurea $(1+\sqrt(5))/2=1.6180399...$.
Ho calcolato F(4198)=2595 con un programmino. Si noti che 2595/4198=0.618...
Molti elementi per n<610 valgono F(n)=13n/21 e 13/21=0.619...
Per n crescente F(n)/n approssima 0.618...
Sostituendo xn a F(n) nella definizione ottengo $xn=n-x^2(n-1) \rightarrow (n-1)x^2+nx-n=0$.
Per $n \rightarrow\infty$ ho $x^2+x-1=0$ che dà $x=(sqrt(5)-1)/2$.
Nb: $(sqrt(5)-1)/2=0.6180399...$ è l'inverso della sezione aurea $(1+\sqrt(5))/2=1.6180399...$.
Ho tentato anch'io un approccio come quello di veciorik; anzi, l'ho complicato supponendo che $F(n)$ sia l'arrotondamento di $nx+y$. Col suo stesso ragionamento ottengo
[size=120]${(x=(sqrt5-1)/2=0.6180),(y=(3-sqrt5)/(3+sqrt5)=(7-3sqrt5)/2=0.1459):}$[/size]
e si ha il corretto $F(4198)=2595$.
La formula però non vale per $n=20$ perché si ha $nx+y=12.5066$ che si arrotonda a $13$; è invece $F(20)=12$.
Ho cercato di ricavare i valori di $F(n)$ con un foglio elettronico ma non so come ottenere la funzione di funzione e chiedo consigli. Ad esempio, se in B10 ho $F(10)=6$ e in B6 c'è $F(6)=4$, come posso ottenere automaticamente che $F(F(10))=4$ ?
Io uso OpenOffice.org Calc, ma penso che possa servirmi anche una risposta relativa ad altri fogli elettronici.
[size=120]${(x=(sqrt5-1)/2=0.6180),(y=(3-sqrt5)/(3+sqrt5)=(7-3sqrt5)/2=0.1459):}$[/size]
e si ha il corretto $F(4198)=2595$.
La formula però non vale per $n=20$ perché si ha $nx+y=12.5066$ che si arrotonda a $13$; è invece $F(20)=12$.
Ho cercato di ricavare i valori di $F(n)$ con un foglio elettronico ma non so come ottenere la funzione di funzione e chiedo consigli. Ad esempio, se in B10 ho $F(10)=6$ e in B6 c'è $F(6)=4$, come posso ottenere automaticamente che $F(F(10))=4$ ?
Io uso OpenOffice.org Calc, ma penso che possa servirmi anche una risposta relativa ad altri fogli elettronici.
Ah eccolo, si nota anche che $F(a_h+a_k) = a_{h-1}+a_{k-1}$ dove $a_h$ e $a_k$ sono numeri di fibonacci. Si dimostra bene?
@Giammaria
Non so se ho capito bene quello che ti serve ma se nella prima colonna hai $A1=1, A2=2, ...$, nella seconda hai $B1=F(A1), B2=F(A2), ...$, nella terza metti $C1=F(B1), C2=F(B2), ...$ forse qualcosa ottieni (se i valori non diventano troppo grandi ...)
Cordialmente, Alex
Non so se ho capito bene quello che ti serve ma se nella prima colonna hai $A1=1, A2=2, ...$, nella seconda hai $B1=F(A1), B2=F(A2), ...$, nella terza metti $C1=F(B1), C2=F(B2), ...$ forse qualcosa ottieni (se i valori non diventano troppo grandi ...)
Cordialmente, Alex
@ xXStephXx
Suppongo che la tua risposta sia la chiave per la soluzione, ma proprio non la capisco. Per favore, puoi spiegarti meglio?
@ axpgn
Il mio problema è che non ho una formula analitica per $F(n)$. Hai ragione per la colonna A e nel pensare che la colonna B riporti i valori della funzione; supponendo che sia già compilata fino a $B10$ e che in quest'ultima cella ci sia $6$, io voglio mettere in $B11$ il risultato di $A11-B6$. Se invece in $B10$ ci fosse $4$, in $B11$ metterei $A11-B4$.
La mia domanda è: come ottenerlo automaticamente, senza dovere ogni volta leggere il contenuto di una cella per indicare l'indirizzo di quella che mi serve?
Suppongo che la tua risposta sia la chiave per la soluzione, ma proprio non la capisco. Per favore, puoi spiegarti meglio?
@ axpgn
Il mio problema è che non ho una formula analitica per $F(n)$. Hai ragione per la colonna A e nel pensare che la colonna B riporti i valori della funzione; supponendo che sia già compilata fino a $B10$ e che in quest'ultima cella ci sia $6$, io voglio mettere in $B11$ il risultato di $A11-B6$. Se invece in $B10$ ci fosse $4$, in $B11$ metterei $A11-B4$.
La mia domanda è: come ottenerlo automaticamente, senza dovere ogni volta leggere il contenuto di una cella per indicare l'indirizzo di quella che mi serve?
Non lo so se serve davvero, però mi era sembrata una cosa buffa. Con ogni numero di fibonacci si ottiene il numero di fibonacci precedente (da qui tutte quelle osservazioni sul rapporto che tende a $\phi$). Poi ho visto che questa cosa sembra valida pure con la somma di due numeri di fibonacci ma qui ho provato solo pochi casi quindi non saprei 
Riferendomi alla soluzione indicata nel mio penultimo intervento, ho provato a dare ad $y$ un valore un po' inferiore ed ho posto $y=0,1392$. Funziona bene con i valori per cui l'ho testato, cioè per $1<=n<=42$ e per il risultato finale; viene però a mancare una giustificazione teorica, anche poco rigorosa.
@giammaria
per studiare la funzione ho fatto questa procedura Basic in LibreOffice Calc.
Non ho decifrato la relazione con i numeri di Fibonacci.
Serve un esperto di successioni ricorsive. Mi defilo.
per studiare la funzione ho fatto questa procedura Basic in LibreOffice Calc.
Non ho decifrato la relazione con i numeri di Fibonacci.
Serve un esperto di successioni ricorsive. Mi defilo.
Grazie mille. Vedo però che hai dovuto ricorrere ad un linguaggio di programmazione; io cercavo una procedura applicabile sul foglio elettronico ma forse non c'è.
Ho preferito scrivere un programma perché ero un informatico (ora in pensione), perché ci posso inserire altri trattamenti per esplorare la questione, per fare moltissimi calcoli con prestazioni decenti, perché posso inserire i dati nelle celle senza fare troppi "copia e incolla" (mi disturbano) e, soprattutto, perché non conoscevo la funzione INDIRETTO appena scoperta.
A1=1
A2=A1+1
...
B1=1
B2=A2-INDIRETTO("B"&INDIRETTO("B"&A1))
...
[/list:u:vqgpk5nc]
Almeno per $n<=1000000$, il computer mi conferma che $f(n) = \floor{{n+1}/\phi}$.
Forse questa si riesce a dimostrare?
Forse questa si riesce a dimostrare?
Complimenti a milizia96! La sua formula è quella voluta e dimostro che è condizione sufficiente per la soluzione; manca ancora la dimostrazione che è condizione necessaria. Forse per assurdo, supponendo che ci siano anche altre soluzioni?
Riscrivo la tesi nella forma
$A=f(f(n-1))+f(n)=n$
Pongo $a=1/phi=(sqrt5-1)/2=0,62$ e ricordo che $a^2+a-1=0$
Ricordando poi che la parte intera di un numero è una sua approssimazione per difetto, deve esistere un numero $x$ tale che
${(f(n-1)=h=[an]=an-x),(0
Analogamente, esiste $y$ tale che
${(f(f(n-1))=f(h)=[a(h+1)]=ah+a-y=a(an-x)+a-y=a^2n-ax-y+a),(0
I caso: si ha $f(n)=h=an-x$
In questo caso dobbiamo avere nell'ordine $h, an, a(n+1),h+1$ e questo è possibile solo se $0
$A=f(f(n-1))+f(n)=a^2n-ax-y+a+an-x=n(a^2+a-1)+n-z=n-z$
avendo posto $z=ax+y-a+x=x(1+a)+y-a$
Gli estremi inferiore e superiore (mai raggiunti) di $z$ si hanno in corrispondenza a quelli di $x,y$ e si ha
$z_("inf")=0*(1+a)+0-a=-a=-0,62$
$z_("sup")=(1-a)(1+a)+1-a=1-a^2+1-a=1-(a^2+a-1)=1$
Abbiamo definito $A$ come la somma di due numeri interi, quindi è intero e tale deve essere anche $z$: è perciò l'unico intero contenuto fra questi estremi, cioè
$z=0->A=n$
II caso: si ha $f(n)=h+1=an-x+1$
In questo caso dobbiamo avere nell'ordine $h, an,h+1, a(n+1)$ e questo è possibile solo se $1-a
$A=f(f(n-1))+f(n)=a^2n-ax-y+a+an-x+1=n(a^2+a-1)+n-z=n-z$
avendo posto $z=ax+y-a+x-1=x(1+a)+y-a-1$
con estremi
$z_("inf")=(1-a)(1+a)+0-a-1=1-a^2-a-1=-1-(a^2+a-1)=-1$
$z_("sup")=1(1+a)+1-a-1=1$
e l'unico intero racchiuso è $z=0->A=n$
@ veciorik. Mille grazie; neanche io conoscevo quella funzione. Nelle istruzioni ho notato che vicino ad essa c'è anche la funzione INDIRIZZO che forse funziona altrettanto bene, ma non ho provato perché, in fondo, me ne basta una.
Riscrivo la tesi nella forma
$A=f(f(n-1))+f(n)=n$
Pongo $a=1/phi=(sqrt5-1)/2=0,62$ e ricordo che $a^2+a-1=0$
Ricordando poi che la parte intera di un numero è una sua approssimazione per difetto, deve esistere un numero $x$ tale che
${(f(n-1)=h=[an]=an-x),(0
Analogamente, esiste $y$ tale che
${(f(f(n-1))=f(h)=[a(h+1)]=ah+a-y=a(an-x)+a-y=a^2n-ax-y+a),(0
I caso: si ha $f(n)=h=an-x$
In questo caso dobbiamo avere nell'ordine $h, an, a(n+1),h+1$ e questo è possibile solo se $0
$A=f(f(n-1))+f(n)=a^2n-ax-y+a+an-x=n(a^2+a-1)+n-z=n-z$
avendo posto $z=ax+y-a+x=x(1+a)+y-a$
Gli estremi inferiore e superiore (mai raggiunti) di $z$ si hanno in corrispondenza a quelli di $x,y$ e si ha
$z_("inf")=0*(1+a)+0-a=-a=-0,62$
$z_("sup")=(1-a)(1+a)+1-a=1-a^2+1-a=1-(a^2+a-1)=1$
Abbiamo definito $A$ come la somma di due numeri interi, quindi è intero e tale deve essere anche $z$: è perciò l'unico intero contenuto fra questi estremi, cioè
$z=0->A=n$
II caso: si ha $f(n)=h+1=an-x+1$
In questo caso dobbiamo avere nell'ordine $h, an,h+1, a(n+1)$ e questo è possibile solo se $1-a
$A=f(f(n-1))+f(n)=a^2n-ax-y+a+an-x+1=n(a^2+a-1)+n-z=n-z$
avendo posto $z=ax+y-a+x-1=x(1+a)+y-a-1$
con estremi
$z_("inf")=(1-a)(1+a)+0-a-1=1-a^2-a-1=-1-(a^2+a-1)=-1$
$z_("sup")=1(1+a)+1-a-1=1$
e l'unico intero racchiuso è $z=0->A=n$
@ veciorik. Mille grazie; neanche io conoscevo quella funzione. Nelle istruzioni ho notato che vicino ad essa c'è anche la funzione INDIRIZZO che forse funziona altrettanto bene, ma non ho provato perché, in fondo, me ne basta una.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo