Settings

Theme

How to Cheat with Math – The Russian Cards Problem

winux-arch.github.io

18 points by winux-arch a year ago · 7 comments

Reader

rawling a year ago

Does "the sum of my cards modulo 7 is [x]" work? It should let Bob know what the missing card is but I can't tell if it conveys sufficiently little information to Eve for it to count.

  • ashdnazg a year ago

    The article's definition of not revealing information is a bit unclear, but if we understand it as Eve not knowing who holds any single card, your solution seems to work. At least assuming the following code is correct :)

    import itertools import functools

    for eve_card in range(7): cards_left = set(range(7)) cards_left.remove(eve_card)

        mod_to_cards = [[], [], [], [], [], [], []]
    
        for c in itertools.combinations(cards_left, 3):
            mod = sum(c) % 7
            mod_to_cards[mod].append(set(c))
    
        for combs in mod_to_cards:
            i = functools.reduce(lambda x, y: x.intersection(y), combs)
            if len(i) != 0:
               print("intersection", eve_card, combs, i)
    
            u = functools.reduce(lambda x, y: x.union(y), combs)
            if len(u) != 6:
               print("union", eve_card, combs, u)
  • BoiledCabbage a year ago

    Is the modulo required? Is just "The sum of my cards is x" sufficient?

    • ashdnazg a year ago

      Yes. For instance, if a player says the sum of their cards is 3, Eve immediately knows they have cards 0, 1 and 2.

ninja3925 a year ago

The advised reader could devise a solution using public / private key where: - Alice communicates her public key - Bob communicates his - Alice encoders her cards with Bob’s public key - Bob does the same

Problem solved!

Keyboard Shortcuts

j
Next item
k
Previous item
o / Enter
Open selected item
?
Show this help
Esc
Close modal / clear selection