TT's Maths Thread

[dcc]

Proof by large numbers (Hi polya's conjecture):

Code: [Select]

import List

-- Checks the number's under n using accuracy level p
check :: Integer   -- Number under consideration
      -> Integer   -- Accuracy
      -> Int       -- # of numbers found (<n)
check n p = length $ filter (<=n) $ nub $ map sfloor (genNumList n p)

-- Our special floor function
sfloor :: Double -> Integer
sfloor x = floor (2*x) + floor (4*x) + floor (6*x) + floor (8*x) :: Integer

-- Generates a special list of numbers (maximal element = n/8 => the highest we want to check (seriously))
genNumList :: Integer      -- Number under consideration
           -> Integer      -- Accuracy
           -> [Double] -- Output list of numbers
genNumList n p = [ (fromIntegral x) / (fromIntegral (8 * p)) | x <- [1..(n * p)]]
From this, we see:

Code: [Select]

check 1000 1   = 400
check 1000 2   = 501
check 1000 3   = 601
check 1000 20  = 601
check 1000 100 = 601
-- ad infinitum

This clearly shows that 601 (counting 0) is the solution.  So the 'real' solution is 600.  Takes about 5 seconds to run for accuracy level 3, about a minute for accuracy level 100.  This is my 'exhaustive' proof by large numbers.

[TrueTears]

expand that difference and you get:



so this is the number of times appears in our sum. Therefore it contributes to the sum.

So now we have to add over m=1 to to m=6. We add to m=6 since 7^4>1995. Then we add on the remaining numbers like you did for f(n=7).

Ah okay, I'll try now, and yeah pretty shit question cause you gotta use a bit of trial and error no matter what to find out that 7^4

[kamil9876]

Where's the flaw in this one? http://vcenotes.com/forum/index.php/topic,19896.msg201920.html#msg201920

edit: oh wait, you agree it's 600  

[dcc]

I drew a picture of the floor problem in Hogo (a programming language I created using haskell), and it's kinda interesting:



You can clearly see the periodic behaviour that kamil referred to (watch the difference in the levels of the bar => increases are not uniform).

[TrueTears]

Prove that the sum is irrational.

I've planned my approach in 2 ways:

1. Must show that the sum is not an integer.
2. Must show it is a zero of a monic polynomial.

But how to go about it?

[Ilovemathsmeth]

TrueTears, you're SOOOO motivated! WOW!

I feel really ashamed, haven't started looking at Specialist, although I did buy the book and all my friend's working out and intend to start...sometime...

[supdawg]

If you can prove each term is irrational then sum must be irrational

So you must prove that

gcd(n, n+1) = 1, so does not share any common divisors with . But ... etc

So none of them are squares => sum is irrational

[kamil9876]

If you can prove each term is irrational then sum must be irrational

[supdawg]

doesn't apply to that sum

[TrueTears]

Prove that the sum is irrational.

I've planned my approach in 2 ways:

1. Must show that the sum is not an integer.
2. Must show it is a zero of a monic polynomial.

But how to go about it?

Okay so had another look at this.

So to prove the sum is not an integer.



So,

Let

An overestimate for the sum would be

An underestimate for the sum would be

But since

Thus the sum is not an integer.

Use induction to prove it is a zero of a monic polynomial.

Base case:

Let the sum be written as

Let .

Thus



Thus is a zero.

Now for the inductive hypothesis, assume is true.

Thus is true.

Now we wish to prove that is also true.

We will denote this as .







Let this be a zero of a monic polynomial

So using the inductive hypothesis, is a zero , namely

so

Now what...? How do we expand that polynomial...?

[kamil9876]

doesn't apply to that sum

yes, and that is the trick to the problem.

[humph]

In Accelerated Maths (1&2) @ uom, we studied linear algebra (vector spaces / inner product spaces) / real analysis / calculus, so there isn't much relation between the types of questions posted here and the stuff you will study at uni. 

Uni mathematics is set up so that you are able to tackle other subjects later on (i.e. complex analysis follows from real analysis, group theory follows from linear algebra and so on), whereas Olympiad maths doesn't really 'lead' anywhere (in terms of learning more about different topics in the future).

At least, that's my take on it.

+1. There's no real structure or focus in Olympiad maths, which is one of the reasons why it's so difficult - there's no set of rules to apply or techniques to use for every question.
(Of course the point of Olympiad training is to teach rules and techniques that come in handy, and try to identify when to apply them, but it's this identifying bit that makes successful IMO participants a head above the rest.)

I think Olympiad Maths teaches the much more important skills of critical thinking and problem solving.

True, but again it's not something that you can really teach, so much as have in the first place. The point of IMO is to nurture that natural talent.

[Over9000]

Someone solve the latest problem

[TrueTears]

Prove that the sum is irrational.

I've planned my approach in 2 ways:

1. Must show that the sum is not an integer.
2. Must show it is a zero of a monic polynomial.

But how to go about it?

Okay so had another look at this.

So to prove the sum is not an integer.



So,

Let

An overestimate for the sum would be

An underestimate for the sum would be

But since

Thus the sum is not an integer.

Use induction to prove it is a zero of a monic polynomial.

Base case:

Let the sum be written as

Let .

Thus



Thus is a zero.

Now for the inductive hypothesis, assume is true.

Thus is true.

Now we wish to prove that is also true.

We will denote this as .







Let this be a zero of a monic polynomial

So using the inductive hypothesis, is a zero , namely

so

Now what...? How do we expand that polynomial...?

yay with kamil's hint I got it.

Using binomial expansion we see terms with and those without it.

So

Where and represents polynomials containing .

Thus



QED.

[TrueTears]

Let . Find the remainder when is divided by .

So



Then what?