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).

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

Offset

1,3

Comments

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.

Links

Table of n, a(n) for n=1..20.

Dmitry Kamenetsky, Optimal solutions

Formula

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).

Example

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.

Crossrefs

Cf. A300576, A301426.

Sequence in context: A225499 A215473 A071988 * A302404 A029050 A066920

Adjacent sequences: A301334 A301335 A301336 * A301338 A301339 A301340

Keyword

nonn,more

Author

Dmitry Kamenetsky, Mar 19 2018

Status

approved