Need help in this homework

In this problem, you will learn how to perform an impressivemagic trick. As all tricks, once you understand it, it becomes lessimpressive. But then you can impress other people with it. And herethe trick is… mathematics.

The trick works as follows: the mathemagician gives you a pieceof paper with fourteen boxes. He asks you tochoose two secret numbers between 1 and9 and to write them in the first two boxes. Then yourecursively fill in the next boxes by computing the sum of theprevious two boxes each time. You do all this without showing it tothe mathemagician. See the below figure for an example where thetwo secret numbers are 7 and 3.

7

3

10

13

23

36

59

95

154

249

403

652

1055

1707

In the end, the mathemagician asks you for the last two numbers(1055 and 1707 in the example)…and he is able to guess the firsttwo secret numbers that you used in few seconds. Magic!

Let’s first make sure that you understand the principle.

1. Write your Student ID. [0.5pts] J
2. Fill in the below table as in the magic trick, by choosing forthe first two boxes the last two digits of your Student ID (if oneof the digits is 0 choose any number between 1 and 9 that youlike). [3 pts]

6

4

10

14

24

38

62

100

162

262

424

686

1110

1796

Now, how is it possible to guess the first two numbers given thelast two?

The numbers written in the boxes form a sequence, and theyfollow a recurrence relationship that we saw in class, namely… theFibonacci sequence (sorry no points for that, I gave theanswer).

3. If we denote the first two numbers by a and b (the first twoelements of the sequence), it is possible to express any of thefollowing elements as a linear function of a and b. Express thesesteps in the following table (I put them in column instead of rowto give you more space to write). [3pts]

From the mathemagician perspective, if we denote the last twoelements (the last two rows) by c and d respectively, then we havea system of two equations with two variables. The unknown are a andb, while c and d are given to the mathemagician.

1. Solving such a system is easy:
   1. Express a and b as functions of c and d [2pts]
   2. Verify that, if c= 1055 and d=1707, you obtain a=7 andb=3 [1 pt]
   3. Verify also that it works with your personal example with thestudent ID (question b)) [1 pt]

This is a nice way to solve this trick, but it requires acalculator to find a and b in the last step (I doubt any of you isable to quickly perform the required computation without acalculator). And a mathemagician using a calculator is notimpressive at all, it looks like the calculator is doing all thework. So the mathemagician need to do the same…withoutcalculator!

For this, we need another beautiful mathematic result. You allknow about modular arithmetic (yes you do, even if you don’t knowthat you do). At least you have seen it in computer programing, asthis is a classical programing exercise.

As a reminder we say that two numbers a and b are equal (orcongruent) modulo n iff n divides (inthe sense of an integer division) the difference a-b. We write:

a= b [n] ?n|(a-b)

For example:

2=4 [2], 2=5 [3], 13 = 23 [5] and so on…

Of course we have many elements that are equal modulo n, as wehave a loop of size n. For example if n=5, we have:

1=6=11=16=21 [5] and many more.

As a result, for any integer, we can find a representativemodulo n which is between 0 and n-1

For example:

23=3 [5], 36=0 [6], 47=2 [9] and so on…

This is exactly what you obtain when using the % operator inpython.

2. Let’s see if you understood this: what is your student IDmodulo 2? modulo 5? modulo 10? [1.5 pts]

What is the link with the mathemagician trick?

Don’t be so impatient!

You know since long time (hopefully) how to verify quickly thata number is a multiple of 9 or not. You simply add the digits ofyour number and if the result is divisible by 9, then the number isdivisible by 9 otherwise it is not.

For example, 458 is not divisible by 9 because the sum of itsdigits is 4+5+8= 17 which is not divisible by 9.

On the contrary, 459 is divisible by 9 because the sum of itsdigits is 4+5+9=18 which is divisible by 9 (if you didn’t knowthat, you just learned a new trick, isn’t it beautiful?)

3. Use this trick to check whether your Student ID is divisible by9 or not (show the steps). Note that if the sum of the digits ofyour Student ID is too big to be able to easily decide if it isdivisible by 9 you can repeat the trick and compute the sum of thedigits of the sum of the digits of your Student ID. [1pt]

Now this “trick” follows from a more general property of thedecimal number system, which is that any number is equal to the sumof its digits modulo 9.

1. Check that your Student ID is equal to the sum of its digitsmodulo 9. For this, subtract from your Student ID the sum of itsdigits, and then use the previous trick to check that the result isdivisible by 9. [1 pt]
2. Give a proof of this theorem for any number of three digits.HINT: remember what is the representation of a number in thedecimal system (base 10). [*3 pts]

Back to the mathemagician trick!

We now know that the sum of the digits of a number is equal tothe number modulo 9.

So we can compute the sum of the digits of any element in thesequence by computing the remainder modulo 9. For example if anelement happened to be 21a + 34b, the sum of its digits would beequal to 3a+7b. This follows from the fact that 21=3 [9] and 34=7[9].

1. Compute the sum of digits of elements of the sequence that youexpressed in question c) (the same elements but modulo9): [3 pts]

If you did things properly, you shouldget two very simple expressions in the last two boxes linking a andc modulo 9 and c and d modulo 9.

Remember that this means that theseexpressions are linking the sum of the digits of a (respectively b)to the sum of the digits of c (respectively d). But

you also know that a and b are bothbetween 1 and 9 (as requested by the mathemagician).

1. So now you should have understood the trick to get a and b:
   1. Summarize how to obtain a and b after all this [2pts]
   2. Apply it to the case given in the example when c=1055 andd=1707 [1 pt]
   3. Apply it to the case of your Student ID (questionb) [1 pt]
   4. Apply it to find the values of a and b when c=898 andd=1453 [1 pt]

Now you can impress people around you…without even acalculator!

And if you want a final trick before leaving, you can ask theaudience to compute the ratio between the last two numbers theyobtained (basically computing d/c). They will do it with acalculator of course, but you can directly tell them that theresult is around 1.618! Don’t repeat this last trick though,because the result is always the same so it is not impressive whenrepeated. Do you know why the result is always the same?