### All Weeks Mathematical Thinking in Computer Science Quiz Answers

### Mathematical Thinking in Computer Science Week 01 Quiz Answer

#### Quiz 01: Tiles, dominos, black and white, even and odd

Q 1. Consider the following shape that we want to tile by 1\times 21×2 tiles. (This means that the tiles should be inside the green zone and cover the entire green zone without overlaps)

Please discuss this quiz here.

Is it possible if we cover the cell “a” by a horizontal tile?

Answer:

**No**

Q 2. Consider the following shape (the same as in the previous question) that we want to tile by 1\times 21×2 domino tiles. (This means that the tiles should be inside the green zone and cover the entire green zone without overlaps).

- No, it is not possible
**Yes, it is possible**

Q 3. A cell is *good* if the board without this cell can be tiled by domino 1\times 21×2 tiles. What is the number of good cells? (Just write a number in the answer field)

(In other words, you want to delete one cell in such a way that the rest can be tiled. How many options do you have? For example, if you delete the left upper corner, you can tile the rest using vertical tiles in the first column and horizontal tiles elsewhere. So the left upper corner is good. Some other cells (e.g., the other corners) are good, but not all. You need to count the good cells.)

Answer:

**13 because of 13 black cells**

#### Puzzle: Tile a Chessboard

Q 1. Tile the chessboard with 1×2 dominoes! Depending on the complexity level, the chessboard may have some missing squares (shown by rose color) that should not be covered by dominos.

In this (and every other) puzzle, please press the Submit button in the end (otherwise, you grade would not be recorded).

Q 2. Tile the chessboard with one missing cell with 1×2 dominoes.

Q 3.Tile the chessboard with two missing cells with 1×2 dominoes.

#### Puzzle: Two Congruent Parts

Q 1. Cut the figure into two parts of the same shape and size by a line the goes along cell edges. To make a cut along a cell side, click near its center.

Recall that it is important to press the Submit button in the end.

Q 2. Cut the figure into two parts of the same shape and size by a line the goes along cell edges. To make a cut along a cell side, click near its center.

Q 3. Cut the figure into two parts of the same shape and size by a line the goes along cell edges. To make a cut along a cell side, click near its center.

Note that the middle cell is missing in this figure, hence one cannot cut along its edges.

#### Puzzle: Splitting

Q 1. Change signs by clicking on them to get zero as a result.

Q 2 . Change signs by clicking on them to get zero as a result.

### Mathematical Thinking in Computer Science Week 02 Quiz Answer

#### Puzzle: Magic Square 3 times 3

Q 1. Put numbers 1,2,3,4,5,6,7,8,9 (each should be used once) into 3 times 3 square to make the same sum in all rows, all columns and both diagonals.

#### Puzzle: Different People Have Different Coins

Q 1. Person A has an unlimited number of 7-florin coins, person B has an unlimited number of 13-florin coins. How A can pay 5 florins to B?

#### Puzzle: Free Accomodation

Q 1. A town has three hotels. You have 10 vouchers for one-night stay for the first hotel, 15 for the second one, and 20 for the third one. The rules do not allow you to use vouchers for two consecutive nights in one hotel. Can you use them all for 10 + 15 + 20 = 45 consecutive nights changing the hotels each night?

Q 2. A town has three hotels. You have 10 vouchers for one-night stay for the first hotel, 15 for the second one, and 30 for the third one. The rules do not allow you to use vouchers for two consecutive nights in one hotel. Can you use them all for 10 + 15 + 30 = 55 consecutive nights changing the hotels each night?

#### Is there…

Q 1. Find a 5-digit integer N*N* such that N^2*N*2 starts with 27182.

Answer: **3x+(3-1)**

Q 2. You have 25 vouchers for hotel A and 20 vouchers for hotel B. What is the maximal number of vouchers for hotel C that you can use if you are not allowed to spend two consecutive nights in the same hotel (and if you have no other place to sleep)?

Answer: **4y+(4-1)**

