CoMa 2015

3040 days ago by Toon.Baeyens

De vragen zijn te vinden op:

http://prime.ugent.be/coma2015/vragen

Vraag 1: Moeilijke getallen

def moeilijk(n): return all(gcd(i, n+i+2)==1 for i in [2015..4030]) hundred = [] i = 1 while(len(hundred) < 100): if moeilijk(i): hundred.append(i) i += 1 sum(hundred) 
       

                                
                            

                                

Vraag 2: Een muur. En nog een.

# e is de x-waarde waar we tegen de rode muur lopen # f is de x-waarde waar we tegen de groene muur lopen indien de rode er niet was # g is de x-waarde waar we tegen de groene muur lopen indien de rode er was var("e,f,g") distance(e,f,g) = sqrt(e^2+1)+(1-e)/2+sqrt((f-e)^2+(1+cosh(f))^2)/2+sqrt((cosh(f)-2)^2+f^2)/4+(sinh(1)-sinh(f))/4+sqrt((1-g)^2+(1+cosh(g))^2)/2+sqrt((cosh(g)-2)^2+g^2)/4+(sinh(1)-sinh(g))/4+sqrt((cosh(1)-2)^2+1)/2 # Juist in getyped? distance 
       

                                
                            

                                
# Minimaliseer de verwachte afstand # Sage laat het niet toe om dit met een grotere nauwkeurigheid te doen. # Hiervoor heb ik een bewerkte versie van # https://github.com/fchollet/nelder-mead/blob/master/nelder_mead.py gebruikt. # En dan een zeer hoge precisie als default gezet. # Als antwoord is volgende normaal voldoende a,b,c = minimize(distance,(.5,.5,.5),disp=0) print "e: "+str(a) print "f: "+str(b) print "g: "+str(c) print distance(a,b,c).n() 
       
e: 0.566043072241
f: 0.534307908631
g: 0.665091313457
4.89127322034907
e: 0.566043072241
f: 0.534307908631
g: 0.665091313457
4.89127322034907

Vraag 3: "O Smaug, Chiefest and Greatest of Calamities"

https://en.wikipedia.org/wiki/Dragon_curve#.5BUn.5DFolding_the_Dragon

eerste iteratie R
tweede iteratie RRL
derde iteratie RRLRRLL
vierde iteratie RRLRRLLRRRLLRLL
vijfde iteratie RRLRRLLRRRLLRLLRRRLRRLLLRRLLRLL

Men kan inzien dat een echt vierkant drie opeenvolgende R'en of L'en zijn. Men kan ook zien dat vanaf de tweede iteratie er één bijkomt en degene die er al waren verdubbelen.

Dus: $2^{n-3}-1$

2^(19-3)-1 
       

                                
                            

                                

Vraag 4: De slag bij Gent

Beetje leuke mechanica, hier op verzoek uitgewerkt:

Noem $l$ en $m$ de lengte en massa van de projectielarm van de katapult, $L$ en $M$ de lengte en massa van de contragewichtarm en $\theta$ de $\alpha$ uit de vraag.

Door het hefboomprincipe weten we dat kracht*arm constant blijft dus:

$LMg\cos(\theta) = lmg\cos(\theta)+(l^2m+L^2M)\alpha$

Met $\alpha$ de hoekversnelling van de katapult.

$LMg\cos(\theta) = (l^2m+L^2M)\frac{d^2\theta}{dt^2}+lmg\cos(\theta)$

Dit geeft ons de volgende differentiaal vergelijking:

$\frac{d^2\theta}{dt^2}= \frac{ M L-ml}{l^2m+L^2M}g\cos(\theta)$

Deze is helaas niet exact op te lossen, dan maar numeriek.

M = 1000 # kg m = 20 # kg L = 1 # m l = 5 # m g = 9.81 # m/s^2 h = 8 # m c = (M*L-m*l)/(l*l*m+L*L*M)*g 
       
T = ode_solver() T.function = lambda t,y: [y[1], c*cos(y[0])] T.y_0=[-pi/4,0] T.ode_solve(t_span=[0,1],num_points=1000) (list_plot(map(lambda x: (x[0],x[1][0]), T.solution)) + list_plot(map(lambda x: (x[0],x[1][1]), T.solution), color="red") + line([(0,pi/4),(1,pi/4)], color="green")) 
       

In rood zie je de hoeksnelheid in blauw de hoek. We zien dat de hoek $\frac{\pi}{4}$ wordt gepasseerd na ongeveer $.5$ seconden. Deze grenzen zoeken we op en berekenen dan tot waar de kogel kan geraken.

