Developing the basics: programming myself, post thirteen

David Watson

Problem-solving strategies

<< Read the previous post from the series     Read the next post in the series >>

So we are really now starting to embark on a whole new discipline that comes with programming. Logic and problem-solving. We now have enough of how and what we can do with with the code behind us that we can work out how to use the code, what different things do in the code, or if we don’t know them off by heart yet, we at least know how to look up answers and adapt and improve the results. But it is time to really stand on our own two feet and work through problems from scratch and solve them for ourselves.

The adaptive Python PyCharm Edu course from Stepik promises this. It’s a system to practice our coding and problem-solving abilities in an environment that is a bit more forgiving as we can get hints from the course. But to prepare for this next stage, let’s have a look at some problem- solving strategies and techniques that may come in useful.

Problem-solving can only be improved by you guessed it… problem-solving. If you struggle to solve problems, you are not alone. Anytime you come up against some intellectual task that can cause you a feeling of pain; this is your body’s response to really activating your brain. It hurts, it is frustrating, it makes your blood pressure rise, why even bother then, why not just bathe our brains in a nice relaxing bath of BuzzFeed articles? It is time to exercise your brain! Let’s start with a light warm-up.

Without a calculator work out the answer to 27 x 13.

So there is no set way of solving this: for me, I would break it into parts; first work out 25 x 10, then add 75 to that then add a final 26. Basically, 25 x 13 + 26 as I find 25 a much easier number to deal with. An alternative would be to times 27 by 10 to get 270, then times 27 by 3 and add the two lots together. You could also do it with the long multiplication you learned at school. 3 x 7 carry the 20, 3 x 20 + (the 20 from before), then the second row, add a 0 for the digits as we are dealing with 10’s now, 1 x 7 then 1 x 200, giving you two rows 81 and 270, then you just need to add them together and boom, same answer.

By working this out, notice how you are feeling, there is probably a certain amount of physical discomfort. This is because you are activating your system 2, a concept covered in Thinking, Fast and Slow, by Daniel Kahneman. You have two systems of thinking: system 1 and system 2. System 1 is the fast system; it’s pretty much automatic and doesn’t require too much effort, for example when you solve 2 + 2 — a different kind of effort than the calculation above. System 1 will try to kick in first, as it takes the least effort and so your brain prefers it. And then there’s system 2 which actually thinks about things.

Let’s try another warm-up:

A bat and ball cost $1.10.

The bat costs $1 more than the ball.

How much does the ball cost?

Hint: it is not 10c. If the ball cost ten cents, the bat would cost $1.10 and so the total cost would be $1.20.

What is the point of this? Well, the first point is – I thought it was cool. The second point is, there is a feeling you get from activating the second system and logically working out solutions, it is not always comfortable, and it is what you should try to get used to as you will come up against it a lot in real problem-solving as you are going to have to use your system 2… a lot.

So on that note let’s take a look at some problem-solving strategies which whether you love them or not, might someday come in handy.

The Box principle

Dirichlet’s box principle states that if n+1 pearls are put into n boxes, then at least one box has more than one pearl. Pretty obvious, huh? As another real-life example, if there are three people in a room, at least 2 are going to be the same sex (in theory that is anyway).

You can recognize if you can use the box principle if the problem has a finite set, it sometimes works with infinite sets too but if you know how many in a set then this principle might be possible to use.

Problem:

In a tournament with n players, everybody plays with everybody else exactly once. Prove that during the game there are always two players who have played the same number of games.

Spoiler Solution:

A player (pearl) goes into game (box) #i if they have i games. We have n players, and n games numbered 0, 1 , 2, 3, … , n-1. But the games with the numbers 0 and n-1 cannot both be occupied. So there is at least one game with more than one player.

The Invariance Principle

This problem-solving strategy is built on the principle of looking for what doesn’t change when an algorithm is repeatedly performed. So basically it can be used to quickly suss out whether a result is even achievable.

Here’s an example question where the invariance principle can be applied…

Problem:

A dragon has 100 heads. A knight can cut off 15, 17, 20, or 5 heads with a single blow of his sword. Immediately after, 24, 2, 14, or 17 new heads, respectively, grow back on its shoulders. If all heads are chopped off, the dragon dies. Can the dragon ever die?

Spoiler Solution (resist the urge to read it before you give the problem a go with your system 2!):