Q 3. There are some books on the table. If you group them by 3, you get some number of full groups and 2 books remain; if you group them by 4, you get some number of full groups and 3 books remain; if you group them by 5, you get some number of full groups and 4 books remain. What is the number of books on the table, if it is less than 100?

Answer : **5z+(5-1)**

Q 4. In some country there are 12-, 20-, and 30-florin coins only. One person in this country wants to pay some amount to other person in this country. What is the minimal amount that can be paid if both people have many coins of each type?

Answer: **all contains -1. So 60 – 1 = 59**

#### Maximum Number of Two-digit Integers

Q 1. There are 90 cards with all two-digit numbers on them:

10,11,12,\dotsc,98,99.10,11,12,…,98,99.

A player takes some of these cards simultaneously. For each card taken she gets $1. However, if the player takes two cards that add up to 100 (say, 23 and 77), she loses all the money. How much could she get?

In mathematical language: What is the maximum number of two-digit integers (10,11,…,99) that one can select satisfying the following condition: no two different selected integers have sum 100?

Answer: **50**

#### Maximum Number of Rooks on a Chessboard

Q 1. Place the maximum number of rooks such that no two attack each other. Click on a cell to add or remove a rook.

#### Maximum Number of Knights on a Chessboard

Q 1. Place the maximum number of knights so that no two of them attack each other

#### Maximum Number of Bishops on a Chessboard

Q 1.Place the maximum number of bishops so that no two attack each other.

#### Subset without x and 2x

Q 1. Choose the maximal number of integers among 1..50 that can be selected if we are not allowed to select n and 2n at at same time

#### Puzzle: Maximum Number of Two Digit Integers

Q 1. There are 90 cards with all two-digit numbers on them:

10,11,12,\dotsc,98,99.10,11,12,…,98,99.

A player takes some of these cards simultaneously. For each card taken she gets $1. However, if the player takes two cards that add up to 100 (say, 23 and 77), she loses all the money. How much could she get?

In mathematical language: What is the maximum number of two-digit integers (10,11,…,99) that one can select satisfying the following condition: no two different selected integers have sum 100?

#### Puzzle: N Queens

Q 1.Place **2** queens such that no two attack each other. Click on a cell to add or remove a queen.

Q 2. Place **3** queens such that no two attack each other. Click on a cell to add or remove a queen

Q 3. Place **4** queens such that no two attack each other. Click on a cell to add or remove a queen.

Q 4. Place **5** queens such that no two attack each other. Click on a cell to add or remove a queen.

#### Puzzle: 16 Diagonals

Q 1. By clicking on squares, draw **6** diagonals that do not touch each other.

Q 2. By clicking on squares, draw **10** diagonals that do not touch each other.

Q 3. By clicking on squares, draw **16** diagonals that do not touch each other.

#### Number of Solutions for the 8 Queens Puzzle

Q 1. Modify the code considered in the lectures to find out the number of solutions to the 8 queens puzzle. For example, as was explained in the videos, for the 4 queens puzzle there are 2 solution

Answer: Comment the Answer.

### Mathematical Thinking in Computer Science Week 03 Quiz Answer

#### Largest Amount that Cannot Be Paid with 5- and 7-Coins

Q 1. Imagine we have only 5- and 7-coins. One can prove that any large enough integer amount can be paid using only such coins. Yet clearly we cannot pay any of numbers 1, 2, 3, 4, 6, 8, 9 with our coins. What is the maximum amount that cannot be paid?

Answer: **23**

#### Pay Any Large Amount with 5- and 7-Coins (Optional)

Q 1. Develop a Python method change(amount) that for any integer amount in the range from 24 to 1000 returns a list consisting of numbers 5 and 7 only, such that their sum is equal to amount. For example, change(28) may return [7, 7, 7, 7], while change(49) may return [7, 7, 7, 7, 7, 7, 7] or [5, 5, 5, 5, 5, 5, 5, 7, 7] or [7, 5, 5, 5, 5, 5, 5, 5, 7].

To solve this quiz, implement the method change(amount) on your machine, test it on several inputs, and then paste your code in the field below and press the submit quiz button. Your submission should contain the change method only (in particular, make sure to remove all print statements).

