user-1: Because the chess site this was on takes its puzzles from real games and gives the move numbers, potential solvers knew that the following position was reached after exactly 10 moves by each player.
[fen "2bk2nr/p1p2ppp/2p5/2p5/2P1P3/2N5/Pr3PPP/R3KB1R w - - 0 11"]



Given that information, can one prove that 11. 0-0-0+ in the above diagram is legal?

(i.e., that neither the white King nor the Ra1 has moved so far)

It seems to me like that's not enough total moves for white to have spent two

moves "shuffling", but I can't come up with any proof or a counterexample-game.


user3806: We can deduce nine moves that white absolutely had to make to get to this position.

At least three moves were required to put white's pawns and its queen's knight there (3 total)
Either the c- or d-rank pawn was captured after it moved. That's another move (4 total)
The pieces captured on c5 and c6, whatever they were, needed at least two moves to get there. That's four extra moves. (8 total)
If the piece captured in c6 isn't white's missing knight (which needs 3 move to get there), that knight had to be captured in d4 by the e pawn, and that means the queen or bishop had to capture it on their way to capture on the c-file, adding another move anyway (not to mention what it means about the missing white pawn). That's another move. (9 total)

This position without possible castling requires two more moves (moving the castle or king back and forth), and it's impossible to fit them in.

user8201: Reasoning by hand about proof games is fine, but is more fun for positions which have been designed by humans to be solvable and to contain interesting features. Automatic verification is standard for all but the most complex of compositions, and is normally done by specialized engine, of which there are several available for free online.
IMHO, the best proof game engine for OP's position is Natch. Running for 49.03 seconds, it found 2493 "solutions" for how to reach the position in exactly 10.0 moves. None of them contained the strings e1, a1 (or 0-0-0!) and so there is no way that White could have lost castling rights in the prior play. 
Notes:
(1) The way that Natch reports consolidates results to reduce the length of the report, so there are rather more than 2493 actual proof games, but that doesn't affect the conclusion.
(2) What about other engines? Popeye is not the most performant for this kind of position, and Euclide would have terminated as soon as it found that there wasn't a unique solution. But both are excellent engines.

user3594: Ok after playing around with a couple of lines, I finally found one line that shows it's still perfectly legal to play long castles for white at move 11, here it is:
[Title "possible 11.O-O-O+"]
[StartFlipped "0"]
[fen "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"]

1.e4 e5 2.Nf3 Nc6 3.c4 Rb8 4.d4 exd4 5.Nxd4 Bc5 6.Nxc6 dxc6 (6... bxc6 7.Be3 d6 8.Bxc5 dxc5 9.Qxd8+ Kxd8 10.Nc3 Rxb2 11.O-O-O+) 7.Qxd8+ Kxd8 8.Be3 b6 9.Bxc5 bxc5 10.Nc3 Rxb2 11.O-O-O+

Added another continuation, taking on c6 with the b-pawn, same position results and same number of moves needed!
To conclude, because I reached the given position in exactly 11 moves, and did not play any redundant moves (e.g. Nf3 then back to Ng1 again), it means that all the played moves were necessary, their order can be different, but point is there was no spare move to use and destroy white's castling (e.g. an impossible scenario would be black exchanging queen on d1, Kxd1, then black plays Kxd8, and white goes back to e1, but that took up 2 more moves than the line I showed, so impossible to reach the position you're looking for in 11 moves after such line)
Long story short, castling is perfectly possible here, and in 11 moves black could not have done anything to prevent us from castling and still manage to reach the final position we want. Interesting post by the way, +1.
Alternatively one can also just look at the final position and count the necessary number of moves, that must take place for this position, I elaborate: have the final position in mind: let's take black's point of view: Pawn moves needed to obtain the final position:

e5
exd4 (why black has to take on d4 and not white on e5 is explained in the diagramm below)
bxc6 or dxc6
b6 or d6 
bxc5 or dxc5, 

Development moves: 

Nc6 (to be captured on c6, otherwise there cannot be a pawn on c6 and not have knight on b8)
Bc5 (otherwise c5 pawn impossible)
Rb8 (otherwise Rxb2 never possible)

Remaining necessary moves: Queen d8 capture and pawn b2 capture:

Kxd8
Rxb2

And we find ourselves at the 11th move again, where all we did was just consider the most straighforward ways our pieces could end up where they are in the shown puzzle. 
Let's see if we reach the same position via another path, showing why exd4 is the fastest way to reach the final position:
[Title "Why black must take on d4 and not white on e5:"]
[StartFlipped "0"]
[fen "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"]

1.e4 e5 2.Nf3 Nc6 3.c4 Rb8 4.d4 Bc5 5.dxe5 Nxe5 6.Nxe5 d6 7.Nc6 bxc6 8.Be3 Rxb2 9.Bxc5 dxc5 10.Qxd8+ Kxd8 11.Nc3 