Look at the net change in the number of heads with each blow. If we cut off 15 heads and 24 grow back, the net change is +9. Similarly, -17 and +2 result in a net change of -15. Similarly, -20 +14 = -6, and -5 +17 = +12. The trick is to notice how all four numbers, +9, -15, -6 and +12, are divisible by 3. Another way to say it would be that the number of heads is invariant mod 3. The final observation we need to make is that 100 is not evenly divisible by 3. This means that no matter how many times or which blows we make, the dragon will not die, and will plague the village for years, so knowing this you know that it’s best to use a strong poison or White Walker magic.

The Extremal Principle

Also known as the variational method, this principle is good for proving the existence of an object with certain properties. The principle tells us to pick an object which maximizes or minimizes some function. The resulting object is then tested for the desired property.

Problem:

Imagine a chessboard that contains a positive integer in each square. If the value in each square is equal to the average of its four neighbors to the north, south, west, and east, prove the values in all the squares are equal.

Solution:

Consider the square containing the minimal value. Then its four neighbors must all have this minimal value. Similarly, their neighbors must also have this minimal value, and so on and so on to infinity and beyond. Thus, every square in the chessboard has the same value.

One more problem:

Every participant of a tournament plays with every other participant exactly once. No game is a draw. After the tournament, every player makes a list with the names of all players, who

1. Where beaten by them (the player)
2. Were beaten by the players beaten by them

Prove that the list of some player contains the names of all the other players.

Solution:

Let ‘A’ be the participant that has won the most number of games. If ‘A’ doesn’t have the property of this problem (won all of the games played), then there would be another player B, who has won against A and against all players beaten by ‘A’. So ‘B’ would have won more times than ‘A’. This contradicts the choice of ‘A’. So what you are doing here is testing the highest possible results (the extremal) which is the top winner winning all their games, if they cant meet this then the chances of anyone else doing it also falls down.

Enumerative Combinatorics

Enumerative combinatorics is an area of problem-solving the number of ways certain patterns can be formed. A better word for this type of problem then is “possible combinations” or even simpler “finding patterns”.

If you have ever watched the film Good Will Hunting, well, “It’s not your fault” as it is a pretty good film about how construction workers all secretly love solving the most complicated math problems while they scrub floors; if I understood the meaning behind the film correctly. What you see on the chalkboard in the hallway is not a rubbish stick spider picture but Cayley’s formula for the number T_n of labeled trees with n vertices.

Problem – Cayley’s formula for the number T_n of labeled trees with n vertices:

A tree is a non-orientated graph without a cycle. It is called labelled if its vertices are numbered… Yep, I went there. If you think that is hard to understand, try and understand the Wikipedia article on it: https://en.wikipedia.org/wiki/Cayley%27s_formula. What it is basically saying if I understand correctly is how many ways can a tree be labeled in different combinations. So to work it out we need to make a formula for T_n .

There is only one way to label a tree with one vertex, and the same for one with two vertices as the tree is not orientated. But for three points there are three possible ways of labeling, for four points there are 16 ways to label 12 different ways of labeling the chain and then four ways of labeling the star.

So then if we have five potential points there are 60 ways to label the chain differently, a star can be done five ways, then there is a way to intersect the points which comes to 60 different combinations. So this means there are 60 + 60 + 5 = 125 ways.

So if we suppose that this goes on indefinitely, we can try and work out the formula.

So it in each case is going up by one more times of itself. 3, 4 x 4, 5 x 5 x 5. So the guess would be 6 x 6 x 6 x 6. Get your notebook out and start trying to see if this holds for 6… it does.

Solution:

But unfortunately we need to make this into an actual equation so using my ancient math from  school – this means 6 to the power of 4. 6⁴, but now we have to make a universal equation, so it becomes T_n = n^n-2. And you can see for each number this equation actually works and we can sit and bask in our glory of solving a problem, why is the problem solved? Because you now have an algorithm to solve this question regardless of what input you have.

To really problem solve we should probably know about all the other points conducive to problem-solving and their relationships with problems and how they can be approached to resolve problems. But, life is short, if I run into trouble, I will google it and hope someone much smarter than myself has an answer.

Also if you want to get into the real nitty gritty and be completely well rounded in problem-solving you are going to have to know how to use and work with the following kinds of fun logical types of things:

Functional equations
Sequences
Polynomials
Inequalities
Geometry

But these are future problems.

Thinking differently

For now, let me leave you with one final problem:

Without letting your pencil leave the paper, draw four straight lines which go through all the following nine dots?

Impossible right? Looking at the problem you may infer that there are limits that have been put on you, like that you need to keep all the lines within the confines of the box that has been drawn, but like all problems in life, the limitations on how you approach a solution are all self-imposed if it works, it is not wrong. Right?

Solution:
Think outside the box, literally.

The problem is not the problem.

The problem is your attitude about the problem. – Captain Jack Sparrow