Oplossingen COMA 2011

4500 days ago by Igor.Voulis

Een foutloos parcours ($\sqrt{2}$ punten)

Stel dat COMA 2012 uit 100 vragen zou bestaan met een puntentelling zoals dit jaar, wat is dan de maximale score die een deelnemer kan behalen?

Antwoord:
We rekenen dit gewoon uit:

sum([sqrt(RR(nth_prime(n))) for n in [1..100]]) 
       
1434.64480185458
1434.64480185458

Een wispelturige functie ($\sqrt{3}$ punten)

Wat is de kleinste oplossing van $2011\cdot\sin(x)=x$?

Antwoord:
We weten zeker dat het nulpunt bereikt wordt voor $x\geq -2011$, want $\max(\sin)=1$, en we verwachten dat het grootste nulpunt niet veel groter is dan $-2011$. We kunnen bijvoorbeeld door een grafiek te bekijken vaststellen dat het nulpunt tussen $-2010$ en $2005$ ligt. Vervolgens kunnen we het nulpunt in dit interval numeriek bepalen. We moeten natuurlijk opletten dat we de juiste oplossing nemen, want er zijn er twee die vrij dicht bij elkaar liggen.

f(x)=x-2011*sin(x) plot(f,(-2015,-1995)) 
       

                                
                            

                                
find_root(f,-2010,-2005) 
       
-2005.8352244172713
-2005.8352244172713
plot(f,(-2006,-2005.6)) 
       

                                
                            

                                

De oplossing die we zoeken is dus:

find_root(f,-2006,-2005.9) 
       
-2005.9775988462893
-2005.9775988462893

Hoe ver durven ze gaan? ($\sqrt{5}$ punten)