# De grenzen der nauwkeurigheid for sol in T.solution: if sol[1][0] > pi/4: break; prev = sol prev;sol 
       

                                
                            

                                
# bereken de afstand van een kogel vertrokken op hoogte h met snelheid v onder een hoek a def kogel(h, v, a): global g var("x,t") t_0 = solve(0==h+v*sin(a)*t-g/2*t*t, t, solution_dict=true)[1][t] return t_0*cos(a)*v RR(kogel(h,l*prev[1][1], prev[1][0]));RR(kogel(h, l*sol[1][1], sol[1][0])) 
       

                                
                            

                                

Het projectiel geraakt dus $134.8$ meter ver.

Vraag 5: "May the odds be ever in your favor"

Voor elke trekking:

Trekking 1 juist 2 juist 3 juist 4 juist
$a$ $b$ $c$ $d$ $w$ $x$ $y$ $z$

maken we volgende observatie: $A+B+C+D = 1w+2x+3y+4z$ met $A$ het aantal mensen dat $a$ heeft gekozen, $B$ het aantal dat $b$ heeft gekozen etc.

Dit leidt tot een stelsel van zeventien vergelijkingen en twintig onbekenden.

lotto = matrix([[1, 5, 10, 16, 40082, 12761, 1173, 18], [6, 8, 11, 15, 39942, 12847, 1143, 16], [5, 11, 12, 14, 40048, 12841, 1097, 18], [1, 3, 10, 14, 39821, 12963, 1079, 16], [5, 9, 17, 19, 40076, 12801, 1159, 18], [3, 5, 7, 13, 40178, 12774, 1195, 18], [6, 10, 13, 19, 39938, 12897, 1220, 16], [0, 8, 16, 18, 39895, 13074, 1136, 13], [5, 9, 14, 17, 40124, 12744, 1138, 20], [12, 13, 17, 19, 40011, 12874, 1139, 21], [0, 3, 8, 15, 39751, 12814, 1131, 26], [0, 2, 17, 18, 40072, 12938, 1181, 13], [0, 1, 16, 19, 40104, 12816, 1104, 21], [1, 9, 14, 17, 39770, 12907, 1148, 10], [7, 12, 13, 18, 39987, 13013, 1165, 19], [1, 2, 13, 18, 40087, 13020, 1145, 18], [1, 7, 8, 11, 40173, 12835, 1143, 16]]) 
       
# De coëficientenmatrix A=matrix(17,20) # De resulterende vector B=vector([0]*17) for n in range(17): for k in range(4): A[n,lotto[n,k]]=1 B[n]=lotto[n,4]+2*lotto[n,5]+3*lotto[n,6]+4*lotto[n,7] print A.right_kernel() # Jeej, het aantal mensen dat 19 koos zit niet in de kern A.solve_right(B)[19]# Dus 17278 is het antwoord 
       
