Can it be proven that 11. 0-0-0+ is legal in this position? 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.
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.