CS4FN Advent – Day 11: the proof of the pudding… mathematical proof

A mathematical proof and a maths puzzle (but no hard sums, promise).

Thank you to everyone who’s been reading our Advent Calendar and said nice things about it and shared it with others. If you’re new to our pages you can see all our previous posts at the end.

We’re doing a post every day from the 1 – 25 December, loosely connected (if we can manage it!) to the theme suggested by the picture on the CS4FN Christmas Computing Advent Calendar.

Today’s picture on the Advent Calendar door is a Christmas pudding. Thanks to the phrase “the proof of the pudding is in the eating” (which I think means you have to eat all the chocolate puddings to know if they’re any good) I have chosen to match this picture with one of the CS4FN articles from the archives that is all about PROOF. Sadly we don’t seem to have any articles about pudding.

People sometimes pour brandy on Christmas puddings and set fire to it but this one has been iced instead and is not a fire hazard.

 

1. Proof without words

by Paul Curzon, QMUL. This article was originally published on the CS4FN website.

A graphical representation of squaring numbers

Graphic news images often help sway public opinion. Images of famine in Africa led to LiveAid, a massive relief effort in 1985. Images from war zones of civilians can be disturbing enough that war leaders lose or gain political support as a result (depending on who did the bad stuff). Images can have far more power than words to argue a case … to persuade.

Mathematical proofs are just arguments intended to persuade too. They aim to leave no element of doubt that some fact is true, not for emotional reasons but by logic. Mathematicians use mathematical notation – special symbols used in precise ways – to represent things in their proofs. That’s just a way of making sure the arguments are precise, with no room for doubt. Sometimes that can make them seem arcane and difficult to follow, though that’s only until you’ve learnt the mathematical language being used.

Mathematical proofs don’t have to use words and symbols though. In fact people have been presenting proofs as pictures at least since the Ancient Greeks, and just as with news images a diagrammatic proof can be much more persuasive. Sometimes just by looking at a diagram the truth of a fact can become obvious.

For example, here is a mathematical ‘fact’ we might want to prove:

“The square of any number is equal to the sum of consecutive odd numbers.”

That may sound a bit hairy. To get even hairier (if you aren’t a mathematician), we can write this precisely in mathematical notation as:

n2 = 1 + 3 + 5 + …+ (2n – 1)

Don’t worry about the notation though. Just look at the pictures. They show what we mean by the fact and should persuade you it’s true.

The square of a number can be drawn as a picture of dots in a square. In other words one way to work out 102, say, is to create a square of dots with sides of length 10 and then count the dots. That’s why it’s called ‘squaring’!

One way to draw the dots to make up a square is as follows. First draw one dot in the corner, then draw three dots in an L-shape round it, then draw 5 dots in an L-shape round that…and keep going. Add a new L-shape (including the first dot) 10 times, say, once for each dot along the side, and you get a square of size 10 with 100 dots altogether. Notice that at every step you still have a square, though. Also notice that each L-shape is 2 bigger than the one before. That’s because you can make it by adding one dot on the end of each arm of the last L-shape.

That means the number of dots in a square can be calculated by adding a sequence of odd numbers, one for each L-shape added: 1 + 3 + 5 + … As you add L-shapes you work up through squares of all sizes, so all squares can be made by adding odd numbers in this way.

We’ve just explained it in words, but actually it’s all in the picture, so it’s possible to see without needing the words at all.

At least it may be possible for a person to see perhaps, but what about a computer? Could a computer ‘see’ a proof from a diagram? Computers are now very good at helping humans do logical proof using mathematical notation – after all they work themselves by pushing ‘symbols’ about and following rules blindly, which is all logical proof is. Seeing a proof in a diagram is different altogether though…or is it?

Mateja Jamnik, of the University of Cambridge has been tackling this problem. In fact her system, DIAMOND, can already check diagrammatic proofs created by a person to see if they really do convince. With DIAMOND you could, for example, take a series of L shape pictures like ours above and build them up step-by-step giving squares of different sizes. The system can then pull out the structure of this step-by-step proof and from that automatically obtain the equation that it proves.

DIAMOND needs a person to develop a diagrammatic proof for it to check. In the future, if Mateja has her way, the computers will be devising new diagrammatic proofs themselves that then convince we humans.

2. Today’s puzzle – Logic and Proof FUNdamentals

(This text, by Paul Curzon, was originally published over several pages at the CS4FN website)

It is often said that being good at Maths is important for Computer Scientists. So what’s the link? Well a lot of the more obviously fun sides of maths are actually computer science too, like how to do puzzles such as Rubik’s Cubes, puzzles about weird and wonderful characters crossing rivers, how to win at strategy games, and doing Sudoku. The Maths you do in solving a Sudoku is the same kind of reasoning as that behind getting computer programs to work.

