CEMC Banner

Problem of the Week
Problem A and Solution
Picture Pixels

Problem

Akhil sends codes to his friends that tell them how to shade in squares of a grid to reveal a secret picture. Each code contains a blank grid with a list of numbers next to each row, which are used to shade in the row from left to right. The first number in a list represents the number of blank squares at the beginning of the row. The second number represents the number of squares that need to be shaded next. After that, the numbers alternate between the number of blank squares and the number of shaded squares until you reach the end of the row.

For example, if the list of numbers was \(2\), \(2\), \(1\), then the leftmost \(2\) squares would be blank, the next \(2\) squares would be shaded, and the next square would be blank. A completed picture is shown.

A grid with 3 rows and 5 columns. The first row has list 2, 2, 1 and, from left to right, has 2 blank squares, then 2 shaded squares, then 1 blank square. The second row has list 1, 3, 1 and, from left to right, has 1 blank square, then 3 shaded squares, then 1 blank square. The third row has list 0, 2, 1, 2 and, from left to right, has two shaded squares, then one blank square, then two shaded squares.

  1. Draw the picture for the given code.

    A description of the code follows.


  2. Akhil turns some of his codes into puzzles. For each column, he adds a list of numbers representing the number of blank and shaded squares, as he has for the rows. Then, for each row and column, he removes the numbers representing blank squares. Two of his puzzles are shown. Try to solve them.


    1. A description of the puzzle follows.




    2. A description of the puzzle follows.


Solution

  1. The completed picture is shown.

    From left to right, the first row has 1 blank square, then 3 shaded squares, then 1 blank square. The second row has 1 shaded, 1 blank, 1 shaded, 1 blank, then 1 shaded. The third row has all 5 squares shaded. The fourth row has 1 blank, 1 shaded, 1 blank, 1 shaded, then 1 blank. The fifth row has 1 shaded, then 3 blank, then 1 shaded.

  2. For each puzzle, start by identifying any squares that you know must be either blank or filled. For example, for puzzle (i), the row with list \(1\), \(3\) must have at least one blank between the \(1\) shaded square and the \(3\) shaded squares. Since there are \(5\) squares in the row, this means that, from left to right, the row must contain one shaded square, then one blank square, then three shaded squares. It also helps to mark the blank squares with a dot. The completed puzzles are shown. Note that these kind of puzzles are often called Nonograms.


    1. From left to right, the first row has 4 blank squares, then 1 shaded square. The second row has 3 blank, then 2 shaded. The third row has 1 shaded, 1 blank, then 3 shaded. The fourth row has 4 shaded, then 1 blank. The fifth row has 2 shaded, then 3 blank.


    2. From left to right, the first row has 2 blank squares, then 1 shaded square, then 2 blank squares. The second row has 2 blank, 2 shaded, then 1 blank. The third row has 2 blank, 1 shaded, 1 blank, then 1 shaded. The fourth row has 3 shaded, 1 blank, then 1 shaded. The fifth row has 2 shaded, then 3 blank.

Teacher’s Notes

The original code in this problem uses run length encoding to describe images. Run length encoding is a way to describe large amounts of data in a more compact way; it is an example of a compression technique.

This particular compression technique was used by fax machines to send information more efficiently. Since fax images were black and white, rather than sending the image data one pixel at a time, it took less data to identify the image by grouping white pixels and black pixels in each row as is shown in this problem.

Although fax machines are not used much these days, run length encoding is still a technique used by computer scientists to help reduce the size of large data to be more manageable. One place where it is used is to describe information in gene sequences. Genes can be described as long sequences made up of four different proteins: adenine (A), thymine (T), cytosine (C), and guanine (G). The long sequences that describe the building blocks of DNA can be compressed by grouping common protein letters and using the count of how many of the same letter appears consecutively.