The smileys problem

Logic Level 3

There are smileys in the infinite square grid. The operation $Q$ is to remove any smiley by replacing one smiley at its top and one smiley at its right (provided that originally there is no smiley at its top and its right).

Here shows an example of 2 iterations of $Q$ .

The following diagram shows an initial stage, where 6 smileys occupied 6 shaded squares. Question: Is it possible that all the 6 shaded squares be eventually unoccupied by iterations of $Q$ ?

It is possible to do within 100 interations of

Q

. It is possible to do more than 100, but less than 500 interations of

Q

. It is possible to do more than 500, but less than 1000 interations of

Q

. It is not possible.

1 solution

Jason Carrier
Jan 13, 2019

Numberphile did a video on this problem: youtube.com

The solution in the video relied on numbering the grid. The bottom left square is 1, the ones adjacent to it are 1/2 each, the next diagonal is 1/4, and so on. Because of this numbering, performing Q leaves the total sum of the smileys’ values unchanged.

The total value of the bottom row is the sum $\displaystyle \sum_{n=0}^{\infty} \frac 1{2^n} = 2$ The same can be done for any other row, with the total sum dividing by two each row, so the sum of all the rows is $\displaystyle \sum_{n=0}^{\infty} 2*\frac 1{2^n} = 4$

The starting sum is 11/4, which is greater than the 5/4 outside these six spaces, so you cannot vacate the spaces without reducing the total, which Q cannot do.

Oh, thanks for the youtube link... Didn't aware about it... I use the same argument, but I have seen some other different method which I cant recall right now. Hope to see a different solution.

Chan Lye Lee - 2 years, 4 months ago

I feel like this could have been strengthened--for instance, if we just put smileys at $(0,0), (1,0),$ and $(0,1)$ and the goal is to vacate those three spaces, the answer remains that it is impossible. This is because the starting sum is $2$ and the infinite sum of the vacant spaces is $2,$ so we cannot vacate the three spaces in finitely many steps.

Ah, I see that the Numberphile video has used the stronger problem!

Patrick Corn - 2 years, 3 months ago

The smileys problem

1 solution

0 pending reports