Problem 984

[michelito]

It's not clear when a set counts as "knight connected" or "horse disjoint".
For the 3x3 case, if we just place one H on the board, we'd have 8 distinct possible sets plus all the sets with 2 or more horses. This does not sum up to 9 = F(3). Would be great if the author could show these 9 sets to clarify the rules.
Looking at the second example shown by the author (horse disjoint NOT knight connected) if some H could move twice would easly attack another H making that set not disjoint, so i suppose that each H can just move once, then if that's true I can't find, in example 3, how any H could reach another one on the board with just one legal move.
I hope someone could clarify what exactly the rules are, what counts as a legal unique set, and if a set can be made up by just one H.
thanks

[wim59]

I am not sure that I understand your confusion, but for the 3x3 case, we can place an H at every square, including the center. Obviously a single H is knight-connected, as well as horse disjoint (because there is no other horse that can be attacked). In general, a set is horse disjoint if no horse can attack another one in the set in a single move. That is what makes the third example horse disjoint.

[pjt33]

For the 3x3 case, if we just place one H on the board, we'd have 8 distinct possible sets plus all the sets with 2 or more horses. This does not sum up to 9 = F(3). Would be great if the author could show these 9 sets to clarify the rules.

The nine sets are the nine singleton sets. There are no sets with two or more squares. Suppose there were a set with 2 squares. One of them would have to be a corner and the other an edge not adjacent to the corner, because the set must be knight-connected. But then for the set to be horse-disjoint the centre square must be in the set. However, the centre square cannot be knight-connected to any other square.

Looking at the second example shown by the author (horse disjoint NOT knight connected) if some H could move twice would easly attack another H making that set not disjoint, so i suppose that each H can just move once, then if that's true I can't find, in example 3, how any H could reach another one on the board with just one legal move.

In example 3 no horse can reach another horse with just one legal move: that's why it's horse-disjoint.

[michelito]

Hi, thanks for your answer.
Maybe I still have not clear what makes a set knight-connected...
If I have a single H in position (1,1) (top left corner) in a 3x3 chessboard, is the set made by (1,1),(2,3),(3,2) squares considered knight-connected?
If there are two knights, do all the squares in the sets have to be reachable by both knights within legal moves to be considered a knight-connected set? If not, is the set with an H in (1,1) and one in (2,2) both knight-connected and horse-disjoint, or only knight-connected?

The third example is said to be both knight-connected AND horse-disjoint, while I understand that no horse can attack another one, I don't see which squares contribute to the knight-connected set.
The square in position (5,1) is reachable by two knights, while the ones in (3,1), (5,3), and (5,4) are reachable by one knight only. Does this mean that a set is both knight-connected and horse-disjoint if no H can attack another one AND there's at least one free square reachable by at least one H?

Then I do not understand what I have to count in F(n), the sum of distinct horse-disjoint sets + distinct knight-connected sets + sets that are both horse-disjoint and knight-connected? Or only distinct sets that are both horse-disjoint AND knight-connected?

[pjt33]

If I have a single H in position (1,1) (top left corner) in a 3x3 chessboard, is the set made by (1,1),(2,3),(3,2) squares considered knight-connected?

The question doesn't make sense in the context of the problem. At no point should you be thinking about one set of squares "under consideration" and a distinct set of squares containing horses. The set of squares (1,1),(2,3),(3,2) is knight-connected because there are knight jumps (1,1)<->(2,3) and (1,1)<->(3,2), so the induced knight-jump graph has one connected component. But if we place horses on those squares then nothing blocks those same jumps, so the set is not horse-disjoint.

    N_   .    .                H__>_.    .
    | \_                       |\    \
     \  \_                     | \    \
     |    \_                   v  \    \
      \     \_                 |   \    \
    . |  .    N                .    ._<__H
       \                        \   |
        |                        \  ^
         \                        \ |
         |                         \|
    .    N    .                .    H    .

If there are two knights, do all the squares in the sets have to be reachable by both knights within legal moves to be considered a knight-connected set? If not, is the set with an H in (1,1) and one in (2,2) both knight-connected and horse-disjoint, or only knight-connected?

A set of squares is knight-connected if when you add edges between squares which are a knight-jump apart you get a single connected component. The set (1,1), (2,2) is not knight-connected because it has two connected components, each with one square and no edges.

The third example is said to be both knight-connected AND horse-disjoint, while I understand that no horse can attack another one, I don't see which squares contribute to the knight-connected set.

There is only ever one set of squares under consideration at a time. It was perhaps a mistake to label them with H.

Then I do not understand what I have to count in F(n), the sum of distinct horse-disjoint sets + distinct knight-connected sets + sets that are both horse-disjoint and knight-connected? Or only distinct sets that are both horse-disjoint AND knight-connected?

The number of sets S for which S is both horse-disjoint and knight-connected.

[michelito]

Thanks for the detailed explanation.
Now it is definitely clearer.

regards