Beschouw de kromme met parametervoorstelling
$$\left\{
\begin{array}{l}
x(t) = 3\cos(2 \pi t) + 2\cos(8\pi t)
\\
y(t) = 3 \sin(2 \pi t) + 2\sin(8\pi t)
\\

\end{array} \right.
.$$

Wat is de maximale afstand tussen 2 punten op deze kromme?

Antwoord:

We lossen dit probleem op door eerst het maximum langs onder af te schatten. Vervolgens kijken we waar er waarden van de afstandsfunctie boven deze schatter liggen. Op die plaatsten gaan we herhaaldelijk 'inzoomen' om een goede benadering van onze oplossing te krijgen.

x(t) = 3* cos(2*pi*t) + 2* cos(8*pi*t) y(t) = 3* sin(2*pi*t) + 2 *sin(8*pi*t) d(u,v)=(x(u)-x(v))^2+(y(u)-y(v))^2 n=50 L=[] for A in [0..n]: a=A/n for B in [A..n]: b=B/n L+=[(d(a,b).n(100))] C=[] M=max(L) n=100 L=[] for A in [0..n]: a=A/n for B in [A..n]: b=B/n val=(d(a,b).n(100)) if(val>=M): L+=[val] C+=[[A,B]] while n<=10000000000: old_n=n n=n*4 rat=n/old_n M=max(L) L=[] old_C=C C=[] for AB in old_C: for A in [floor((AB[0]-1/2)*rat)..ceil((AB[0]+1/2)*rat)]: a=A/n for B in [floor((AB[1]-1/2)*rat)..ceil((AB[1]+1/2)*rat)]: b=B/n val=d(a,b).n(100) if(val>=M): L+=[val] C+=[[A,B]] 
       

Van het maximum dat we nu geschat hebben moeten we nu nog de vierkantswortel trekken. De oplossing volgt.

sqrt(max(L)) 
       
9.5812195602659082152682927629
9.5812195602659082152682927629

Men kan de oplossing voor een groot stuk ook symbolisch uitrekenen.  Omdat het een redelijke lange berekening is, gaan we dit hier niet doen.  Maar men kan aantonen dat de maximale afstand gelijk is aan het grootste nulpunt van de veelterm

R.<y> = PolynomialRing(QQ) pol3 = 262144*y^8 - 36831232*y^6 + 1242009600*y^4 - 6526474375*y^2 + 8801237500 pol3 
       
262144*y^8 - 36831232*y^6 + 1242009600*y^4 - 6526474375*y^2 + 8801237500
262144*y^8 - 36831232*y^6 + 1242009600*y^4 - 6526474375*y^2 + 8801237500
pol3.roots(ring=RealField(128), multiplicities=False)[-1] 
       
9.5812195602659082154375293569737199264
9.5812195602659082154375293569737199264

$f$ na $f$ en daarna nog een enkele keren $f$ ($\sqrt{7}$ punten)

Zij \[f:[-\pi,\pi]\rightarrow\mathbb{R}:x\mapsto\pi\cdot\cos(x)\]
Wat is de kleinste waarde waarvoor $f^{2011}$ ($f$ 2011 keer met zichzelf samengesteld) haar maximum bereikt?

Antwoord:

We definieren $g:[-\pi,\pi]\rightarrow\mathbb{R}:x\mapsto\arccos(x/\pi)$. We weten dat $f$ gemaximeerd wordt door $0$, en $f^2$ dus door $g(0)$ en $-g(0)$ en $f^3$ door $g(g(0))$, $g(-g(0))$, $-g(g(0))$ en $-g(-g(0))$ zo verdergaand kunnen we de $2^{2010}$ waarden die $f^{2011}$ maximeren. $g$ is een dalende functie, we moeten $-g$ uitgerkend is het kleinst mogelijke argument uit de vorige stap hebben. We definieren nu een recursieve methode zodanig dat de kleinste waarde altijd op de laatste plaats staat.

RR=RealField(124) 
       
def g(stap,k): if(stap==1): return RR(0) else: return RR(arccos(g(stap-1,floor(k/2))/pi)*(-1)^k) 
       
sys.setrecursionlimit(50000) 
       
g(2011,2^2010-1) 
       
-2.481332382863522569263019336254904794
-2.481332382863522569263019336254904794

De vraag van 24 november 2011 ($\sqrt{11}$ punten)

Zij $f(x)=x^{2011} + a^{24}x^{11} + a^{11}x^{24} +(11a^{24} + 24a^{11})x + e^{a^2}$ en zij $x_1,...,x_{2011}$ de nulpunten van $f$, waarbij elk nulpunt even vaak voorkomt als zijn multipliciteit. Zij $s(a)=\sum_{i=1}^{2011} \frac{1}{x_i}$. Voor welke $a\in\mathbb{R}$ is $s(a)$ maximaal.

Antwoord:

Merk op dat $\prod_{i=1}^{2011} x_i = -e^{a^2}$ en $\sum_{i=1}^{2011} \prod_{i\neq j}x_i = (11a^{24} + 24a^{11})$. En dus: $s(a)=\frac{11a^{24} + 24a^{11}}{-e^{a^2}}$. Door enkele plotjes te maken stellen we vast waar het maximum moet ligt.

f(a)=(11*a^24+24*a^11)/(-e^(a^2)) plot(f,(-10,10)) 
       

                                
                            

                                
plot(f,(-1.5,1.5)) 
       

                                
                            

                                
plot(f,(-1.1,1.1)) 
       

                                
                            

                                

De oplossing is dus:

find_root(derivative(f(a),a),-1.1,-0.5) 
       
-0.99146484444947425
-0.99146484444947425

Is er eentje jarig? ($\sqrt{13}$ punten)

Er zijn 7 miljard mensen op de wereld. Neem gemakshalve aan dat er op 29 februari niemand verjaart en dat elk ander moment even waarschijnlijk is als geboortedag en  -tijdstip. Wat is de kans dat 2 mensen op dezelfde dag van het jaar, het zelfde uur, dezelfde minuut, dezelfde seconde, dezelfde milliseconde, dezelfde microseconde, dezelfde nanoseconde en dezelfde picoseconde geboren zijn?

Antwoord:

Zij $n$ het aantal mensen op de wereld en $N$ het aantal picoseconden per jaar. Het de waarde die we zoeken kunnen we schrijven is \[1-\frac{N!}{N^n (N-n)!} = 1-\frac{\Gamma(N+1)}{N^n \Gamma(N+1-n)} = 1-\exp\left(\log\Gamma(N+1) - n\log(N) - \log\Gamma(N+1-n)\right) .\]

def birthday_gamma(N,n,K=RR): N = K(N) n = K(n) return 1 - exp(log_gamma(N+1) - n*log(N) - log_gamma(N+1-n)) 
       
N = 365*24*60*60*1000*1000*1000*1000 n = 7*10^9 
       
birthday_gamma(N, n, RealField(128)) 
       
0.54016608247371523495245968553007054089
0.54016608247371523495245968553007054089