Skip to content
Tutorials Center
My learning

Topics

Lesson 65 of 68 Β· Practice and Review

Exercises: Counting and Number Theory

Seventeen graded exercises on counting, probability, divisibility, modular arithmetic, number bases and toy RSA, each with a runnable Python solution.

This is the second exercise set of the course. It covers two big chapters: counting (with a little probability) and number theory. There are seventeen exercises in four rounds. Every round has one runnable solution block that computes each answer by brute force and, where a formula exists, compares the two. When a formula and a brute-force count agree, you can trust both. When they disagree, you have found a bug in one of them, and that is the most useful thing a check can do.

Grades: β˜… is a warm-up, β˜…β˜… needs two ideas or some care, β˜…β˜…β˜… is a real puzzle. Try each exercise on paper before you run the code, and write your answer down first. If a topic feels shaky, the matching lessons are Counting Principles, Permutations and Combinations, Discrete Probability, Modular Arithmetic and Number Theory in Cryptography.

Four rounds

Counting Rules, arrangements, inclusion-exclusion.
Special counts and chance Derangements, Catalan, Bayes, birthdays.
Modular arithmetic Euclid, inverses, remainders, CRT.
Bases and primes Binary, sieves, Carmichael, toy RSA.
1 / 2

Round 1: basic counting

Exercise 1 (β˜…). A license plate has three letters followed by three digits. How many plates are possible if repeats are allowed? How many if no letter and no digit may repeat?

Exercise 2 (β˜…). A club of 10 people picks a committee of 4. Two members, Ana and Ben, refuse to serve together. How many committees are possible?

Exercise 3 (β˜…β˜…). How many different strings can you make by rearranging the letters of BANANA? Of MISSISSIPPI? (Brute-force the first, use a formula for the second, because 11 letters have almost 40 million orderings.)

Exercise 4 (β˜…β˜…). How many integers from 1 to 1000 are divisible by 3, by 5 or by 7?

Exercise 5 (β˜…β˜…). How many ways can you write 12 as x₁ + xβ‚‚ + x₃ + xβ‚„ with every xα΅’ a non-negative integer? How many if every xα΅’ must be at least 1?

Python Solutions for Round 1

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For Exercise 1 the product rule gives 26Β³ Β· 10Β³ = 17,576,000 plates with repeats, and 26 Β· 25 Β· 24 Β· 10 Β· 9 Β· 8 = 11,232,000 without. In Exercise 2, count all committees (210) and subtract those that contain both Ana and Ben (the other two members come from the remaining 8, so 28): 182. BANANA has 60 arrangements and MISSISSIPPI has 34,650: divide the factorial of the length by the factorials of the letter repeats. In Exercise 4 you add the three single counts (333, 200, 142), subtract the three overlaps (66, 47, 28) and add back the triple overlap (9), for 543. Exercise 5 is stars and bars: 455 non-negative solutions, and 165 when every part is at least 1 (give each variable 1 first, then distribute the remaining 8).

Round 2: special counts and probability

Exercise 6 (β˜…β˜…). How many permutations of 1..6 leave no element in its original position (derangements)? How many strings of 4 pairs of parentheses are balanced?

Exercise 7 (β˜…β˜…). Roll two fair dice: what is the probability the sum is 7? Roll one die four times: what is the probability of at least one six? Give exact fractions.

Exercise 8 (β˜…β˜…β˜…). What is the smallest group size for which two people share a birthday with probability above 1/2? (Ignore leap days and assume 365 equally likely birthdays.)

Exercise 9 (β˜…β˜…β˜…). A disease affects 1% of a population. A test is positive for 95% of the sick and, wrongly, for 5% of the healthy. If you test positive, what is the probability that you are sick?

Python Solutions for Round 2

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are 265 derangements of six items and 14 balanced strings with four pairs (the fourth Catalan number). In Exercise 7 the sum is 7 with probability 1/6, and at least one six in four rolls has probability 671/1296 (about 0.5177), which is 1 βˆ’ (5/6)⁴. The birthday answer is 23 people, with a probability of about 0.5073; the surprise comes from counting pairs, not people. For Exercise 9 the answer is 19/118, about 16%: most positive tests come from the large healthy group. That is Bayes' theorem at work, and the reason base rates matter.

Round 3: divisibility and modular arithmetic

Exercise 10 (β˜…). Find gcd(1071, 462), their lcm, and integers x and y with 1071x + 462y = gcd.

Exercise 11 (β˜…β˜…). What is the last digit of 7²⁰²⁡? What is the remainder of 3¹⁰⁰ divided by 13? What are the last two digits of 7²⁰²⁡?

Exercise 12 (β˜…β˜…). Solve 17x ≑ 5 (mod 31).

Exercise 13 (β˜…β˜…β˜…). Find the smallest positive x with x ≑ 2 (mod 3), x ≑ 3 (mod 5) and x ≑ 2 (mod 7). Then solve the system with the Chinese remainder theorem recipe instead of searching.