#### Puzzle: Hanoi Towers

Q 1. Place blocks in the same order to another tower.

Q 2. Place blocks in the same order to another tower.

Q 3. Place blocks in the same order to another tower.

#### Puzzle: Two Cells of Opposite Colors

Q 1. You are given 20 black and white cells. The leftmost one is white, the rightmost one is black, the colors of all other cells are hidden. You can reveal the color of a cell by clicking on it. Your goal is to find two adjacent cells of different colors by using at most 5 clicks.

#### Two Cells of Opposite Colors: Feedback

Q 1. Please help us to improve the course by leaving a feedback on the previous puzzle.

**I was able to solve the puzzle myself.**- I have solved the puzzle after reading the hint.
- I still have no idea how to solve it.

#### Puzzle: Guess a Number

Q 1. Find an unknown integer **1 ≤ x ≤ 3** by asking **2** questions “Is x = y?” (for any 1 ≤ y ≤ N ). When you ask such a question, simply enter “y” instead of “Is x=y?” Your opponent will reply either “Yes”, or “x < y”, or “x > y.” (Your goal is to get answer “Yes” at some moment.)

Answer:

Q 2. Find an unknown integer **1 ≤ x ≤ 15** by asking **4** questions “Is x = y?” (for any 1 ≤ y ≤ N ). When you ask such a question, simply enter “y” instead of “Is x=y?” Your opponent will reply either “Yes”, or “x < y”, or “x > y.”

Answer:

Q 3. Find an unknown integer **1 ≤ x ≤ 127** by asking **7** questions “Is x = y?” (for any 1 ≤ y ≤ N ). When you ask such a question, simply enter “y” instead of “Is x=y?” Your opponent will reply either “Yes”, or “x < y”, or “x > y.”

Answer:

Q 4. Find an unknown integer **1 ≤ x ≤ 2 097 151** by asking **21** questions “Is x = y?” (for any 1 ≤ y ≤ N ). When you ask such a question, simply enter “y” instead of “Is x=y?” Your opponent will reply either “Yes”, or “x < y”, or “x > y.”

Answer:

#### Puzzle: Local Maximum (Optional)

Q 1. Given a sequence of **4** integers, find a local maximum by revealing at most **3** of them. An element is called a local maximum if it is not smaller than all its neighbors.

Answer:

Q 2. Given a sequence of **8** integers, find a local maximum by revealing at most **5** of them. An element is called a local maximum if it is not smaller than all its neighbors.

Answer:

Q 3.Given a sequence of **16** integers, find a local maximum by revealing at most **7** of them. An element is called a local maximum if it is not smaller than all its neighbors.

Answer:

#### Puzzle: Connect Points

Q 1. Connect some of the points with segments such that each point is connected with 5 other points

Q 2. Connect some of the points with segments such that each point is connected with 5 other points.

#### Induction

Q 1. What is the formula for the sum of all integers from 55 to n*n*, where n \geq 5*n*≥5?

- \frac{(n+5)(n-4)}{2}2(
*n*+5)(*n*−4) - \frac{(n+5)(n-6)}{2}2(
*n*+5)(*n*−6) - \frac{(n+5)(n+1)}{2}2(
*n*+5)(*n*+1) - \frac{(n+5)(n-5)}{2}2(
*n*+5)(*n*−5) - \frac{n(n+1)}{2}2
*n*(*n*+1)

Q 2. Find the formula for the sum of all odd numbers from 11 to 2n – 12*n*−1: 1 + 3 + 5 + \dots + (2n – 3) + (2n – 1)1+3+5+⋯+(2*n*−3)+(2*n*−1).

- (2n-1)(n)(2
*n*−1)(*n*) - n(n + 1)
*n*(*n*+1) - n^2
*n*2 - 3n-23
*n*−2

Q 3. Function T*T* is defined by T(0) = a, T(n + 1) = T(n) + b*T*(0)=*a*,*T*(*n*+1)=*T*(*n*)+*b*. What is the correct formula for T(n)*T*(*n*)?

