A300576 -id:A300576 - cp's OEIS frontend

A331693 Number of Tom graphs with n vertices.

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 328, 705, 1576, 3551, 8179, 18980, 44559, 105111, 249426, 593484, 1416269, 3384581, 8099819, 19398194, 46487665, 111447044, 267260387, 641022947, 1537706522, 3688974818, 8850411933, 21234093757, 50946316856, 122234742311

Offset: 0

Bobby Jacobs, Jan 24 2020

nonn

This sequence is from a Project Euler problem called "Tom and Jerry". A cat named Tom and a mouse named Jerry play a game on a graph G. Each vertex of G is a mousehole. Jerry starts in one of the vertices. Every day, Tom tries to catch Jerry in one of the holes. If there is a vertex adjacent to Jerry's hole, then Jerry moves to one of the adjacent holes. A Tom graph is a graph on which Tom can always catch Jerry by following a sequence of holes.
All Tom graphs are loop-free graphs, but not all loop-free graphs are Tom graphs. The smallest loop-free graph that is not a Tom graph has 10 vertices:
        1
        |
        2
        |
        3
        |
        4
       / \
      5   8
     /     \
    6       9
   /         \
  7           10
From Hugo Pfoertner, Feb 20 2020 (Start):
The sequence is an equivalent of A005195 (number of forests with n unlabeled nodes), but made from trees that don't have the unlabeled 10-node graph shown above as a subgraph. This is described in the comment of A300576 and there is also a link to Christian Perfect's website.
In order to find a term of the current sequence, the number of trees containing the shown subgraph must be subtracted from the total number A000055. For n = 10 this is exactly one, for n = 11 it is trivially 4 and for n = 12 it is 19 (A130132).
The marked illustrations from the Steinbach graph catalog show these manually counted tree graphs.
The formulas of A005195 (Euler transform) can then be used to calculate the number of forests if the reduced number of trees A130131 is used instead of A000055. (End)
a(0) = 1: the empty graph is a Tom graph, since Jerry cannot hide from Tom. - Rainer Rosenthal, Mar 01 2020

			The graph
  1---2---3
is a Tom graph: Tom can follow the sequence 2, 2 to guarantee that he catches Jerry.
The graph
    1
   / \
  2---3
is not a Tom graph: Jerry always has 2 vertices to go to, and whatever vertex Tom picks, Jerry can choose another to evade Tom.

Seiichi Manyama, Table of n, a(n) for n = 0..2000
Project Euler, Problem 690: Tom and Jerry
Peter Steinbach, Simple Graphs - Trees, illustrations of the graphs, including an added marking of the relevant 4 cases for 11 nodes.
Peter Steinbach, Simple Graphs - Trees, illustrations of the graphs, including an added marking of the relevant 19 cases for 12 nodes.

Cf. A000055, A005195, A130131, A130132, A300576.

a(n) <= A005195(n) with equality only for n in {1, ..., 9}.

a(11)-a(12) from Hugo Pfoertner, Feb 20 2020

a(0), a(13)-a(33) from Rainer Rosenthal, Feb 29 2020

A386462 Box which a player should open at step n to catch as fast as possible a cat performing a random walk through 8 boxes.

Original entry on oeis.org

4, 7, 5, 2, 7, 4, 2, 5, 7, 7, 4, 2, 2, 4, 7, 7, 4, 2, 2, 4, 7, 7, 4, 4, 7, 2, 4, 7, 2, 5, 5, 2, 7, 4, 4, 7, 2, 5, 5, 2, 7, 4, 4, 7, 2, 5, 5, 2, 7, 4, 4, 7, 2, 5, 5, 2, 7, 4, 4, 7, 2, 5, 5, 2, 7, 4, 2, 5, 7, 7, 5, 2, 4, 7, 2, 5, 5, 2, 7, 4, 2, 5, 7, 7, 5, 2, 4

Offset: 1

Ruediger Jehn, Jul 22 2025

A cat is randomly hiding in one of 8 boxes and a single player tries to catch the cat. In each step, first the player opens a box, if the cat is found, the game is finished, if not the cat will move randomly one box to the left or one box to the right. If the cat is in box 1 it can only move to box 2 in the next step. A safe strategy to find the cat in no more than 12 steps is to open the boxes in this order: 2,3,4,5,6,7,7,6,5,4,3,2. On average this strategy takes 25963/4096 (6.339) steps to catch the cat. However, applying the strategy to open box a(n) at step n reduces the average duration of the game to 4.749593 which is a factor of 1.335 faster. Note, since the problem is symmetric also a mirrored strategy exists.

			a(1) = 4: If the player starts with box 1 (or 8) the average duration of the game exceeds the value of 4.7496 at least after 10 steps no matter in which order the player will open the next boxes. If the player starts with box 2 (or 7) the average duration of the game exceeds the value of 4.7496 at least after 25 steps and if the player starts with box 3 (or 6) the average duration of the game exceeds the value of 4.7496 at least after 11 steps. Hence opening box 4 (or 5 for the mirrored strategy) allows the player to catch the cat in the fastest way.

Ruediger Jehn, Optimal Strategies to Detect Randomly Walking Cat

Cf. A300576, A386463.

More terms from Jinyuan Wang, Jul 29 2025