Here we are at move 11 and we still have to play Nc3... clearly because we played 2 knight moves for black.
Finally let's demonstrate why in the fastest path to the final position, white has to be taking on d8 (queen exchange) and not the other way around:  
[Title "A line white cannot castle but the final position cannot be reached within the 10 required moves (so impossible for our purposes)"]
[StartFlipped "0"]
[fen "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"]

1.e4 e5 2.Nf3 Nc6 3.c4 Rb8 4.d4 exd4 5.Nxd4 Bc5 6.Nxc6 dxc6 7.Nc3 Qxd1+ 8.Kxd1 b6 9.Be3 Kd8 10.Bxc5 bxc5 11.Ke1 Rxb2

We lost 2 king moves(capture on d1 then back to e1) for white in this line, hence the Rxb2 only happening at the 11th move.
So it was shown that the only line leading up the the final position within 10 moves, is one where white still must be able to castle.
EDIT: A summary of the discussed elements in the comments:
The proof presented in this answer is purely deduction based, in the sense that the simple fact of having reached the position in exactly 11 moves without having made any redundant (or insensitive to the position) moves, implies that 11.O-O-O+ should be legal without exception. 
What does redundant mean here? "Redundant moves": here, are defined as moves that do not bring us any closer to the final position, or would even deviate us from it. For example playing Nf3, then back to Ng1, would be redundant. Playing Be2 then back to Bf1 would be redundant, and so on. 
Point being, in any variation, you may come up with, that would take away white's castling rights, will imperatively entail redundant moves, that will in turn delay reaching the final position by a couple of moves. (As an exercise, try some of your ideas, it is interesting, and see how many moves it takes you.)
Looking at such problem from a combinatorics point of view, may be possible, but would be too complicated as we're looking at a depth of moves(tree lines) resulting from 11 moves. Instead, like most chess puzzles, one has to look at it from a purely heuristic point of view, and find the right ideas that would go in the direction of proving the question at hand. Finally, in chess, one usually has an easier time looking for counter examples(proof by contradiction), which is why it is encouraged to look into some of the lines on your own.

-1: <p>Because the chess site this was on takes its puzzles from real games and gives the move numbers, potential solvers knew that the following position was reached after exactly 10 moves by each player.</p>

<pre><code>[fen "2bk2nr/p1p2ppp/2p5/2p5/2P1P3/2N5/Pr3PPP/R3KB1R w - - 0 11"]
</code></pre>

<p><br></p>

<blockquote>
  <p>Given that information, can one prove that 11. 0-0-0+ in the above diagram is legal?</p>
</blockquote>

<p>(i.e., that neither the white King nor the Ra1 has moved so far)</p>

<p><br></p>

<p>It seems to me like that's not enough total moves for white to have spent two
<br>
moves "shuffling", but I can't come up with any proof or a counterexample-game.
<br><br></p>
 3806: <p>We can deduce nine moves that white absolutely had to make to get to this position.</p>

<ul>
<li>At least three moves were required to put white's pawns and its queen's knight there (3 total)</li>
<li>Either the c- or d-rank pawn was captured after it moved. That's another move (4 total)</li>
<li>The pieces captured on c5 and c6, whatever they were, needed at least two moves to get there. That's four extra moves. (8 total)</li>
<li>If the piece captured in c6 isn't white's missing knight (which needs 3 move to get there), that knight had to be captured in d4 by the e pawn, and that means the queen or bishop had to capture it on their way to capture on the c-file, adding another move anyway (not to mention what it means about the missing white pawn). That's another move. (9 total)</li>
</ul>

<p>This position without possible castling requires two more moves (moving the castle or king back and forth), and it's impossible to fit them in.</p>
 8201: <p>Reasoning by hand about proof games is fine, but is more fun for positions which have been designed by humans to be solvable and to contain interesting features. Automatic verification is standard for all but the most complex of compositions, and is normally done by specialized engine, of which there are several available for free online.</p>

<p>IMHO, the best proof game engine for OP's position is Natch. Running for 49.03 seconds, it found 2493 "solutions" for how to reach the position in exactly 10.0 moves. None of them contained the strings e1, a1 (or 0-0-0!) and so there is no way that White could have lost castling rights in the prior play. </p>

<p>Notes:<br>
(1) The way that Natch reports consolidates results to reduce the length of the report, so there are rather more than 2493 actual proof games, but that doesn't affect the conclusion.<br>
(2) What about other engines? Popeye is not the most performant for this kind of position, and Euclide would have terminated as soon as it found that there wasn't a unique solution. But both are excellent engines.</p>
 3594: <p>Ok after playing around with a couple of lines, I finally found one line that shows it's still perfectly legal to play long castles for white at move 11, here it is:</p>

<pre><code>[Title "possible 11.O-O-O+"]
[StartFlipped "0"]
[fen "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"]