- T(n) = a + nb
*T*(*n*)=*a*+*nb* - T(n) = a + (n+1)b
*T*(*n*)=*a*+(*n*+1)*b* - T(n) = a + (n-1)b
*T*(*n*)=*a*+(*n*−1)*b* - T(n) = ab^n
*T*(*n*)=*abn* - T(n) = b + na
*T*(*n*)=*b*+*na*

Q 4. Function T(n)*T*(*n*) is defined by T(0) = a, T(n + 1) = b \cdot T(n)*T*(0)=*a*,*T*(*n*+1)=*b*⋅*T*(*n*). What is the correct formula for T(n)*T*(*n*)?

- T(n) = ab^n
*T*(*n*)=*abn* - T(n) = a + bn
*T*(*n*)=*a*+*bn* - T(n) = b + na
*T*(*n*)=*b*+*na* - T(n) = a^nb
*T*(*n*)=*anb*

Q 5. Recall the recursive formula for the minimum number of moves in the Hanoi Towers problem: T(1) = 1, T(n + 1) = 2T(n) + 1*T*(1)=1,*T*(*n*+1)=2*T*(*n*)+1, where T(n)*T*(*n*) is the minimum number of moves for Hanoi Towers with n*n* disks. What is the correct formula for T(n)*T*(*n*)?

- T(n) = 2^n – 1
*T*(*n*)=2*n*−1 - T(n) = n
*T*(*n*)=*n* - T(n) = \frac{n(n+1)}{2}
*T*(*n*)=2*n*(*n*+1) - T(n) = 2n – 1
*T*(*n*)=2*n*−1

Q 6. You have $1000 on day 11, and every day you earn 10\%10% of what you already get, so that on day 22 you have $1000+10%⋅$1000=$1100, and on day 33 you have $1100+10%⋅$1100=$1210. On which day you will have more than $1000000 for the first time? Feel free to use the notebook about Bernoulli’s inequality that we provided in this lesson.

- On day 7474.
- On day 7676.
- On day 1000010000.
- On day 565

Q 7. What is the flaw in the following proof?

**Claim: **For any integer n \geq 0*n*≥0 and any positive integer a*a*, a^n = 1*a**n*=1.

**Proof by Induction.**

**Induction base:** n = 0*n*=0, so a^n = a^0 = 1*a**n*=*a*0=1.

**Induction step: **If the statement is true for all n*n* up to m*m*, then it is true for n = m + 1*n*=*m*+1.

a^{m + 1} = \frac{a^m \cdot a^m}{a^{m – 1}} \stackrel{!}{=} \frac{1 \cdot 1}{1} = 1*a**m*+1=*a**m*−1*a**m*⋅*a**m*=!11⋅1=1

Where we marked by “!” the assumption of the induction that a^m = 1*a**m*=1 and a^{m – 1} = 1*a**m*−1=1.

- The induction step must prove something for n + 1
*n*+1 based just on the fact that something is true for n*n*. - The induction base is wrong: a^0
*a*0 is not always equal to 11. - We are using the assumption of the induction for both m
*m*and m – 1*m*−1, so we must have proved induction base for at least two different values of n*n*– 00 and 11. - The induction step is wrong: \frac{1 \cdot 1}{1} \neq 111⋅1=1.

Q 8. Function T(n)*T*(*n*) is defined as T(0) = 0, T(2n) = T(n) + 1, T(2n + 1) = T(n) + 1*T*(0)=0,*T*(2*n*)=*T*(*n*)+1,*T*(2*n*+1)=*T*(*n*)+1. What is the correct formula for T(n)*T*(*n*)?

- T(n) = 2^n
*T*(*n*)=2*n* - T(n) = 2n
*T*(*n*)=2*n* - T(n) = n
*T*(*n*)=*n* - T(n) = k
*T*(*n*)=*k*, where k*k*is the smallest non-negative integer such that 2^k > n2*k*>*n*.

Q 9. What is the value of the sum \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \dots + \frac{1}{99 \cdot 100}1⋅21+2⋅31+3⋅41+⋯+99⋅1001?

- 0.90.9
- 0.990.99
- 11
- 0.50.5