A301337 Number of steps required in the worst case for two knights to find the princess in a castle with n rooms arranged in a line (Castle and princess puzzle).

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 4, 4, 6, 6, 6, 7, 8, 8, 10, 10, 10, 11, 12, 12

Offset: 1

Dmitry Kamenetsky, Mar 19 2018

The main entry for this problem is A300576. In this version there are two knights who are searching for the princess; each knight can search a different room.

			For n = 1, there is only room to search, so a(1) = 1.
For n = 2, the knights search both rooms, so a(2) = 1.
For n = 3, the knights can search the first two rooms twice, so a(3) = 2.
For n = 4 and 5, the knights can search the second and the fourth rooms twice, so a(4) = 2 and a(5) = 2.

Dmitry Kamenetsky, Optimal solutions

Cf. A300576, A301426.

It seems that for n >= 3:
  if n = 0 mod 6, then a(n) = (n/6)*4 - 1,
  if n = 1 or 2 mod 6, then a(n) = floor(n/6)*4,
  if n = 3, 4 or 5 mod 6, then a(n) = floor(n/6)*4 + 2.
i.e., a(n) = A302404(n-2).

A301426 Number of steps required in the worst case for three knights to find the princess in a castle with n rooms arranged in a line (Castle and princess puzzle).

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 6, 6, 7, 8, 8

Offset: 1

Dmitry Kamenetsky, Mar 21 2018

The main entry for this problem is A300576. In this version there are three knights who are searching for the princess; each knight can search a different room.

Dmitry Kamenetsky, Optimal solutions

Cf. A300576, A301337.

It seems that for n >= 3:
  if n = 3 mod 5, then a(n) = (n - 3)/5*2 + 1,
  otherwise a(n) = floor((n - 4)/5)*2 + 2.
This conjecture is a(n) = A194222(n) for n>2. - R. J. Mathar, Mar 27 2025

A386463 Box which a player should open at step n to catch a cat performing a random walk through 8 boxes to minimize the escape rate of the cat.

Original entry on oeis.org

1, 7, 7, 1, 2, 2, 4, 7, 7, 2, 3, 4, 7, 1, 8, 7, 2, 3, 7, 7, 6, 2, 2, 3, 6, 8, 1, 8, 7, 6, 1, 2, 3, 4, 7, 1, 8, 7, 2, 3, 7, 7, 6, 2, 2, 3, 6, 8, 1, 8, 7, 6, 1, 2, 3, 4, 7, 1, 8, 7, 2, 3, 7, 7, 6, 2, 2, 3, 6, 8, 1, 8, 7, 6, 1, 2, 3, 4, 7, 1, 8, 7, 2, 3, 7, 7, 6

Offset: 1

Ruediger Jehn, Jul 22 2025

A cat is randomly hiding in one of 8 boxes, and a single player tries to catch the cat. In each step, the player opens a box. If the cat is found, the game ends; if not, the cat will move randomly either to the box on the left or to the box on the right. If the cat is in box 1 or 8, it has a 50% probability of escaping. By using the optimal strategy, the cat's escape rate is minimized to 0.223305988. The average duration of the game is 5.35 steps. Note that, since the problem is symmetric, a mirrored strategy also exists.

			a(1) = 1: 0.223306 is an upper bound for the minimum escape rate. If the player starts with box 2 (or 7) the escape rate exceeds this value at least after 11 steps no matter in which order the player will open the next boxes. If the player starts with box 3 (or 6) the escape rate exceeds the bound at least after 7 steps and if the player starts with box 4 (or 5) the escape rate exceeds the bound at least after 6 steps. Hence opening box 1 (or 8 for the mirrored strategy) allows the player to minimize the escape rate of the cat.

Ruediger Jehn, Optimal Strategies to Detect Randomly Walking Cat

Cf. A300576, A386462.

More terms from Jinyuan Wang, Jul 27 2025

A301860 Number of steps required in the worst case for n knights to find the princess in a castle with rooms arranged in a (n+1) X (n+1) grid (Castle and princess puzzle).

Original entry on oeis.org

10, 12, 12, 14, 16

Offset: 2

Dmitry Kamenetsky, Mar 28 2018

The main entry for this problem is A300576. In this version there are n knights who are searching for the princess inside a grid; each knight can search a different room.
It is not possible to solve the n X n grid with fewer than (n-1) knights.
a(2) and a(3) were found by Robby Goetschalckx.

Dmitry Kamenetsky, Optimal solutions

Cf. A300576.

cp's OEIS Frontend

A331693 Number of Tom graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A386462 Box which a player should open at step n to catch as fast as possible a cat performing a random walk through 8 boxes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A301337 Number of steps required in the worst case for two knights to find the princess in a castle with n rooms arranged in a line (Castle and princess puzzle).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A301426 Number of steps required in the worst case for three knights to find the princess in a castle with n rooms arranged in a line (Castle and princess puzzle).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A386463 Box which a player should open at step n to catch a cat performing a random walk through 8 boxes to minimize the escape rate of the cat.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A301860 Number of steps required in the worst case for n knights to find the princess in a castle with rooms arranged in a (n+1) X (n+1) grid (Castle and princess puzzle).

Views

Author

Keywords

Comments

Links

Crossrefs