Posts Tagged with "Pen & Paper"

problem145

Project Euler 145: How many reversible numbers are there below one-billion?

Saturday, April 20, 2013

1 Comment

In Problem 145 of Project Euler we move away from Geometry and over to number theory again, with a problem which readsSome positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversibleHow many reversible numbers are there below one-billion (109)?This one is insanely easy to write a brute force method and that is the first thing I did. However, as we shall see there is a more analytic approach to the problem as well.

Continue reading...
Project Euler 79: By analysing a user's login attempts, can you determine the secret numeric passcode?

Project Euler 79: By analysing a user’s login attempts, can you determine the secret numeric passcode?

Saturday, January 14, 2012

8 Comments

Before even starting this problem I would like to say that I have solved the major part of Problem 79 of Project Euler by hand. The problem reads Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length. I actually just wanted to take a look at the data before thinking of a solution, and as I saw there were some multiple entries I wanted to remove them. So I imported the input file into a spread sheet and sorted them to remove the duplicate entries.

Continue reading...
Proving the fundamental lemma of Arithmetic

Proving the fundamental lemma of Arithmetic

Tuesday, November 1, 2011

0 Comments

Last time I blogged I wrote about why proofs are so difficult. This time we should try to prove something a little more complicated and see if we can get some of the thoughts behind the proof while doing it to see if it really requires that amount of insights or part of a proof can be done by using more or less common sense. My guess is that we can come far with common sense, but we at some point need to rely on some insights or methods we have seen before.

Continue reading...
Project Euler 68: What is the maximum 16-digit string for a "magic" 5-gon ring?

Project Euler 68: What is the maximum 16-digit string for a “magic” 5-gon ring?

Saturday, October 29, 2011

6 Comments

We have now been dealing with continued fractions for a good while, except for the last problem which was solved a good while ago. Problem 68 of Project Euler is completely different. It reads Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?

Continue reading...
Why are proofs so frustrating?

Why are proofs so frustrating?

Wednesday, October 12, 2011

0 Comments

I have often been sitting there swearing when I couldn't figure out to how to prove something and I know for certain I am not the only one. But why are proofs so difficult when they seem so easy when you read them? This post is about the softer side of proofs, to encourage you to not loose faith when you meet something you can't prove.I think the answer to the question lies in the fact that what we see when other presents a proof is the result. That doesn't mean the person constructing the proof didn't make them, but there is no reason to leave it in the final version, since it doesn't help in the argument that the statement is valid

Continue reading...
The pigeon hole principle

The pigeon hole principle

Wednesday, September 14, 2011

0 Comments

The pigeon hole principle is a counting argument stating something as simple as "if you have n items which are to be put into m < n boxes then there is at least 2 items in one of the boxes". My first comment on that was "well duh!", that is obvious, but it can actually be used to prove some less intuitive things.So an example if you have 10 balls which are to be put into 9 boxes then at least 1 of the boxes contains at least 2 balls (unless you drop one of them...). But what can we use it for. I will show one of my favourite examples of it which I do not find intuitive at first glance.

Continue reading...
Proof by mathematical induction

Proof method: Multidimensional induction

Wednesday, August 24, 2011

0 Comments

For the last couple of posts we have been dealing with mathematical induction, I will pick up where we left and continue on this topic one more time. Many introductions to proof by induction covers only the one dimensional case, here is an introduction to multidimensional induction. I will treat the two dimensional case in this post, but the expansion to n dimensions should be relatively easy. So for now we will assume that we have a statement P(m,n) which we need to prove.

Continue reading...
Project Euler 57: Investigate the expansion of the continued fraction for the square root of two.

Project Euler 57: Investigate the expansion of the continued fraction for the square root of two.

Saturday, August 20, 2011

10 Comments

I found Problem 57 of Project Euler to be a rather interesting problem, with more than one solution. The problem description readsIn the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?First thing I will present is a brute force solution, which for all practical purposes are fast enough. The second solution is a closed form approximation to the problem, so it can be solved as fast as you can punch the calculator.

Continue reading...
Proof by mathematical induction

Proof method: Strong Induction

Wednesday, August 10, 2011

10 Comments

As I promised in the Proof by induction post, I would follow up to elaborate on the proof by induction topic. Here is part of the follow up, known as the proof by strong induction. What I covered last time, is sometimes also known as weak induction.In weak induction the induction step goes: Induction step: If P(k) is true then P(k+1) is true as well.Strong induction expands that to: Induction step: If P(b), P(b+1), P(b+2)... P(k) is true then P(k+1) is true as well for some k > b.

Continue reading...
Proof by mathematical induction

Proof methods: Proof by mathematical induction

Wednesday, August 3, 2011

4 Comments

It has been a while since I last posted something about proof methods, but lets dig that up again and take a look at a fourth method. The first three were direct proof, proof by contradiction and contrapositive proofs. Proof by induction is a somewhat different nature.Induction usually has it's force on statements of the type "For all integers k greater than b, P(k) is true". For some statements we could prove it with some of the already covered methods, but for others it would mean that we had to prove an infinity of cases.The analogy I see everywhere and which I find quite fitting is to compare induction to dominoes (and I don't mean the pizza thing) which are lined up. As soon as you knock the first one over it knocks all the remaining once over one by one. Induction works in much the same way.

Continue reading...