Python Solutions for Round 3

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Euclidean algorithm gives gcd(1071, 462) = 21 and lcm = 1071 Β· 462 / 21 = 23,562; the coefficients are x = βˆ’3 and y = 7, because 21 = 7 Β· 462 βˆ’ 3 Β· 1071. In Exercise 11 the last digits of powers of 7 repeat with period 4 (7, 9, 3, 1), and 2025 leaves remainder 1 modulo 4, so the last digit is 7. Since 3Β³ = 27 ≑ 1 (mod 13), 3¹⁰⁰ = (3Β³)Β³Β³ Β· 3 ≑ 3. The last two digits are 07, because 7 has order 4 modulo 100 as well and 7⁴ = 2401. For Exercise 12 the inverse of 17 modulo 31 is 11, so x ≑ 55 ≑ 24, and since 31 is prime the solution is unique. Exercise 13 gives 23; the CRT recipe builds it from three terms, each of which is 0 modulo two of the moduli.

Round 4: bases, primes and toy RSA

Exercise 14 (β˜…). Write 2024 in binary and hexadecimal. Convert 101101 (binary) to decimal. Write βˆ’5 as an 8-bit two's complement number.

Exercise 15 (β˜…β˜…). How many primes are below 100? How many twin prime pairs (p, p + 2 both prime) are there below 100? How many divisors does 360 have?

Exercise 16 (β˜…β˜…). Fermat's little theorem says aᡖ⁻¹ ≑ 1 (mod p) for prime p and a not divisible by p. Show that the converse fails: 561 is composite, yet a⁡⁢⁰ ≑ 1 (mod 561) for every a coprime to it.

Exercise 17 (β˜…β˜…β˜…). With the toy primes p = 11 and q = 17 and public exponent e = 7, compute the RSA modulus, the private exponent d, and encrypt and decrypt the message 42. This is only for learning: real keys use primes of hundreds of digits and padding schemes, and you should never write your own cryptography for real use.

Python Solutions for Round 4

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

2024 is 11111101000 in binary and 7e8 in hexadecimal; 101101 is 45; and βˆ’5 in 8 bits is 11111011 (invert 00000101 and add 1). Exercise 15: there are 25 primes below 100, with 8 twin pairs, and 360 = 2Β³ Β· 3Β² Β· 5 has (3 + 1)(2 + 1)(1 + 1) = 24 divisors. In Exercise 16, 561 = 3 Β· 11 Β· 17 is the smallest Carmichael number: it fools the Fermat test for every base coprime to it, which is why stronger primality tests (Miller-Rabin) exist. The note about 3 shows the one caveat: a base that shares a factor with n never gives 1. For the toy RSA, n = 187, Ο† = 160, d = 23 (since 7 Β· 23 = 161 ≑ 1 mod 160), and 42 encrypts to 15, and decrypting 15 returns 42.

Scoring yourself

  • 14 to 17 on paper first: you handle counting and number theory well; move on to Exercises: Graphs and Recurrences.
  • 9 to 13: reread the lessons linked above for the rounds you missed, then change the numbers (a different group size, another modulus) and predict the output before running.
  • Fewer than 9: run each solution line by line and add a print after each step. Counting problems usually fall apart into the sum, product and complement rules once you name which one you are using.

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. How many distinct strings can be made from the letters of BANANA?

    6! orderings, divided by 3! for the three A's and 2! for the two N's, gives 720 / 12 = 60.
  2. 2. A test is 95% accurate on sick people and gives 5% false positives on healthy ones, and 1% of people are sick. Why is P(sick | positive) only about 16%?

    Of 10,000 people, 95 sick people test positive but so do 495 healthy people. Only 95 of 590 positives are real.
  3. 3. What is 7^2025 mod 10?

    The last digits of powers of 7 cycle 7, 9, 3, 1 with period 4. Since 2025 mod 4 = 1, the digit is the first one in the cycle: 7.
  4. 4. Why does 561 matter for Fermat's little theorem?

    561 = 3 * 11 * 17 is a Carmichael number, so a^560 = 1 (mod 561) for every a coprime to 561 even though 561 is not prime.
  5. 5. In the toy RSA example with n = 187, which two numbers must be kept secret?

    n and e are public. Knowing p and q lets you compute phi and d, so those stay private. Real RSA uses huge primes; this toy size is trivially breakable.

Summary

  • Combine the product, sum and complement rules, and verify formulas such as C(n, k), multiset permutations and inclusion-exclusion with a brute-force count on a small case.
  • Derangements, Catalan numbers and stars and bars are counting patterns you can recognize and then confirm in code.
  • Use exact Fraction arithmetic for probability; Bayes' theorem shows why base rates change the answer.
  • pow(a, b, m) and pow(a, -1, m) handle modular powers and inverses; the Euclidean algorithm gives Bezout coefficients; the CRT recombines remainders.
  • Base conversion, sieves, Carmichael numbers and toy RSA tie the number theory together, for learning only.

Next: Exercises: Graphs and Recurrences.