I Why can't I reach every cell in a 3x3 square?

Hi,

I was playing this game in which you start from any cells of a 3x3 or 5x5 square and draw a line that loops through every cell in the box. The line can go only through a vertical or horizontal side (not diagonally). When you start from certain cells (problem cells), you can't reach at least one cell. In the attached file, I have shown such paths. The cells that can't be reached are shown with a question mark.

I am trying to find out how to express mathematically a.) why a particular cell can't reach every cell in a box, and 2) how many problem cells will be in a nxn matrix, where n is an odd number.

This is what I have noticed so far:
1. With even numbered squares such as 2x2 and 4x4, have no problem cells.
2. The 3x3 square has 4 problem cells and the 5x5 square has 12 problem cells.
3. Corner cells and the center cell (in the case of 3x3 and 5x5) are never problem cells.
4. The problem situation occurs when the line enters a T junction with empty cells on either sides.


How should I approach this problem?

Thanks.
 

Attachments

mathman

Science Advisor
7,628
378
Attached Files

When I click on it. a new page opens up - blank!
 
32,682
8,553
and it is difficult
In this special case: It always works if at least one of the side lengths is even because they have a Hamilton cycle and you can just follow that no matter where you start. Otherwise there are some starting positions that don't work.
 
When I click on it. a new page opens up - blank!
That means it downloads the file in the default download folder of your browser.
 
I have done some more progress on this problem.
5. If I name each cell of the box using the Row x column convention, I can see a pattern. The top left cell is named as (1,1) , the next cell on the right as (1,2) , the first cell in the second row as (2,1) and so on. The cells whose row and column numbers add to an odd number are problem cells.

6. Based on that, I think, in a NxN square, where N is an odd number, there will be
## (N^2 -1 )/2 ##. I am not sure how to prove this though.

 

FactChecker

Science Advisor
Gold Member
2018 Award
4,822
1,647
You are showing particular paths that can not be completed. But it's not clear to me that there are any such problem and starting point where there is no solution even if one is free to pick the right path. Do you have an example like that?

EDIT: I take it back. I do not see any solution to your 3x3 example. I think I have trouble with all of the odd x odd examples.
 
32,682
8,553
I have done some more progress on this problem.
5. If I name each cell of the box using the Row x column convention, I can see a pattern. The top left cell is named as (1,1) , the next cell on the right as (1,2) , the first cell in the second row as (2,1) and so on. The cells whose row and column numbers add to an odd number are problem cells.

6. Based on that, I think, in a NxN square, where N is an odd number, there will be
## (N^2 -1 )/2 ##. I am not sure how to prove this though.
Color the field with a checkerboard pattern. Every connection goes from black to white or vice versa. Now consider how many fields of each color there are.
 

Want to reply to this thread?

"Why can't I reach every cell in a 3x3 square?" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top