### Mathematical Thinking in Computer Science Week 04 Quiz Answer

#### Puzzle: Always Prime?

Q 1. Somebody has a conjecture: for every integer n > 1*n*>1 the number n^2 + n + 41*n*2+*n*+41 is prime (is not a product of two smaller integers). Is it true? If not, find a counterexample.

Answer:

#### Examples, Counterexamples and Logic

Q 1. Alice (a mathematician specialized in mathematical logic) says that every recursive ordinal is constructive. Bob wants to refute Alice’s claim by giving a counterexample. Which of the following could he provide? (*Note that in order to answer this question you do not need to know what an ordinal is, or what it means for it to be constructive or recursive.*).

- A constructive ordinal that is not recursive
- A non-constructive ordinal that is not recursive
- A non-constructive ordinal that is recursive

Q 2. Which of the following statements are equivalent? Group the equivalent statements:

- All recursive ordinals are constructive
- All constructive ordinals are recursive
- All non-recursive ordinals are non-constructive
- All non-constructive ordinals are non-recursive
- Some constructive ordinals are recursive
- Some recursive ordinals are constructive
- Some non-recursive ordinals are non-constructive

- One group: 5, 6 and 7.
- Two groups: 1, 4 and 6; 2, 3, 5 and 7.
- Three groups: 1 and 4; 2 and 3; 5 and 6.
- Two groups: 1 and 2, 3 and 4.

Q 3. Alice claims that every student in a group knows both French and German. Which of the following sentences asserts that Alice’s statement is wrong (no more, no less)?

- All students know at most one of these two languages
- There is a student who does not know French and does not know German
- There is a student who does not know French or does not know German (or both)
- Every student who knows French does not know German

Q 4. Alice claims that every student in a group knows French, German, or both. Which of the following sentences asserts that Alice’s statement is wrong (no more, no less)?

- All students know at most one of these two languages
- There is a student who does not know French and does not know German
- There is a student who does not know French or does not know German (or both)
- Every student who knows French does not know German

Q 5. Let x be a number. Consider the following five statements: x>10, x>20, x>30, x>40, x>50*x*>10,*x*>20,*x*>30,*x*>40,*x*>50. Three of these statements are true and two are false. Which ones are true?

- x > 10
*x*>10 - x > 20
*x*>20 - x > 30
*x*>30 - x > 40
*x*>40 - x > 50
*x*>50

Q 6. Consider the following statements about a number x:

- x is a multiple of 2 (x/2 is integer);
- x is a multiple of 3;
- x is a multiple of 6.

Is it possible that for some integer x

- None of them are true?
- Exactly one of them is true?
- Exactly two of them are true?
- All three statements are true?

Q 7. Alice says that in every region there is a town where all inhabitants are happy. Bob wants to say that Alice is wrong. Which of the following sentences should Bob say?

- There is a region where in all towns at least one inhabitant is unhappy.
- There is a region where there is a town where all inhabitants are happy.
- In every region in all towns all inhabitants are happy.
- In every region there is a town where at least one inhabitant is unhappy.

#### Girls, Boys, and Two Languages

Q 1. here are boys and girls in a class. Some study French, others study German. Is there a boy and a girl that study different languages?

**Yes, it is true.**- No, it can be the case that there are no such boy and girl.

#### Puzzle: Balls in Boxes

Q 1. Distribute **60** black balls among 10 boxes so that every two boxes have different number of balls (you can put 0 balls in some box if you want to). Fill in numbers of black balls in each box below.

#### Puzzle: Numbers in Boxes

Q 1. There is a sequence of 10 cells, the leftmost cell contains 1 and the rightmost cell contains 30. Is it possible to fill other cells with numbers in such a way that consecutive numbers differ by at most 3?

#### Puzzle: Numbers on the Chessboard

Q 1. Is it possible to put numbers 1,2,…,64 on the chessboard in such a way that neighbors (sharing a side) differ by at most 4?

#### Numbers in Boxes