Free module of degree 20 and rank 3 over Integer Ring
Echelon basis matrix:
[ 1  0 -4 -1  0  0 -3 -1 -2 -1  1  3 -3  2  0  2 -1  1  2  0]
[ 0  1  0  0  0  1  2  0  1 -1 -1 -2  1 -1  0 -1 -1  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
Free module of degree 20 and rank 3 over Integer Ring
Echelon basis matrix:
[ 1  0 -4 -1  0  0 -3 -1 -2 -1  1  3 -3  2  0  2 -1  1  2  0]
[ 0  1  0  0  0  1  2  0  1 -1 -1 -2  1 -1  0 -1 -1  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]

Vraag 6: Pfffffffffff

Stelling. Zij $n\in\mathbb N$ zo dat $n+1$ priem is en $2$ een primitieve wortel is modulo $n+1$. Definieer $f$ zoals in de opgave. Dan is er juist één niet-triviale cykel en deze bestaat uit de getallen $\frac{n^2-n}2,\ldots,\frac{n^2+n}2-1$, in een zekere volgorde.

Lemma 1. Een niet-triviale cykel heeft minstens $n$ elementen.

Bewijs. $f$ verdubbelt de waarde modulo $n+1$. Omdat $2$ een primitieve wortel is modulo $n+1$, is het aantal elementen van een niet-triviale cykel een veelvoud van $n$. $\square$

Definieer nu voor $a\in\{1,\ldots,n-2\}$ de verzameling $I_a=\{(a,a+1)_n,\ldots,(a+1,a)_n\}$.

Lemma 2. $I_a$ bevat precies één veelvoud van $n$, zijnde $(a+1)n$, en dit is niet één van de randpunten van $I_a$.

Bewijs. Deze uitspraak is niets anders dan $(a,a+1)_n<(a+1,0)_n<(a+1,a)_n$. $\square$

Lemma 3. Zij $k\in I_a$ en noem $b=(a+1)n$ het unieke veelvoud van $n$ in $I_a$. Dan geldt:

  • Als $k<b$ is $f(k)>k$
  • Als $k\geq b$ is $f(k)<k$

Bewijs. Stel $k=(xy)_n$.

  • Als $k<b$ moet wel $b=(x+1,0)_n$, dus $a=x$. Omdat $k\in I_a$ is $k>(xx)_n$, zodat $y>x$ en dus $f(k)>k$.
  • Als $k\geq b$ moet wel $b=(x0)_n$, dus $a=x-1$. Omdat $k\in I_a$ is $k<(xx)_n$, zodat $y<x$ en dus $f(k)<k$. $\square$

Lemma 4. Zij $a\in\{1,\ldots,n-2\}$ en noem $b=(a+1)n$ het unieke veelvoud van $n$ in $I_a$. Dan geldt:

  • $a<\frac n2$ a.s.a. $f(b-1)>I_a$.
  • $a>\frac n2$ a.s.a. $f(b)<I_a$.
Bewijs.
  • De ongelijkheid $f(b-1)=f((a,n-1)_n)=(a+1)n+(n-1)-a\geq(a+1)(n+1)$ herschrijft zich als $a\leq\frac n2-1$.
  • De ongelijkheid $f(b)=f((a+1,0)_n)=(a+1)n-(a+1)\leq a(n+1)$ herschrijft zich als $a\geq\frac n2+\frac12$. $\square$
Lemma 5. Voor $k\in I_a$ geldt:
  • Als $a<\frac n2$: de rij die vertrekt in $k$ bereikt geen getallen kleiner dan die in $I_a$, en bereikt vroeg of laat een getal groter dan die in $I_a$.
  • Als $a>\frac n2$: de rij die vertrekt in $k$ bereikt geen getallen groter dan die in $I_a$, en bereikt vroeg of laat een getal kleiner dan die in $I_a$.
  • Als $a=\frac n2$: de rij die vertrekt in $k$ blijft in $I_a$.

Bewijs. Het volstaat de volgende twee te bewijzen:

  • Als $f(k)<I_a$ is $a>\frac n2$.
  • Als $f(k)>I_a$ is $a<\frac n2$.
Aangezien een niet-triviale cykel minstens $n$ elementen heeft, en omdat uit Lemma 4 volgt dat indien $a\neq\frac n2$, $f(k)\not\in I_a$ voor minstens één $k$, volgt hieruit dan het gestelde. Noem $b=(a+1)n$ het unieke veelvoud van $n$ in $I_a$, en stel $k=(xy)_n$.
  • Als $f(k)<I_a$ moet wegens Lemma 3 $k\geq b$. Merk op dat $f(k)=(xy)_n+y-x\geq(x0)_n-x=f(b)$, dus $f(b)<I_a$. Wegens Lemma 4 is $a>\frac n2$.
  • Als $f(k)>I_a$ moet wegens Lemma 3 $k<b$. Merk op dat $f(k)=(xy)_n+y-x\leq(x,n-1)_n+(n-1)-x=f(b-1)$, dus $f(b-1)>I_a$. Wegens Lemma 4 is $a<\frac n2$. $\square$
 

Bewijs van de stelling. Wegens Lemma 5 kan een niet-triviale cykel enkel bestaan uit elementen van $I_{n/2}$, en brengt elk element van $I_{n/2}$ een niet-triviale cykel voort. Wegens Lemma 1 heeft zo'n cykel minstens $n$ elementen, en omdat $|I_{n/2}|=n$ vormt $I_{n/2}$ de enige niet-triviale cykel. (Merk op dat Lemma 5 ook zegt dat elke rij uiteindelijk in deze cykel terecht komt.) $\square$

n = 2000000000002 print "Nu blijkt toevallig:\n n+1 is priem: "+str(is_prime(n+1))+"\n De multiplicatieve orde van 2 (mod n+1) is n: "+str(multiplicative_order(mod(2,n+1))==n) 
       
Nu blijkt toevallig:
   n+1 is priem: True
   De multiplicatieve orde van 2 (mod n+1) is n: True
Nu blijkt toevallig:
   n+1 is priem: True
   De multiplicatieve orde van 2 (mod n+1) is n: True
var("i") # De ene niet triviale cykel plus alle triviale cykels s(m) = sum(m^2/2+i, i, -m/2, m/2-1) + sum(i*m+i, i, 1, m-1) s 
       

                                
                            

                                
s(n)