A Hunt for Darvin - Permanent Quest

[Demonic God]

This quest was originally ran during the 2020 anniversary - here.

After nearly a year, I happened to discuss this quest with @Aia del Mana, who had generously offered to sponsor this into a permanent quest. In essence, the quest is identical, though, after it has proven to be of... quite high difficulty, the requirements has been reduced somewhat, and the rewards increased to reflect it.

The quest will be, as following:

A hunt for Darvin.

• Darvin, the advanced Aramor, had escaped into a new section of the labyrinth, and needs to be captured. This new section is a huge interconnected area, akin to a chessboard.
• Each turn, A25 holders, using their given A25 tools, freely teleports into a tile of their choosing.
• Each turn, Darvin surfs the heat current, moving to a different adjacent tile. He cannot move to tiles diagonal to his current location, as there would be no heatvein connecting the two square. He cannot remain still, as such is the nature that he was given.
• Each party action happen simultaneously. The tool holders and Darvin must move, at the same turn, to the same square, for Darvin to be considered "found".
• By chance, magic, or unknown mechanic within the realm itself, almost like quantum physics, he cannot be found unless, by deduction, he must be found. Should one seek him out at random, even how improbable it would be, he shall never be found.
• Noticing these rules, Chew deducted a simple way method: to organize a massive manhunt, placing players in every tile. Gets the job done, gets it done fast. However, Mur insist that the A25 tools may only be handed out to as few people as possible. To this end, find the methods needed, and the numbers of tools to hand out, to solve the following situations:

1. If the labyrinth size is 3x3. For this simple case, simply pointing out a correct pattern (with the minimum number of tools holders), would suffice. Those who solve this should expect a spell document to celebrate their success.
2. If the labyrinth size is 5x5. A detailed mathematical proof, showing not only the pattern, but that it is indeed the minimum number of tool holder needed. A wishpoint will be rewarded.
3. If the labyrinth size is unknown (n x n). A detailed mathematical proof, showing the pattern/rules is required. A single selection between a colored Winderwild, Elemental, or Pope, shall be rewarded. This is not first-come, first-served, anyone who managed to meet the requirements shall be rewarded all the same. I could provide aid and discussion if you want to challenge this - as this task is quite difficult.

In mathematical terms (or simplified terms):

• Darvin will be on a chessboard-like grid. Each turn, he must move one tile, up, down, left or right.
• Each turn, you choose a number of squares to find Darvin.
• Actions happen simultaneously. Darvin is considered found, if he and you chose the same square.
• Darvin cannot be found at random. You must prove that he must be found using your pattern. Think of it as a strategy game, and that he knows your strategy from the very start. Find a pattern that he can't beat.
• You must find a pattern that requires the least amount of searches per turn.

1. Find the solution if the square is 3x3. No proof required, just the pattern. I've been authorized to grant you a spell-document should you submit a valid solution.
2. Find the solution if the square is 5x5. Proof, including why the pattern is optimal (uses the least amount of searches per turn), is required. A wishpoint will be rewarded.
3. Find the general solution for an n x n square, showing the pattern, as well as the proof for why it is optimal. Aid may be provided if requested. You may choose between a colored Winderwild, Elemental, or Pope as your reward.

Rules:

• Solutions must be submitted in a private manner. Any private methods is acceptable, though I must warn that I do not check the ingame inbox often.
• Do not discuss, share, or collaborate.
• Please check your work thoroughly before submitting. If I feel like you're probing for the answer by having me pointing out mistakes, you may be disqualified. This applies mostly to reward 1, and somewhat for reward 2.

To clarify, for task 2 and 3, a detailed proof of not only how the pattern will work, but also why you can't find Darvin with less tool holders will be required. For task 1, simply showing a pattern would suffice, without much explanation needed.

If there's anything you need clarification on, feel free to DM or post a reply.

Winners:

Tier 1:

• @Aelis(as he finished it during the 2020 anniversary)
• @Kaya- May 7th, 2021

Tier 2:

• @Kaya- May 10th, 2021

Tier 3:

Edited May 10, 2021 by Demonic God

[Nep]

Just to clarify if I understand this correctly. He will never be randomly found just because I placed an A25 holder there - so he has to move to where I placed them the next time he moves. So essentially, we need a pattern that makes it impossible for him to move to a square where there is no A25 holder (with the minimum number of holders placed, so no covering the board with A25 people). Is that correct? 

[Demonic God]

39 minutes ago, Nepgear said:

Just to clarify if I understand this correctly. He will never be randomly found just because I placed an A25 holder there - so he has to move to where I placed them the next time he moves. So essentially, we need a pattern that makes it impossible for him to move to a square where there is no A25 holder (with the minimum number of holders placed, so no covering the board with A25 people). Is that correct? 

Yes. This is just me trying to be creative in writing that you need to prove that he must be captured, regardless of his movements or starting location.

Filling the board is an example of a strategy that works. Your goal is to find a strategy with the least amount of holders.

Edited March 19, 2021 by Demonic God

[Demonic God]

This is to announce/acknowledge that Kaya had sent me a correct submission for the 3x3 case. I'm eagerly waiting for her 5x5 submission!

[Demonic God]

Kaya has submitted a correct submission for 5x5! On top of that, they're also working on a general solution. Given the occasion, I'll also update a bit on the general case proof criteria, to make it a bit less ridiculously inappropriate.