Q 1. Suppose there is a sequence of 20 cells, the first cell contains number 1 and the last cell contains 50. We would like to fill all cells with integer numbers in such a way that numbers in the neighbouring cells differ by at most k*k*. For which minimal k*k* this is possible?

#### How to Pick Socks

Q 1. Now we will address the problem that thousands of people encounter on daily basis. Suppose there is a box with socks in the dark room. There are socks of five different colours: black, brown, blue, red and green. But we do not see the colour in the dark. How many socks do we have to take to *guarantee *that we have two socks of the same colour?

#### Pigeonhole Principle

Q 1.Suppose there are 2n2*n* pigeons sitting in n*n* holes. They are trying to minimise the number of pigeons in the most occupied pigeonhole. What is the best value they can achieve?

Answer:

Q 2. Suppose there are 2n+12*n*+1 pigeons sitting in n*n* holes. They are trying to minimise the number of pigeons in the most occupied pigeonhole. What is the best value they can achieve?

Answer:

#### Puzzle: An (-1,0,1) Antimagic Square

Q 1. Fill a 3×3 table by numbers -1, 0 and 1 so that the sum in each row, each column and each diagonal produces different numbers. Click on the cell to change the number there. Sums in rows, columns and diagonals will be shown.

Answer:

### Mathematical Thinking in Computer Science Week 05 Quiz Answer

#### Puzzle: Sums of Rows and Columns

Q 1. Fill a 3 x 5 table with integers so that the sum of each row is equal to 20 and the sum of each column is equal to 10

Answer: Comment the Answer

#### ‘Homework Assignment’ Problem

Q 1. Each of 20 students in a group have solved three problems from the homework assignment, and each problem was solved by two students. How many problems were in the assignment?

Answer: Comment the Answer

#### ‘Homework Assignment’ Problem 2

Q 1. Everybody in the class got the same assignment. It turned out that every student solved more than half of all problems. Is it possible that at the same time each problem was solved by less than half of students?

**Yes**- No

#### Girls and Boys

Q 1. In a group of 27 students every girl knows four boys and every boy knows five girls. Find the number of boys in the group.

Answer: **12**

#### Chess Tournaments

Q 1. Four chess players played a series of tournaments between each other. In each tournament the player that finishes in the first place receives $4000 of prize money, the player that finishes in the second place receives $2000 and the player that finishes in the third place receives $1000. The player that finishes the last does not receive anything. After the series the total prizes won by each player are $13000, $10000, $7000 and $5000 respectively. How many tournaments have they played?

Answer: Comment the Answer.

#### Coffee with Milk

Q 1. There are two cups, the first with coffee and the second with milk. We take a spoon of coffee from the first cup and add it to the cup with milk. After that we take one spoon of a drink in the second cup and put it to the first cup. What is larger, the amount of milk in the first cup or the amount of coffee in the second cup?

- The amount of milk in the coffee cup is larger
**They are equal**- The amount of coffee in the milk cup is larger
- One needs to know the volumes of both cups and the spoon to answer the question.

#### More Coffee

Q 1. There are two equally sized cups, one with coffee, another with milk. Both cups are half full. We like the first cup and we like coffee with lots of milk: 1/3 coffee, 2/3 milk. We can pour drinks from one cup to another back and forth. Can we get our favorite coffee in our favorite cup? Any amount would do, the right proportion is what matters.

- Yes, we can
**No, we cannot**

#### Debugging Problem

Q 1. Bob is debugging his code. When he starts, he has only one bug. But once he fixes one bug, 3 new bugs appear. In several hours Bob fixed 15 bugs. How many pending bugs Bob has at this point?

Answer: Comment the Answer.

#### Merging Bank Accounts

Q 1. Suppose we have 10 banks and we have 10$ in each of them. We would like to merge all accounts into one. For this each day we repeat the following operation. We arbitrarily pick two banks in which we still have money and move all money from one bank to another. How many days do we need to do it to move all money to one account?

Answer: Comment the Answer.

Q 2. Now, in the formulation of the previous problem each time we merge two accounts together a bank charges us 1$ for this operation. How many dollars we will have left once we move all money to the same account?

Answer: Comment the Answer

