Puzzle time! (1 Viewer)

[GoldyOrNugget]

I know how much y'all like logic puzzles...

Alice and Bob are playing a game in a sealed empty room. Alice is blindfolded and Bob gives her two marbles of identical size, weight and texture. Bob claims that the marbles are of different colours, but Alice believes they are identical. By interacting with Bob, find a process that allows Alice to ascertain, with arbitrarily high probability, whether the marbles are identical.

It's not a lateral thinking problem, it's a maths problem. In fact I got it off mathoverflow.

HINT: if the marbles are identical, then Bob can’t differentiate between them either

 

[GoldyOrNugget]

Part B, for those who've done a discrete maths course:

Alice and Bob are looking at a large graph G. Bob claims that the graph contains a Hamiltonian cycle, but doesn’t want to reveal any information about the cycle (e.g. whether any particular edge in G is in the cycle) to Alice. By interacting with Bob, give a process by which Alice can ascertain, with arbitrarily high probability, whether or not Bob has in fact found Hamiltonian cycle – without Bob conveying any information that facilitates Alice's search for the cycle.

No hints for this one.