1.e4 e5 2.Nf3 Nc6 3.c4 Rb8 4.d4 exd4 5.Nxd4 Bc5 6.Nxc6 dxc6 (6... bxc6 7.Be3 d6 8.Bxc5 dxc5 9.Qxd8+ Kxd8 10.Nc3 Rxb2 11.O-O-O+) 7.Qxd8+ Kxd8 8.Be3 b6 9.Bxc5 bxc5 10.Nc3 Rxb2 11.O-O-O+
</code></pre>

<p>Added another continuation, taking on c6 with the b-pawn, same position results and same number of moves needed!</p>

<p>To conclude, because I reached the given position in exactly 11 moves, and did not play any redundant moves (e.g. Nf3 then back to Ng1 again), it means that all the played moves were necessary, their order can be different, but point is there was no spare move to use and destroy white's castling (e.g. an impossible scenario would be black exchanging queen on d1, Kxd1, then black plays Kxd8, and white goes back to e1, but that took up 2 more moves than the line I showed, so impossible to reach the position you're looking for in 11 moves after such line)</p>

<p>Long story short, castling is perfectly possible here, and in 11 moves black could not have done anything to prevent us from castling and still manage to reach the final position we want. Interesting post by the way, +1.</p>

<p>Alternatively one can also just look at the final position and count the necessary number of moves, that must take place for this position, I elaborate: have the final position in mind: let's take black's point of view: Pawn moves needed to obtain the final position:</p>

<ol>
<li>e5</li>
<li>exd4 (why black has to take on d4 and not white on e5 is explained in the diagramm below)</li>
<li>bxc6 or dxc6</li>
<li>b6 or d6 </li>
<li>bxc5 or dxc5, </li>
</ol>

<p>Development moves: </p>

<ol start="6">
<li>Nc6 (to be captured on c6, otherwise there cannot be a pawn on c6 and not have knight on b8)</li>
<li>Bc5 (otherwise c5 pawn impossible)</li>
<li>Rb8 (otherwise Rxb2 never possible)</li>
</ol>

<p>Remaining necessary moves: Queen d8 capture and pawn b2 capture:</p>

<ol start="9">
<li>Kxd8</li>
<li>Rxb2</li>
</ol>

<p>And we find ourselves at the 11th move again, where all we did was just consider the most straighforward ways our pieces could end up where they are in the shown puzzle. </p>

<p>Let's see if we reach the same position via another path, showing why exd4 is the fastest way to reach the final position:</p>

<pre><code>[Title "Why black must take on d4 and not white on e5:"]
[StartFlipped "0"]
[fen "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"]

1.e4 e5 2.Nf3 Nc6 3.c4 Rb8 4.d4 Bc5 5.dxe5 Nxe5 6.Nxe5 d6 7.Nc6 bxc6 8.Be3 Rxb2 9.Bxc5 dxc5 10.Qxd8+ Kxd8 11.Nc3 
</code></pre>

<p>Here we are at move 11 and we still have to play Nc3... clearly because we played 2 knight moves for black.</p>

<p>Finally let's demonstrate why in the fastest path to the final position, white has to be taking on d8 (queen exchange) and not the other way around:  </p>

<pre><code>[Title "A line white cannot castle but the final position cannot be reached within the 10 required moves (so impossible for our purposes)"]
[StartFlipped "0"]
[fen "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"]

1.e4 e5 2.Nf3 Nc6 3.c4 Rb8 4.d4 exd4 5.Nxd4 Bc5 6.Nxc6 dxc6 7.Nc3 Qxd1+ 8.Kxd1 b6 9.Be3 Kd8 10.Bxc5 bxc5 11.Ke1 Rxb2
</code></pre>

<p>We lost 2 king moves(capture on d1 then back to e1) for white in this line, hence the Rxb2 only happening at the 11th move.</p>

<p>So it was shown that the only line leading up the the final position within 10 moves, is one where white still must be able to castle.</p>

<p><strong>EDIT:</strong> A summary of the discussed elements in the comments:</p>

<p>The proof presented in this answer is purely deduction based, in the sense that the simple fact of having reached the position in exactly 11 moves without having made any redundant (or insensitive to the position) moves, implies that 11.O-O-O+ should be legal without exception. </p>

<p><em>What does redundant mean here?</em> "Redundant moves": here, are defined as moves that do not bring us any closer to the final position, or would even deviate us from it. For example playing Nf3, then back to Ng1, would be redundant. Playing Be2 then back to Bf1 would be redundant, and so on. </p>

<p>Point being, in any variation, you may come up with, that would take away white's castling rights, will imperatively entail redundant moves, that will in turn delay reaching the final position by a couple of moves. (As an exercise, try some of your ideas, it is interesting, and see how many moves it takes you.)</p>

<p>Looking at such problem from a combinatorics point of view, may be possible, but would be too complicated as we're looking at a depth of moves(tree lines) resulting from 11 moves. Instead, like most chess puzzles, one has to look at it from a purely heuristic point of view, and find the right ideas that would go in the direction of proving the question at hand. Finally, in chess, one usually has an easier time looking for counter examples(proof by contradiction), which is why it is encouraged to look into some of the lines on your own.</p>
