Putnam Exam | 2007: B3

Поділитися
Вставка
  • Опубліковано 21 гру 2024

КОМЕНТАРІ • 97

  • @alejandromahillo3536
    @alejandromahillo3536 4 роки тому +34

    For the HW exercise at 9:39 i will show my answer:
    We want to prove that ⌊√5(3m+⌊m√5⌋)⌋ = 5m+3⌊m√5⌋,
    This is the same as proving :
    √5(3m+⌊m√5⌋) ≥ 5m+3⌊m√5⌋ and
    √5(3m+⌊m√5⌋)

  • @3manthing
    @3manthing 4 роки тому +41

    Michael Penn: "So now we are gonna jump into the solution."
    [An ad starts rolling.]
    Me: 😑

    • @Guilherme-xp1tv
      @Guilherme-xp1tv 4 роки тому

      Every four minutes on his videos I get an ad. I hope he's making a lot of money

  • @mikihermann6045
    @mikihermann6045 4 роки тому +15

    [LaTeX notation for math] Once you reach the 2-recursive expression x_{n+2} = 6 x_{n+1} - 4 x_n, it would be easier now to turn to the characteristic equation t^2 - 6t + 4 = 0 (which you need to solve anyway), solve it to get the roots r_0 and r_1, then pose x_n = A (r_0)^n + B (r_1)^n and compute the coefficients A and B from x_0 = 1 and x_1 = 5.

    • @arimermelstein9167
      @arimermelstein9167 4 роки тому +3

      I didn’t see this comment. See my comment above. I was wondering the same thing. Because I’m in computer science, recurrences are like second nature, so I was so excited to see this question.

  • @alexayg95
    @alexayg95 4 роки тому +2

    HW 9:27
    set sqrt5*m = k + p
    where k is natural number, and 0

    • @TaliaMeir
      @TaliaMeir 4 роки тому +1

      WOW!!! The BEST solution by far

  • @Taterzz
    @Taterzz 4 роки тому +15

    oh no it happened! the proof is trivial and left as an exercise to the reader.

  • @tuffleader2448
    @tuffleader2448 4 роки тому +2

    9:26 Let A=sqrt(5)(3m+floor(m*sqrt(5)) and B=5m+3floor(m*sqrt(5))
    Note that B is an integer. To show floor(A)=B, we need to show A>=B and B+1>A, or equivalently, 0

  • @goodplacetostop2973
    @goodplacetostop2973 4 роки тому +30

    24:43
    Almost the 100K subs. It’s so great to see this channel growing so fast! Anyway, homework....
    Show that in the arithmetic progression with first term 1 and common difference 729, there are infinitely many powers of 10.

    • @divyanshaggarwal6243
      @divyanshaggarwal6243 4 роки тому +2

      by 'ratio' do you mean the common difference?

    • @themathsgeek8528
      @themathsgeek8528 4 роки тому +1

      @@divyanshaggarwal6243 Had the same doubt, I believe it should be the common difference

    • @integralboi2900
      @integralboi2900 4 роки тому +5

      729 = 9^3
      1 + a*9^3 = 10^ n
      a*9^3 = 10^n - 1
      = 9*( 10^n-1 + 10^n-2 … + 1)
      a*9^2 = 10^n-1 + 10^n-2 … + 1
      a*81 = 10^n-1 + 10^n-2 … + 1
      a*81 = 0 (mod 9)
      10^n-1 + 10^n-2 … + 1 = 1^n-1 + 1^n-2 … + 1 (mod 9)
      0 = n (mod 9)
      Choose n = 9x, where x is a positive integer to get a solution and so there are infinite solutions.
      (I hope this is right)

    • @factorial1059
      @factorial1059 4 роки тому +1

      a(n+1)=1+3⁶(n)
      So if a(n+1)=10^k we have
      10^k-1=3⁶(n) so we have to show 3⁶ divide infinitly many numbers 10^k-1
      By LTE we have V3(10^k-1)=V3(10-1)+V3(k)=2+V3(k) so if k=3⁴*a then 10^k-1 is divisible by 3^6 so for every 10^(3⁴*a) there exist number in this sequece

    • @goodplacetostop2973
      @goodplacetostop2973 4 роки тому +1

      @@divyanshaggarwal6243 Fixed

  • @DarkMonolth
    @DarkMonolth 4 роки тому +4

    Using generating functions to solve for the general form of a sequence always gives me differential equations vibes, i.e. solving a differential equation with the Laplace transform.

  • @DeanCalhoun
    @DeanCalhoun 4 роки тому +15

    this one felt a little bit hand-wavy, but still fun nonetheless

    • @kerrym9254
      @kerrym9254 4 роки тому +1

      @@angelmendez-rivera351 Agreed, but the 6 and 4 did seem like it was on his belt next to his light saber.

  • @farpasmasterfarpador9092
    @farpasmasterfarpador9092 4 роки тому +21

    If x1+x2+...+xn=0 and x1²+x2²+...+xn²=1, what is the maximum possible value of x1³+x2³+...+xn³?
    From Brazilian Math Olympiad 2018

    • @DharmveerSingh-ko3nd
      @DharmveerSingh-ko3nd 4 роки тому +1

      If you want more hard maths loving questions then I will highly recommend you this channel's latest videos #mathsandphysicsfun .

    • @abidahasnain2638
      @abidahasnain2638 4 роки тому

      The answer according to me is most probably 0. If you want the solution then you may write (comment) down.

    • @gio5607
      @gio5607 4 роки тому

      @@abidahasnain2638 gimme solution pls

  • @adblockturnedoff4515
    @adblockturnedoff4515 4 роки тому +2

    I believe 22:10 should be (1-sqrt(5))/4 and not (-1-sqrt(5))/4. Thanks for the content!

  • @factorial1059
    @factorial1059 4 роки тому +3

    There is also Simple way to get closed form of recursion xn=6x(n-1)-4x(n-2) let's name M,N roots of the polynomial x²=6x-4. Then we say that x(n)=A*M^n+B*N^n where A and B are some constans that satisfy A+B=x(0) and AM+BN=x(1) and we get the same result

    • @factorial1059
      @factorial1059 4 роки тому +1

      It works because M²=6M-4 and N²=6n-4

  • @algorfrile739
    @algorfrile739 4 роки тому +1

    Nice solution and explanation, as usual.
    Using the first hint, I feel we can come up with an easier way to find the answer.
    First we notice that the nth Fibonacci number is (1/sqrt(5))(phi^n-phib^n) where phi is the golden ratio and phib its conjugate, (1-sqrt(5))/2. When n is big, since |phib|

  • @AlephThree
    @AlephThree 4 роки тому +1

    My blue (1+...+n)^2 Michael Penn hoodie has just arrived. Very nice!

  • @ShenghuiYang
    @ShenghuiYang 4 роки тому

    9:00 proof ==>
    let m be a positive integer and epsilon = m * sqrt(5) - floor( m * sqrt(5)), which is between 0 and 1 exclusive. We know we can take integers from floor functions directly.
    Distribute sqrt(5) in the lhs
    and we have lhs = floor (3 * sqrt(5) * m + sqrt(5) * (sqrt(5) * m - epsilon)) = floor( 3 * floor(sqrt(5) * m ) + 3*epsilon + 5 m - sqrt(5) * epsilon)
    = 5 * m + floor( 3 * floor(sqrt(5) * m )) + (3-sqrt(5)) * epsilon )
    = 5 * m + floor( 3 * floor(sqrt(5) * m ))) + floor( (3-sqrt(5)) * epsilon )
    notice that floor( 3 * floor(sqrt(5) * m )) = 3 * floor(sqrt(5) * m )
    (3-sqrt(5)) * epsilon is a product of two numbers less than one so floor( (3-sqrt(5)) * epsilon) = 0
    Therefore we have the claimed identity.

  • @versatilt7530
    @versatilt7530 4 роки тому +2

    9:31
    you can prove it by induction :
    . x0 = 1 is a natural number
    . suppose xn is a natural number
    xn+1 = xn + Ent(xn*sqrt(5)) = sum of 2 natural numbers
    then xn+1 is a natural number
    .for all n >= 0, xn is a natural number

  • @maydavidr
    @maydavidr 4 роки тому +7

    You really should have provided some explanation for how you obtained the two-step recurrence relation. That was the key step and the rest was just standard procedure.

    • @tomatrix7525
      @tomatrix7525 3 роки тому +1

      @@angelmendez-rivera351 I always find math so unreadable when it is written digitally

    • @MrSantiagoPrado
      @MrSantiagoPrado 3 роки тому

      Try it on x_2, 3 (which you called manually) and you have a 2d system of linear eqs

    • @MrSantiagoPrado
      @MrSantiagoPrado 3 роки тому

      For A and B as he calls them

  • @buxeessingh2571
    @buxeessingh2571 4 роки тому +2

    If you know the closed form of the Fibonacci sequence, then that sqrt(5) should point you at it.

  • @ShinySwalot
    @ShinySwalot 4 роки тому +1

    I love this channel and everything about it, the solutions are always so neat, your voice is good too listen to and the problems are challenging!
    My only problem is the sheer amount of ads lol, but that's on UA-cam's side... Kinda insane though, never expected something as "unpopular" as maths to get consistent double ad midrolls every 7 minutes lol

  • @tomatrix7525
    @tomatrix7525 4 роки тому +1

    Very nice indeed

  • @adandap
    @adandap 4 роки тому +3

    Wow, you did the 5.12 when there is a 5.8 trade route right next door... great if you're up to it I guess. :) But (as others point out too) once you have the second order recursion isn't it much easier to go to an auxiliary equation to get x_n = A (3 + srt(5) )^n + B (3 - sqrt(5) )^n then fit A and B to x_0 and x_1? You get nice neat answers in a few lines that way.

  • @benreymamou
    @benreymamou 4 роки тому

    Hi Michael, I love ur videos, a friend from numebr theory found a shorter way (the only problem is that it uses university methods)
    Let
    K=\Q(\sqrt{5}) and S its Galois automorphism
    Let
    a = 3+\sqrt{5}, b = s(a)=3-\sqrt{5} and they r both algebric integers
    A=\frac{\sqrt{5}+2}{2\sqrt{5}}, B=s(A)=\frac{\sqrt{5}-2}{2\sqrt{5}}
    Define
    y_n = Aa^n + Bb^n.
    Now
    s(y_n)=y_n so all r rationals and later we will show that they r all algebric integers and also (we chose the right A and B):
    y_0=A+B=1=x_0, y_1=Aa+Bb=5=x_1
    Let's assume by induction that
    y_n=x_n and it's also an integer then:
    y_{n+1} = a y_n - Bb^n(a-b) = 3x_n + (\sqrt{5}x_n - Bb^n(a-b))
    Now, the 2 numbers
    y_{n+1},3x_n r integers and
    b^n eopnentially decays so
    (\sqrt{5}x_n - Bb^n(a-b)) = \lfloor\sqrt{5}x_n
    floor

  • @mathlessons4116
    @mathlessons4116 4 роки тому +11

    Could you please show a solution to ANY combinatorics problem? Until i started watching your videos i didnt get number theory and somehow you fixed it, please consider making some combinatorics videos

    • @factorial1059
      @factorial1059 4 роки тому +3

      Yea i agree, we want to see some combinatory problems

    • @MichaelPennMath
      @MichaelPennMath  4 роки тому +25

      I hear you guys! My semester is wrapping up and I will be able to do some new types of problems soon. I'll make sure and do some combinatorics.

    • @tomatrix7525
      @tomatrix7525 4 роки тому

      And he has done it

    • @mathlessons4116
      @mathlessons4116 4 роки тому

      @@tomatrix7525 And it didnt disappoint

  • @JB-ym4up
    @JB-ym4up 4 роки тому +8

    There is a extra - sign.

  • @skylardeslypere9909
    @skylardeslypere9909 4 роки тому +2

    22:10 it should be (1 - sqrt5)/4 instead of
    ( -1 - sqrt5)/4

  • @bobajaj4224
    @bobajaj4224 4 роки тому +2

    your persistence in heavy calculations is praiseworthy

    • @bobajaj4224
      @bobajaj4224 4 роки тому +2

      @@madhukushwaha4578 congratulations, your suggestion just showed how your IQ is close to your age.

    • @bobajaj4224
      @bobajaj4224 4 роки тому

      @Sanjay Surya well if you need this level of education feel free to go learn there :)

  • @juanixzx
    @juanixzx 4 роки тому +3

    I found an error in minute 21:44, you forgot a minus sign, beta-alpha = -√5/2, therefore, A & B are different.
    A=(-1+√5)/(8√5), B=(1+√5)/(8√5)
    I already checked them rejoining partial fractions.

  • @shauryabhardwaj9643
    @shauryabhardwaj9643 4 роки тому

    Please look at the functional equation from 1988 IMO.

  • @natepolidoro4565
    @natepolidoro4565 4 роки тому +1

    21:44 Wouldn't that be negative sqrt(5)/2 ?

    • @natepolidoro4565
      @natepolidoro4565 4 роки тому +1

      Also, 11:08 Wouldn't that be (-2-sqrt(5))/4?

  • @Minskeeeee
    @Minskeeeee 4 роки тому +8

    not saying I would do this, but when a math competition says to write this in closed form, would one receive points for doing 2017 manipulations on 1? lol

    • @DharmveerSingh-ko3nd
      @DharmveerSingh-ko3nd 4 роки тому +1

      If you want more hard maths loving questions then I will highly recommend you this channel's latest videos #mathsandphysicsfun .

    • @EliotPlaysMinecraft
      @EliotPlaysMinecraft 4 роки тому +4

      Theoretically you would receive credit, but that would give you terms on the order of 5^2007 which is far too large to do computations with by hand.

  • @martothelfriky
    @martothelfriky 4 роки тому +2

    Outline of the homework:
    1.- Write [a] = b as a-1 < b

  • @Happy_Abe
    @Happy_Abe 3 роки тому

    How do we get the Xn in the very last step from the equation of F(t)

  • @shwmog
    @shwmog 4 роки тому

    Maybe I have a proof for 9:24
    I don't know if this is the easiest proof, because it is done with just highschool maths.
    First we can say that the left hand of the equation (the part inside the floor function) is greater than/equal to some natural n and less than n+1. Then we try to isolate floor(m*sqrt5) and we get: -m*(3 - sqrt5) + 3/sqrt5 *floor(m*sqrt5)

    • @shwmog
      @shwmog 4 роки тому

      Just realized prof. Penn asked for a "nice solution". This is absolutely NOT a nice solution XD

    • @elkincampos3804
      @elkincampos3804 4 роки тому +1

      Thus, assume m>0 then 1

    • @fernandosotomate6633
      @fernandosotomate6633 4 роки тому

      @@elkincampos3804 Also, the difference you just described is greater than 0. Btw, if I'm not wrong you proved it in less than 3! lines!! That IS a nice and short proof.

    • @elkincampos3804
      @elkincampos3804 4 роки тому

      Since that √5 is irrational . Set {a} is dense in interval (0,1). Then the difference is 0

  • @aleksapupovac
    @aleksapupovac 4 роки тому

    7:23 you forgot to close the normal bracket

  • @divyanshugupta5159
    @divyanshugupta5159 4 роки тому

    Not sure what I am missing:
    It appears that for the generating function, F(1) = 0. Isn't F(1) just the sum of all x_n from zero to infinity. This seems odd since all x_n are positive, right?

  • @robertgerbicz
    @robertgerbicz 4 роки тому +3

    A shorter way without recursion, after we guessed the answer use the explicit formula for Fibonacci numbers:
    fib(n)=1/S*(a^n-b^n) with S=sqrt(5) and a=(1+S)/2, b=(1-S)/2
    then with induction assume that x(n)=2^(n-1)*fib(2*n+3), so
    we need x(n+1)=2^n*fib(2*n+5).
    Use the definition of x:
    x(n+1)=3*x(n)+floor(S*x(n))=floor((3+S)*x(n))=
    =floor((3+S)*2^(n-1)/S*a^(2*n+3)-(3+S)*2^(n-1)/S*b^(2*n+3))
    notice that 3+S=2*a^2, so we can write:
    x(n+1)=floor(2^n/S*a^(2*n+5)-(3+S)*2^(n-1)/S*b^(2*n+3))
    use the formula for fib(2*n+5), so subtract then add the conjectured 2^n*fib(2*n+5), we got:
    x(n+1)=2^n*fib(2*n+5)+floor(-(3+S)*2^(n-1)/S*b^(2*n+3)^n+1/S*2^n*b^(2*n+5))=
    =2^n*fib(2*n+5)+floor(1/S*(2*b^2)^n*b^3*(b^2-(3+S)/2))
    here 0

  • @raghualluri4245
    @raghualluri4245 4 роки тому +1

    I have a unique solution to the 2019 Putnam B2 problem. I can send it you and could you share it on your vid?

  • @andreamarino95
    @andreamarino95 4 роки тому

    I would have used continued fractions of sqrt(5) = 2+1/(2+1/... to get something like floor( xn sqrt(5) ) = floor ( xn an/bn) = usual quotient, for an/bn a sufficiently accurate aporoximant of the continued fraction expansion.
    But this solution is waaaaay clever :) how the hell you guessed the linear recurrence??

  • @aliasgharheidaritabar9128
    @aliasgharheidaritabar9128 4 роки тому

    It was so great.thank u.

  • @davidgillies620
    @davidgillies620 4 роки тому

    This is Sloane A018903, by the way.

  • @wesleydeng71
    @wesleydeng71 4 роки тому +1

    Hmm, feels like you already knew the answer before you started solving the problem. Not sure if anyone in the contest would take this approach.

  • @williamchurcher9645
    @williamchurcher9645 4 роки тому +1

    Hi Michael. Your solutions are fantastic, but often I see you doing complicated generating function analysis rather than just using characteristic equation stuff. Your solutions would be far neater. W

  • @hatimsebbahi8201
    @hatimsebbahi8201 4 роки тому

    les valeurs dans le tableau sont ils exactes?

  • @mathunt1130
    @mathunt1130 4 роки тому

    He left the only tricky part as homework. All the rest is just standard methods.

  • @davidbaxter5473
    @davidbaxter5473 4 роки тому +1

    Homework: I think this is it.
    To prove:
    floor(sqrt(5) * (3m + floor(sqrt*5)*m)) = 5m+3*floor(m*sqrt(5)) where m is any natural number.
    Let m*sqrt(5) = x + c where x is a natural number and 0

  • @tobycooper4639
    @tobycooper4639 4 роки тому

    just solve the entire thing by hand. At 1:40 ish theres the table for xn, with n from 0 to 6. just keep writing that out until you hit n=2007 bro

  • @tomatrix7525
    @tomatrix7525 3 роки тому

    I feel the only hard part here (the key) was to notice that double step recursion. T

  • @marcotosini7156
    @marcotosini7156 4 роки тому

    we have ⌊√5(3m+⌊m√5⌋)⌋ = 5m+3⌊m√5⌋ then
    ⌊√5(3m+⌊m√5⌋)⌋ - 5m+3⌊m√5⌋ = 0
    5m+3⌊m√5⌋ is an integer number so we can move it into the floor
    ⌊√5(3m+⌊m√5⌋) - 5m+3⌊m√5⌋] = 0
    to be true we need to have
    √5(3m+⌊m√5⌋) - 5m+3⌊m√5⌋ < 1
    with simple calculation become
    (3 - √5)(m√5 - ⌊m√5⌋) < 1
    both factors are less the 1 so the product is less than 1

  • @arimermelstein9167
    @arimermelstein9167 4 роки тому +4

    I wonder why you didn’t use characteristic equations to solve the recurrence:
    x(n) = 6x(n-1) - 4x(n-2)
    Assume the solution is r^n
    So we have:
    r^2 - 6r + 4 = 0
    r = 6 +/- sqrt (36 - 16)
    -----------
    2
    r = 3 +/- sqrt (5)
    So the solution is x(n) = A (3+sqrt 5)^n + B (3-sqrt 5)^n
    x(0) = 1 = A+B
    x(1) = 5 = A(3+sqrt5) + B (3-sqrt 5)
    Solve this and obtain the solution.
    A = 1/2 + 1/sqrt 5, B= 1/2 - 1/sqrt 5
    So x(n) = (1/2 + 1/sqrt5) (3+sqrt5)^n + (1/2- 1/sqrt5)(3-sqrt5)^n
    I have no idea whether my answer is the same as the Professor’s or not.

    • @tomasstride9590
      @tomasstride9590 4 роки тому

      Yes it will be the same if there are no slips on either side. I think the reason he choses a diffferent method is that he likes to take a pure mathematical approach rather than say the appproach of an engineer or appied mathematician. On the other hand the real difficulty in this problem was the start which did seem to require a bit of tial and error.

  • @davidmeijer1645
    @davidmeijer1645 4 роки тому

    Wish I could clean my blackboard that fast

  • @davidmeijer1645
    @davidmeijer1645 4 роки тому

    22:15 Shouldn’t that -1 be a +1?

  • @rafael7696
    @rafael7696 4 роки тому

    Uffff, very tricky problem

  • @Div1nePiece
    @Div1nePiece 4 роки тому +5

    I respect Mr. Penn's videos a lot but this one felt like a complete cheat, I don't like the approach
    Edit: β-α= half negative root of 5

    • @Aciniaczek
      @Aciniaczek 4 роки тому +1

      And 1 - α should be (1 - sqrt(5)) / 4 i guess :D

  • @emanuellandeholm5657
    @emanuellandeholm5657 4 роки тому

    Professor Penn really likes those floors!

  • @abdlazizlairgi9690
    @abdlazizlairgi9690 4 роки тому

    Hard af

  • @Tekashiixine-yb5kh
    @Tekashiixine-yb5kh 4 роки тому +1

    I need to watch these videos during my spanish class and ap world history class lol

  • @andrebrouwer7634
    @andrebrouwer7634 4 роки тому

    Try to place a comment once again...
    HW; A=3√5m+√5⌊√5m⌋=3(⌊√5m⌋+{√5m})+√5(√5m - {√5m}) = 3⌊√5m⌋+5m+{√5m}(3-√5) => ⌊A⌋=3⌊√5m⌋+5m

  • @jamescaley9942
    @jamescaley9942 4 роки тому

    I wonder what AI would be like at solving this kind of problem without a priori knowledge of the question. Totally useless I would imagine.

  • @mathsamtube2741
    @mathsamtube2741 4 роки тому +1

    cool