It is not so much the actual Maths you learn at school that is important. It is more that a similar way of thinking is important: logical reasoning. Doing Maths at school is one good way to start to learn how to think that way. So if you are good at Maths you will probably be good at Computer Science, though (using a bit of logical reasoning) that doesn’t mean the opposite follows of course.

Kakuro, Logic and Computer Science

To be a good computer scientist you have to enjoy problem solving. That is what it’s all about: working out the best way to do things. You also have to be able to think in a logical way: be a bit of a Vulcan. But what does that mean? It just means being able to think precisely, extracting all the knowledge possible from a situation just by pure reasoning. It’s about being able to say what is definitely the case given what is already known…and it’s fun to do. That’s why there is a Sudoku craze going on as I write. Sudoku are just pure logical thinking puzzles. Personally I like Kakuro better. They are similar to Sudoku, but with a crossword format.

What is a Kakuro?

A Kakuro is a crossword-like grid, but where each square has to be filled in with a digit from 1-9 not a letter. Each horizontal or vertical block of digits must add up to the number given to the left or above, respectively. All the digits in each such block must be different. That part is similar to Sudoku, though unlike Sudoku, numbers can be repeated on a line as long as they are in different blocks. Also, unlike Sudoku, you aren’t given any starting numbers, just a blank grid.

Where does logic come into it? Take the following fragment:

There is a horizontal block of two cells that must add up to 16. Ways that could be done using digits 1-9 are 9+7, 8+8 or 7+9. But it can’t be 8+8 as that needs two 8s in a block which is not allowed so we are left with just two possibilities: 9+7 or 7+9. Now look at the vertical blocks. One of them consists of two cells that add up to 17. That can only be 9+8 or 8+9. That doesn’t seem to have got us very far as we still don’t know any numbers for sure. But now think about the top corner. We know from across that it is definitely 9 or 7 and from down that it is definitely 9 or 8. That means it must be 9 as that is the only way to satisfy both restrictions.

A Kakuro for you to try

Here is a full Kakuro to try. The answer will be in tomorrow’s post.

Being able to think logically is important because computer programming is about coming up with precise solutions that even a dumb computer can follow. To do that you have to make sure all the possibilities have been covered. Reasoning very much like in a Kakuro is needed to convince yourself and others that a program does do what it is supposed to.

 

Printer friendly version as PDF.

 

3. Previous Advent Calendar posts

CS4FN Advent – Day 1 – Woolly jumpers, knitting and coding (1 December 2021)

 

CS4FN Advent – Day 2 – Pairs: mittens, gloves, pair programming, magic tricks (2 December 2021)

 

CS4FN Advent – Day 3 – woolly hat: warming versus cooling (3 December 2021)

 

CS4FN Advent – Day 4 – Ice skate: detecting neutrinos at the South Pole, figure-skating motion capture, Frozen and a puzzle (4 December 2021)

 

CS4FN Advent – Day 5 – snowman: analog hydraulic computers (aka water computers), digital compression, and a puzzle (5 December 2021)

 

CS4FN Advent – Day 6 – patterned bauble: tracing patterns in computing – printed circuit boards, spotting links and a puzzle for tourists (6 December 2021)

 

CS4FN Advent – Day 7 – Computing for the birds: dawn chorus, birds as data carriers and a Google April Fool (plus a puzzle!) (7 December 2021)

 

CS4FN Advent – Day 8: gifts, and wrapping – Tim Berners-Lee, black boxes and another computing puzzle (8 December 2021)

 

CS4FN Advent – Day 9: gingerbread man – computing and ‘food’ (cookies, spam!), and a puzzle (9 December 2021)

 

CS4FN Advent – Day 10: Holly, Ivy and Alexa – chatbots and the useful skill of file management. Plus win at noughts and crosses – (10 December 2021)

 

CS4FN Advent – Day 11: the proof of the pudding… mathematical proof (11 December 2021) – this post

 

 

 

CS4FN Advent – Day 8: gifts, and wrapping – Tim Berners-Lee, Right to Repair & another computing puzzle

Tim Berners-Lee, Right to Repair, and a maths puzzle.

Welcome to Day 8 of our CS4FN Christmas Computing Advent Calendar. It features a computing-themed post every day in December until Christmas Day. All the blog posts in the Advent Calendar so far have been inspired by the picture on the ‘door’ – and today’s post is also inspired by the picture, which is of a Christmas present.

Presents are something you give freely to someone, but they’re also something you hide behind wrapping paper. This post is about a gift and also about trying to uncover something that’s been hidden. Read on to find out about Tim Berners-Lee’s gift to the world, and about the Restart Project who are working to stop the manufacturers of electronic devices from hiding how people can fix them. At the bottom of the post you’ll find the answer to yesterday’s puzzle and a new puzzle for today, also all of the previous posts in this series. If you’re enjoying the posts, please share them with your friends 🙂