#### Football Fans

Q 1. There are two football teams in a town. Each citizen supports one of the teams. If among someone’s friends there are more fans of the other team than of her own, she switches to support the other team. Each day, one such citizen switches. Is it possible that this switching process goes forever? (For the sake of this problem, we assume that the friendship is always mutual and that both the population and the friendship connection do not change.)

- Yes, it is possible
**No, it is not possible**

#### Puzzle: Arthur’s Books

Q 1. King Arthur has a shelf with 10 books, numbered 1,2,3,…,10. Over the years, the volumes got disordered. Arthur tries to order the books in the increasing order by exchanging positions of two books at once. Since the books are heavy, he can only switch two volumes each day. Help Merlin to order the books.

Solve Merlin’s task on the picture below.

Answer: Comment the Answer

Q 2. Solve Merlin’s task on the picture below in at most 5 days.

Answer: Comment the Answer

Q 3. Solve Merlin’s task on the picture below in at most 7 days.

Answer: Comment the Answer

Q 4. Solve Merlin’s task on the picture below in at most 7 days.

Answer: Comment the Answer

Q 5. Solve Merlin’s task on the picture below in at most 9 days.

Answer: Comment the Answer

Q 6. Find an arrangement of books such that it takes Merlin as many days as possible to solve the task.

Press solve to see the solution.

Comment the Answer.

#### Puzzle: Piece on a Chessboard

Q 1. A piece on a chessboard can move to any cell adjacent by edge to the current one. Can it return to the original position after **17** moves?

Comment the Answer.

Q 2. A piece on a chessboard can move to any cell adjacent by edge to the current one. Can it return to the original position after **18** moves?

Comment the Answer.

#### Operations on Even and Odd Numbers

Q 1. Suppose a and b are even. What can we say about their sum a+b?

- a+b is even
- a+b is odd
- Both cases are possible

Q 2. Suppose a is even and b is odd. What can we say about their sum a+b?

- a+b is even
- a+b is odd
- Both cases are possible

Q 3. Suppose a and b are odd. What can we say about their sum a+b?

- a+b is even
- a+b is odd
- Both cases are possible

Q 4.Suppose a and b are even. What can we say about their product a\times b*a*×*b*?

- a \times b
*a*×*b*is even - a \times b
*a*×*b*is odd - Both cases are possible

Q 5. suppose a is even and b is odd. What can we say about their product *a*×*b*?

*a*×*b*is even*a*×*b*is odd- Both cases are possible

Q 6. Suppose a and b are odd. What can we say about their product *a*×*b*?

*a*×*b*is even*a*×*b*is odd- Both cases are possible

#### Puzzle: Summing Up Digits

Q 1. Place signs in the expression ± 1 ± 2 ± … ± 9 to get as a result the sum N = 0.

Answer: Comment the Answer.

Q 2. Place signs in the expression ± 1 ± 2 ± … ± 9 to get as a result the sum N = 1.

Answer: Comment the Answer.

Q 3. Place signs in the expression ± 1 ± 2 ± … ± 9 to get as a result the sum N = 2.

Answer: Comment the Answer.

Q 4.Place signs in the expression ± 1 ± 2 ± … ± 9 to get as a result the sum N = 100.

Answer: Comment the Answer.

#### Puzzle: Switching Signs

Q 1. We are given a 4 x 4 table as on the picture. On one step we are allowed to switch all signs in some column or some row. Can we switch all signs to ‘+’?

Comment the Answer.

Q 2. We are given a 4 x 4 table as on the picture. On one step we are allowed to switch all signs in some column or some row. Can we switch all signs to ‘+’?

Comment the Answer.

Q 3. We are given a 4 x 4 table as on the picture. On one step we are allowed to switch all signs in some column or some row. Can we switch all signs to ‘+’?

Comment the Answer.

Q 4. We are given a 4 x 4 table as on the picture. On one step we are allowed to switch all signs in some column or some row. Can we switch all signs to ‘+’?

Comment the Answer.

Q 5. We are given a 4 x 4 table as on the picture. On one step we are allowed to switch all signs in some column or some row. Can we switch all signs to ‘+’?

