A few basic facts I notice:
- The breakthrough threat of ...b4, cxb4, and ...c3 prevents the White
king from leaving the square a1-d4, namely we must rule out a winning plan of running to the kingside and gobbling up the black pawns on g4 etc.
- The a6-b7 structure keeps Black's king confined, both spatially and temporally, to b8-a7 (or c7).
- Black can never make a passed pawn on the kingside due to the natural structure of his pawns there. In fact, left to their own devices, Black's 4 pawns will eventually run out of moves.
It therefore pops out at me that fact 2 and 3 combined make for a natural zugzwang challenge, where we must time a winning position right, i.e., reach a position where Black's king is on a7, White's is on a5, it's Black's move, and Black has run out of pawn moves on the kingside. In that scenario, Black must move ...Kb8, wherein we move in with Kb6 and mate next move (a7#). Black can also jettison pawns earlier with ...b4 and ...a3 but then the win is trivial (just take the pawns).
The final fact we need to utilize is that White's king has ample squares - all of a2, a1, b1, c1, c2, d1, and d2 are available to "lose" tempi whenever required. It seems to me that combining all these facts makes for an executable winning plan.
So to elaborate a bit on what I'm thinking - we make a baseline assumption that Black's MO is to avoid moving his kingside pawns for as long as possible, and instead to shuffle with Ka7-Kb8 whenever he can. This draws out defeat. Then:
- Stage 1 is to get White's king to a5 while Black's is on a7. So, 1. Kd2 Ka7 2. Kc1 Kb8 3. Kb1 Ka7 4. Ka1 (triangulation required to time it right) Kb8 5. Ka2 Ka7 6. Ka3 Kb8 7. Kb4 Ka7 8. Ka5. Move counter: 8
- At this point, we rule out 8...Kb8 due to 9. Kb6 and mate next move; we rule out 8...a3 and ...b4 because White just captures; so Black is forced to make a pawn move on the kingside, e.g. 8...f6.
- Here, White must lose a tempo and return to the same position but with Black to move. To do this, White must retreat and start the process again, i.e. traverse b4-a3-a2-a1-b1-a2-a3-b4-a5 (9 moves), as Black shuffles Ka7-b8. The point is that each time the key Ka5-Ka7 position is reached at the end of the cycle, Black must concede a pawn move on the kingside. Including the initial pawn move (8...f6), Black has a maximum of 10 total tempi to deploy on the kingside - ...f6, ...g6, ...h6, ...f5, ...g5, ...h5, ...f4, ...h4, ...f3, and ...h3. (White of course doesn't capture unless to capture back; we disregard any ...fxg3 because White's recapture cancels out the tempo and thus doesn't maximize Black's time-wasting.) Repeating the 9-move White king path for 10 cycles of kingside pawn moves yields 90 more moves. Move counter: 98
- I'm envisioning now a position where Black's pawns are amassed like f3-g4-g5-h3, i.e. completely blocked, and we have the key Ka5-Ka7 position. Here Black must start jettisoning pawns with 98...a3 or 98...b4.
With helpful confirmatory feedback from @Rewan Demontay, I decided to forge ahead from where I left off. Brute-force calculation becomes the name of the game, but so be it.
At the juncture described at the end of step 4 above, with White's last move being 98. Kb4-a5, there are two moves that need to be analyzed: 98...a3 and 98...b4. With the correct response from White, they turn out to be transpositions, so we focus on the former:
98...a3. 99. bxa3 b4 is forced, whereupon White must clearly capture b4, but has a choice to make in how to do so (100. cxb4, 100. axb4, or 100. Kxb4). We eliminate taking with the c-pawn because it lets Black's c4-pawn promote. Keeping in mind the optimization memo, that leaves us with two choices to consider:
- 100. Kxb4, with the wrap-around plan of xc4-d4-e5-e6-d6-c7. (Note that 98...b4 leads to a simple transposition to this juncture after 99. Kxb4 a3 100. bxa3.) From there, queening on b8 and mating along the b-file becomes White's fastest way to mate. The naive plan is to play 100...Kb8 101. Kxc4 Ka7 102. Kd4 Kb8 103. Ke5 Kc7 (to bump-check d6) 104. Ke6 (triangulation) Kb8 105. Kd6 Ka7 106. Kc7 Kxa6 107. b8Q Ka5 108. Qb4+ Ka6 109. Qb6#, setting a benchmark of mate in 109 moves.
- 100. axb4 is more direct in its hopes of queening as quickly as possible. But can it beat 109 moves? Unfortunately, 100...Kb8 101. b5 Ka7 leaves us in a precarious position - there are so many variations to consider! But the tag says
no-computers, so I took the plunge. (Note that 101. Kb6 is impossible due to stalemate and 101...cxb5 is not optimal for Black given 102. Kb6.)
- 102. b6+ Kb8 103. a7+ Kxb7 104. a8Q+ Kxa8 105. Ka6 Kb8 106. b7 Kc7 107. Ka7 Kd7 allows Black to escape checkmate within the 109-move mark set above.
- 102. bxc6 Kb8 103. Kb4 (sidestepping stalemate to let the pawns do their thing) creates yet another fork in the road: (i) 103...Ka7 104. c7 Kxa6 105. c8Q and mate next move (not 105. b8Q stalemate), or (ii) 103...Kc7 104. a7, at which point the number of possibilities spirals out of puzzle-like control and I'm going to assume White can't mate within the 109-move mark. So 100. Kxb4 is superior and we rule out 100. axb4.
Great, so is the answer is 109 moves? Not quite. There is further optimization to be done. In the position occurring after 98...b4 99. Kxb4 a3 100. bxa3, or equivalently 98...a3 99. bxa3 b4 100. Kxb4, there is a winning idea that I had an "aha" moment for. The key is to replace move 104, the triangulation with 104. Ke6, with 104. c4!! - a beauty that not only "loses" a tempo, but controls the square b5. The newfound control of b5 becomes critical in allowing White to shave off a move to checkmate after queening - there opens the possibility of an earlier Qa7# on move 108. Wow,
Therefore the final full line, starting with Black to move at move 100, is 100...Kb8 101. Kxc4 Ka7 102. Kd4 Kb8 103. Ke5 Kc7 104. c4 Kb8 105. Kd6 Ka7 106. Kc7 Kxa6 107. b8Q Ka5 108. Qa7#.
I must note that 104. a4 also seems to work, and that running for the kingside with 104...Kd7 doesn't affect the solution, as it also leads to mate in the same number of moves after 105. b8Q Ke7 106. Qc7+ Kf8 107. Kf6 and mate next move. Therefore the final answer is checkmate in 108 moves. An absolutely exquisite puzzle beautified by move 104.