CODING PUZZLES

[Solutions are shown after the puzzles]

Puzzle 1: Infinity (Scratch)

Go to https://scratch.mit.edu/projects/964712868/editor .

Run the code to see the list of numbers shown below.

1. The code finds the sum of 10 fractions.

a) Which fractions are they?

b) What is the sum if this pattern continues forever?

2. How does the code work?

3. Edit the code as shown on the right to find the sum of fractions 1/4, 1/16, 1/64, and so on.

a) What is the sum?

b) How does this sum make sense?

4. Edit the code to find the sum of fractions 1/2, 1/8, 1/32, and so on.

a) What is the sum?

b) How does this sum make sense?

Puzzle 2: Infinity (Python)

Go to https://cscircles.cemc.uwaterloo.ca/console .

Enter and run this Python code to list the numbers shown on the right.

1. The code finds the sum of 10 fractions.

a) Which fractions are they?

b) What is the sum if this pattern continues forever?

2. How does the code work?

3. Edit the code as shown on the right to find the sum of fractions 1/4, 1/16, 1/64, and so on.

a) What is the sum?

b) How does this sum make sense?

4. Edit the code to find the sum of fractions 1/2, 1/8, 1/32, and so on.

a) What is the sum?

b) How does this sum make sense?

Puzzle 3: Natural Density

Natural numbers = {1, 2, 3, 4, 5, 6, 7, 8 …}

Even numbers = {2, 4, 6, 8, 10 …}

Natural density of even numbers 

= Chance of picking an even number from the infinite set of natural numbers

= 0.5

Puzzles

  1. What is the natural density of the odd numbers: {1, 3, 5, 7, 9 …}?
  2. What is the natural density of multiples of 3: {3, 6, 9, 12, 15 …}?
  3. What is the natural density of multiples of 10: {10, 20, 30, 40, 50 …}?
  4. What is the natural density of the number 1?
  5. What is the natural density of the square numbers: {1, 4, 9, 16, 25 …}?

SOLUTIONS

Puzzle 1

1.a)  1/2, 1/4, 1/8, 1/16 …     

1.b)  1  [we see in the image below that all these fractions fit in 1 square]

3.  1/3          4. 2/3

In the 2 images on the right, we see that:

  • the pink rectangle is twice the size of the blue square;
  • the yellow rectangle is twice the size of the green square;
  • the purple rectangle is twice the size of the orange square;
  • and so forth.

So, the rectangular pieces make up 2/3 of the square below, and the remaining square pieces make up the remaining 1/3.

That is, 1/2 + 1/8 + 1/32 + … = 2/3.

And, 1/4 + 1/16 + 1/64 + … = 1/3.

Puzzle 2

1.a)  1/2, 1/4, 1/8, 1/16 …                  1.b)  1

2.  1/2

3.  1/3          4.a)  2/3

[see explanation in Puzzle 1, #3 & 4]

Puzzle 3

  1. 0. 5 or 1/2 (as half the natural numbers are odd)
  2. 0.333… or 1/3 (since 1/3 of the natural numbers are multiples of 3)
  3. 0.1 or 1/10 (since 1/10 of the natural numbers are multiples of 10)
  4.  
  • For natural numbers 1-10, there is 1/10 chance of randomly picking the number 1.
  • For natural numbers 1-100, there is 1/100 chance of randomly picking the number 1.
  • For natural numbers 1-1000, there is 1/1000 chance of randomly picking the number 1.
  • As we consider large and larger intervals, the probability decreases. Its limit is 0.
  • This is like the walk to the door, where the distance left to walk is decreasing, and getting closer and closer to 0, which is its limit.

5.

  • Run the code with different intervals: 100, 10,000 and 1,000,000.
  • Notice how the density changes.
  • What is the limit of the natural density values?

ABOUT THE NATURAL DENSITY OF SQUARE NUMBERS:

The natural density of square numbers is counter-intuitive, as there is an infinite number of square numbers. How can their density be 0?

But as we see from the coding simulation, the density of square numbers gets closer and closer to 0 as we consider larger intervals of natural numbers.

We may also look this problem algebraically:

Natural density of square numbers

= number of square numbers / number of natural numbers

= sqrt(N) / N

= 1 / sqrt(N)

(Note: In the first N natural numbers, there are at most ÖN square numbers) As N becomes larger and larger, 1 / sqrt(N) gets closer and closer zero.