Comment the Answer.

Q 6. We are given a 4 x 4 table as on the picture. On one step we are allowed to switch all signs in some column or some row. Can we switch all signs to ‘+’?

Comment the Answer.

Q 7. We are given a 4 x 4 table as on the picture. On one step we are allowed to switch all signs in some column or some row. Can we switch all signs to ‘+’?\

Comment the Answer

#### Recolouring Chessboard

Q 1. Suppose we have an 8 \times 88×8 chessboard coloured in black and white colours in a standard way. On one step we are allowed to pick a square 2 \times 22×2 on this chessboard and recolour all its squares into the opposite colour. Is it possible after several such operations to obtain a board with only one black 1 \times 11×1 square?

**Yes, it is possible**- No, it is not possible

### Mathematical Thinking in Computer Science Week 06 Quiz Answer

#### Puzzle: 15

Q 1. A click on a green square moves it to the neighboring empty cell. Use such clicks to order 15 numbers in the increasing order: 1 2 3 4 (first row), 5 6 7 8 (second row), 9, 10, 11, 12 (third row), 13, 14, 15, empty (fourth row).

Comment the Answer

Q 2. A click on a green square moves it to the neighboring empty cell. Use such clicks to order 15 numbers in the increasing order: 1 2 3 4 (first row), 5 6 7 8 (second row), 9, 10, 11, 12 (third row), 13, 14, 15, empty (fourth row)

Comment the Answer

Q 3. A click on a green square moves it to the neighboring empty cell. Use such clicks to order 15 numbers in the increasing order: 1 2 3 4 (first row), 5 6 7 8 (second row), 9, 10, 11, 12 (third row), 13, 14, 15, empty (fourth row).

Comment the Answer.

#### Transpositions and Permutations

Q 1. Find a sequence of transpositions of letters that transform the sequence MARINE (positions are numbered 0..5) to the sequence AIRMEN. Transpositions are represented by pairs of integers. For example, the pair (0,1) transforms MARINE to AMRINE. Transpositions are performed from left to right. You should define the sequence by writing something like this (the dots should be replaced by numbers, each pair in parentheses specifies one permutation, and these permutations are performed sequentially, from left to right):

def sequence():

return [(…,…),…, (…,…)]

(The format looks strange if you have no experience with python, but codeblocks are the easiest way to check the answer, sorry. The second line should be indented, i.e., should have some spaces before “return”. The exact number of spaces does not matter here.)

#### Neighbor transpositions

Q 1. Now you should find a sequence of ** neighbor** transpositions of letters that transform the sequence MARINE (letters are numbered 0..5) to the sequence AIRMEN. Transpositions are represented by pairs of integers. For example, the pair (0,1) transforms MARINE to AMRINE. Transpositions are performed from left to right. You should define the sequence as shown:

def sequence():

return [(…,…), (…,…),…,(…,…)]

(Just replace the dots in the parentheses by pairs of numbers that say which neighbor letters should be replaced. Yes, the format is strange, but this is how python codeblock works…)

#### Is a permutation even?

Q1. Is the permutation [0,3,2,4,5,6,7,1,9,8] even?

- Yes
- No

Q2. Implement a function is_even(p) that returns True for even permutations and False for odd permutations. (Note that the name of the function is important. Keep the first line of the function definition unchanged!)

#### Bonus Track: Algorithm for 15-Puzzle

Q1. Write a Python function solution(position) that gets a (solvable) position in 15-puzzle and outputs a sequence of moves that transforms it to a standard position. (See in the previous Reading item about encodings. In short, position is a sequence of integers written in the cells, where empty cell is represented by 0; moves in the sequence are labels on the cells that move.

#### Get All Course Quiz Answers of **Entrepreneurship Specialization**

Entrepreneurship 1: Developing the Opportunity Quiz Answers

Entrepreneurship 2: Launching your Start-Up Quiz Answers

Entrepreneurship 3: Growth Strategies Coursera Quiz Answers

Entrepreneurship 4: Financing and Profitability Quiz Answers