A present in blue wrapping paper with a large green bow.

 

1. “This is for everyone” – Tim Berner’s Lee

Audiences don’t usually cheer for computer scientists at major sporting events but there’s one computer scientist who was given a special welcome at the London Olympics Opening Ceremony in 2012.

Tim Berners-Lee invented the World Wide Web in 1989 by coming up with the way for web pages to be connected through links (everything that’s blue and clickable on this page is a link). That led to the creation of web browsers which let us read web pages and find our way around them by clicking on those links. If you’ve ever wondered what “www” means at the start of a link it’s just short for World Wide Web. Try saying “www” and then “World Wide Web” – which takes longer to say?

Tim Berners-Lee didn’t make lots of money from his invention. Instead he made the World Wide Web freely available for everyone to use so that they could access the information on the web. Unless someone has printed this onto paper, you’re reading this on a web browser on the World Wide Web, so three cheers Tim Berners-Lee.

In 2004 the Queen knighted him (he’s now Sir Tim Berners-Lee) and in 2017 he was given a special award, named after Alan Turing, for “inventing the World Wide Web and the first web browser.”

Below is the tweet he sent out during the Olympics opening ceremony.

 

 

Further reading

The Man Who Invented The Web (24 June 2001) Time
“I Was Devastated”: Tim Berners-Lee, the Man Who Created the World Wide Web, Has Some Regrets (1 July 2018) Vanity Fair

 

2. Do you have the right to repair your electronic devices?

A ‘black box’ is a phrase to describe something that has an input and an output but where ‘the bit in the middle’ is a complete mystery and hidden from view. An awful lot of modern devices are like this. In the past you might have been able to mend something technological (even if it was just changing the battery) but for devices like mobile phones it’s becoming almost impossible.

People need special tools just to open them as well as the skills to know how to open them without breaking some incredibly important tiny bit. Manufacturers aren’t always very keen for customers to fix things. The manufacturers can make more money from us if they have to sell us expensive parts and charge us for people to fix them. Some even put software in their devices that stops people from fixing them!

The cost of fixing devices can be very expensive and in some cases it can actually be cheaper to just buy a new device. Obviously it’s very wasteful too.

The Restart Project is full of volunteers who want to help everyone fix our electronic devices, and also fix our relationship with electronics (discouraging us from throwing away our old phone when a new one is on the market). The project began in London but they now run Repair Parties in several cities in the UK and around the world. At these parties people can bring their broken devices and rather than just ‘getting them fixed’ they can learn how to fix their devices themselves by learning and sharing new skills. This means they save money and save their devices from landfill.

Restart also campaign for people to have the Right to Repair their own devices. They want a change in manufacturing laws to make sure that devices are designed so that the people who buy and use them can easily repair them without having to spend too much money.

 

3. Today’s puzzle

A more mathematical puzzle today. Rather than writing letters into the kriss-kross you need to write the equation and its answer.

For example 5 + 2 = as the clue gives you 5 + 2 = 7 as the answer which takes up 5 characters (note that the answer is not “seven” which also takes up 5 characters!). There are several places in the puzzle where a 5 character answer could go, but which one is the right one? Start with the clues that have only one space they can fit into (the ones with 7 symbols and 9 symbols) then see what can fit around them.

This puzzle was created by Daniel, aged 6. For an explanation of the links to computer science and how these puzzles can be used in the classroom please see the Maths Kriss-Kross page on our site for teachers. Note that the page does include the answer sheet, but no cheating, we’ll post the answer tomorrow. Also, if you don’t have a printer you can use the editable PDF linked on that page.

4. Answer to yesterday’s puzzle

 

The creation of this post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.

 

5. Previous Advent Calendar posts

CS4FN Advent – Day 1 – Woolly jumpers, knitting and coding (1 December 2021)

 

CS4FN Advent – Day 2 – Pairs: mittens, gloves, pair programming, magic tricks (2 December 2021)

 

CS4FN Advent – Day 3 – woolly hat: warming versus cooling (3 December 2021)

 

CS4FN Advent – Day 4 – Ice skate: detecting neutrinos at the South Pole, figure-skating motion capture, Frozen and a puzzle (4 December 2021)

 

CS4FN Advent – Day 5 – snowman: analog hydraulic computers (aka water computers), digital compression, and a puzzle (5 December 2021)

 

CS4FN Advent – Day 6 – patterned bauble: tracing patterns in computing – printed circuit boards, spotting links and a puzzle for tourists (6 December 2021)

 

CS4FN Advent – Day 7 – Computing for the birds: dawn chorus, birds as data carriers and a Google April Fool (plus a puzzle!) (7 December 2021)

 

CS4FN Advent – Day 8: gifts, and wrapping – Tim Berners-Lee, black boxes and another computing puzzle (8 December 2021) – this post