19 ِAgain! - overlapped squares

Probability Level 4

Consider a grid of 19 × 19 19 \times 19 LED's which Initially are OFF. You are allowed to select an array of 5 × 5 5 \times 5 LED's and toggle their states. After toggling the 225 225 different 5 × 5 5 \times 5 arrays one after one, how many LED's will be turned O N ON ?

This problem is original.


The answer is 225.

Ossama Ismail by Ossama Ismail , 63, Egypt

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Henry U
Dec 27, 2018

The following table gives the number of times an LED is toggled. If this number is even, then the LED will of OFF at the end, but if the number is odd, then the LED will be ON.

1 2 3 4 5 5 5 ⋯ 5 5 5 4 3 2 1 2 4 6 8 10 10 10 ⋯ 10 10 10 8 6 4 2 3 6 9 12 15 15 15 ⋯ 15 15 15 12 9 6 3 4 8 12 16 20 20 20 ⋯ 20 20 20 16 12 8 4 5 10 15 20 25 25 25 ⋯ 25 25 25 20 15 10 5 5 10 15 20 25 25 25 ⋯ 25 25 25 20 15 10 5 5 10 15 20 25 25 25 ⋯ 25 25 25 20 15 10 5 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 5 10 15 20 25 25 25 ⋯ 25 25 25 20 15 10 5 5 10 15 20 25 25 25 ⋯ 25 25 25 20 15 10 5 5 10 15 20 25 25 25 ⋯ 25 25 25 20 15 10 5 4 8 12 16 20 20 20 ⋯ 20 20 20 16 12 8 4 3 6 9 12 15 15 15 ⋯ 15 15 15 12 9 6 3 2 4 6 8 10 10 10 ⋯ 10 10 10 8 6 4 2 1 2 3 4 5 5 5 ⋯ 5 5 5 4 3 2 1 \begin{array}{cccccccccccccc} 1&2&3&4&5&5&5&\cdots&5&5&5&4&3&2&1 \\ 2&4&6&8&10&10&10&\cdots&10&10&10&8&6&4&2 \\ 3&6&9&12&15&15&15&\cdots&15&15&15&12&9&6&3 \\ 4&8&12&16&20&20&20&\cdots&20&20&20&16&12&8&4 \\ 5&10&15&20&25&25&25&\cdots&25&25&25&20&15&10&5 \\ 5&10&15&20&25&25&25&\cdots&25&25&25&20&15&10&5 \\ 5&10&15&20&25&25&25&\cdots&25&25&25&20&15&10&5 \\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots& \\ 5&10&15&20&25&25&25&\cdots&25&25&25&20&15&10&5 \\ 5&10&15&20&25&25&25&\cdots&25&25&25&20&15&10&5 \\ 5&10&15&20&25&25&25&\cdots&25&25&25&20&15&10&5 \\ 4&8&12&16&20&20&20&\cdots&20&20&20&16&12&8&4 \\ 3&6&9&12&15&15&15&\cdots&15&15&15&12&9&6&3 \\ 2&4&6&8&10&10&10&\cdots&10&10&10&8&6&4&2 \\ 1&2&3&4&5&5&5&\cdots&5&5&5&4&3&2&1 \end{array}

In the table, we see that there are 9 odd numbers in each of the 5 × 5 5 \times 5 -corner squares. Additionally, in the 5 × 9 5 \times 9 -edge rectangles, there are 3 ⋅ 9 = 27 3 \cdot 9 = 27 odd numbers each. In the central 9 × 9 9 \times 9 -square, all 81 numbers are 25, so also odd.

Therefore, there are a total of

4 ⋅ 9 + 4 ⋅ 27 + 81 = 225 4 \cdot 9 + 4 \cdot 27 + 81 = \boxed{\boxed{225}}

LEDs that will be on.

How I got the table:

If we enumerate the LEDs such that the top left ist ( 1 , 1 ) (1,1) and the bottom right is ( 19 , 19 ) (19,19) , then the numbers in the top left quarter of the table are given by

a ( x , y ) = min ⁡ ( x , 5 ) ⋅ min ⁡ ( y , 5 ) a_{(x,y)} = \min(x,5) \cdot \min(y,5) .

This is because for a particular LED ( x , y ) (x,y) there is a toggling square for each LED that is to the top and left of this LED, but no further than 5 spots away.

A more complicated formula can also give the number for all LEDs

a ( x , y ) = min ⁡ ( 5 , 10 − ∣ x − 10 ∣ ) ⋅ min ⁡ ( 5 , 10 − ∣ x − 10 ∣ ) a_{(x,y)} = \min(5, 10-|x-10|) \cdot \min(5, 10-|x-10|)

2 Helpful 4 Interesting 2 Brilliant 0 Confused
Ossama Ismail
Dec 27, 2018

A general mathematical formula for any given L × W L \times W grid taking n × m n \times m arrays

Number of O N \color{#D61F06} ON LEDs = L × W − ( ⌊ n 2 ⌋ × 2 × W + ⌊ m 2 ⌋ × 2 × L ) + ⌊ n 2 ⌋ × ⌊ m 2 ⌋ × 4 = L \times W -(\lfloor \frac{n}{2}\rfloor \times 2 \times W+\lfloor \frac{m}{2} \rfloor \times 2 \times L) + \lfloor \frac{n}{2}\rfloor \times \lfloor \frac{m}{2}\rfloor \times 4

1 Helpful 2 Interesting 2 Brilliant 1 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...