Pen & Paper

Contrapositive proofs – part 2

Contrapositive proofs – part 2

Once I finished up the post on contrapositive proofs I spend the better part of an hour feeling I wasn’t quite finished with the topic. I still had a couple of things to explore. The first one is a contrapositive proof that puzzled me, the other thing is De Morgan’s Laws which tells us how to negate a statement. Continue reading →

Posted by Kristian in Math, 3 comments
Proof Method: Contrapositive proof

Proof Method: Contrapositive proof

On my journey to improve my mathematical rigour I have covered direct proofs and Proof by Contradiction. In this post I will cover the third method for proving theorems.

Reading up on different methods for proving things I realized that a contrapositive proof is a really clever thing to used and often a better way to prove things than a proof by contradiction. However, I love the proof by contradiction so much that I wanted to cover it first. Continue reading →

Posted by Kristian in Math, 10 comments
Proof method: Proof by contradiction

Proof method: Proof by contradiction

I was first presented with a proof by contradiction while I was studying Discrete event systems in Canada. And I was puzzled about it most day. I came to really like it though.

When we want to prove something by contradiction we assume that the statement we want to prove is false and then show that it leads to a logic contradiction at some point, therefore the statement must be true. Don’t be confused just yet. I will come to the examples.

Proof by contradiction is not limited to conditional statements like the the direct proof is. So we don’t need to have a proposition on the form if Q then P. Continue reading →

Posted by Kristian in Math, 11 comments

Theorems, Lemmas and Other definitions

I was asked by an avid reader (I always wanted to write that), to cover the different terms in mathematics regarding proofs, so here is a post which covers some of the terms which I think we will see a lot more of. Continue reading →

Posted by Kristian in Math, 4 comments

Proof method: Direct Proof

In my first post on my journey for improving my mathematical rigour I said that I would go through a few different techniques for conducting proofs.

The first one I want to dabble into is direct proofs.  This is the “simplest” method and sometimes it can seem that the proof isn’t there at all.

It will often go something like “if a then b”. So using some definition of a, we can show that b follows as a direct consequence through an unbroken line of logical arguments such that

a -> … -> b

Lets try it out on some sample problems Continue reading →

Posted by Kristian in Math, 3 comments

Improving my mathematical rigour

I have reached a point in my mathematical journey where I feel the need to learn how to make sound arguments for the validity of a mathematical claim. Or in other words, I want to learn more on how to prove things.

The path I took through the Danish educational system has never dealt much with mathematical proofs, but rather on how to apply the mathematics we have learned. I have developed an intuition for mathematics in some areas. But I lack mathematical rigour, so I often time have to resolve to hand waving instead.

The usual approach to learning proving techniques is through a taught topic where you are presented with some proofs. Through that you will expand your toolbox and learn how to do proofs. However, I would through a series of blog posts dabble into how to prove mathematical things and study different techniques.

Ben Tilly pointed me through his blog – random observations – to a document he wrote on how to do proofs. It has a flow chart which you can also see to the below, which I think is a very thorough way to ensure that you get through the proof. It doesn’t say anything about how to actually make your arguments, but it helps you break down the problem.

Let me spend the rest of this blog post to go through the flow chart and interpret it. Continue reading →

Posted by Kristian in Math, 0 comments

Project Euler 43: Find the sum of all pandigital numbers with an unusual sub-string divisibility property

When I first saw pandigital numbers I thought it was just a curious thing that we would visit once. I was wrong as Problem 42 of Project Euler is also about a special group of pandigital numbers. The problem reads

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

We will take two different approaches to this. First We will explore the brute force of generating all permutations and after that we will use the divisibility requirements to limit the number of permutations we have to explore. Continue reading →

Posted by Kristian in Project Euler, 18 comments

Project Euler 40: Finding the nth digit of the fractional part of the irrational number

I am currently sitting in a train, and writing this post since I solved problem 40 in Project Euler using pen & paper waiting for my computer to start up and get online.  It is not a terribly difficult problem to answer, at least it wasn’t for me. The problem reads

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021…

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000

Continue reading →

Posted by Kristian in Project Euler, 12 comments

Project Euler 29: How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Problem 29 of Project Euler reads

Consider all integer combinations of ab for 2 <= a <= 5 and 2 <= b <= 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 <= a <= 100 and 2 <= b <= 100?

It is fairly trivial to realise that the solution is somewhere below 99*99 = 9801, using combinatorics. Based on the amount of possible combinations it should also be fairly easy to implement a brute force solution in C#. That is the first solution we will elaborate on, but I have a pen and paper method as well, where we will use logic to deduce the solution. Continue reading →

Posted by Kristian in Project Euler, 18 comments