Options

Just For Fun 4

I was reminded of this by my discussion with John in the comments to Lecture 11.

In 1969 the Mathematician Hans Freuden came up with the following puzzle:

\(A\) says to \(S\) and \(P\): I have chosen two integers \(x\), \(y\) such that \(1 < x < y\) and \(x + y ≤ 100\). In a moment, I will inform \(S\) only of \(s = x + y\), and \(P\) only of \(p = xy\). These announcements remain private. You are required to determine the pair \((x, y)\). He acts as said. The following conversation now takes place:

i. P says: “I do not know it.”

ii. S says: “I knew you didn’t.”

iii. P says: “I now know it.”

iv. S says: “I now also know it.”

Determine the pair \((x, y)\).

(translated from Dutch by van Ditmarsch et al. here)

I think this puzzle is cute, hopefully someone here might find it fun too.

Comments

  • 1.
    edited April 2018

    Cool! Thanks for the puzzle, Matthew! It was fun – I got a bit confused at the second step, when S says: “I knew you didn’t,” but I think I found my way through. My attempt is a small computer program; otherwise it seems quite laborious. Here's the Python implementation (not very clean, but should do the job):

    from collections import (
        defaultdict,
        Counter,
    )
    
    flatten = lambda xss: sum(xss, [])
    
    pairs = [
        (x, y)
        for x in range(2, 100)
        for y in range(2, 100)
        if x < y and x + y <= 100]
    print(len(pairs))
    
    # P says: "I do not know it."
    counts_p = Counter([x * y for x, y in pairs])
    pairs_1 = [(x, y) for (x, y) in pairs if counts_p[x * y] > 1]
    print(len(pairs_1))
    
    # S says: "I knew you didn't."
    sums = defaultdict(list)
    for x, y in pairs:
        sums[x + y].append((x, y))
    pairs_2 = flatten([
        ps for _, ps in sums.items()
        if all(counts_p[x * y] > 1 for (x, y) in ps)])
    print(len(pairs_2))
    
    # P says: "I now know it."
    pairs_3 = sorted(set(pairs_1) & set(pairs_2))
    counts_p = Counter([x * y for x, y in pairs_3])
    pairs_3 = [(x, y) for (x, y) in pairs_3 if counts_p[x * y] == 1]
    print(len(pairs_3))
    
    # S says: "I now also know it."
    counts_s = Counter([x + y for x, y in pairs_3])
    pairs_4 = [(x, y) for (x, y) in pairs_3 if counts_s[x + y] == 1]
    print(len(pairs_4))
    
    print(pairs_4[0])
    

    Edit: The answer that I got was the pair (4, 13).

    Comment Source:Cool! Thanks for the puzzle, Matthew! It was fun – I got a bit confused at the second step, when S says: “I knew you didn’t,” but I think I found my way through. My attempt is a small computer program; otherwise it seems quite laborious. Here's the Python implementation (not very clean, but should do the job): from collections import ( defaultdict, Counter, ) flatten = lambda xss: sum(xss, []) pairs = [ (x, y) for x in range(2, 100) for y in range(2, 100) if x < y and x + y <= 100] print(len(pairs)) # P says: "I do not know it." counts_p = Counter([x * y for x, y in pairs]) pairs_1 = [(x, y) for (x, y) in pairs if counts_p[x * y] > 1] print(len(pairs_1)) # S says: "I knew you didn't." sums = defaultdict(list) for x, y in pairs: sums[x + y].append((x, y)) pairs_2 = flatten([ ps for _, ps in sums.items() if all(counts_p[x * y] > 1 for (x, y) in ps)]) print(len(pairs_2)) # P says: "I now know it." pairs_3 = sorted(set(pairs_1) & set(pairs_2)) counts_p = Counter([x * y for x, y in pairs_3]) pairs_3 = [(x, y) for (x, y) in pairs_3 if counts_p[x * y] == 1] print(len(pairs_3)) # S says: "I now also know it." counts_s = Counter([x + y for x, y in pairs_3]) pairs_4 = [(x, y) for (x, y) in pairs_3 if counts_s[x + y] == 1] print(len(pairs_4)) print(pairs_4[0]) Edit: The answer that I got was the pair (4, 13).
  • 2.

    Great job Dan! You blazed through that one.

    Here's another one from Terry Tao's blog:

    There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

    [for the purposes of this logic puzzle, “highly logical” means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.]

    Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople).

    One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.

    One evening, he addresses the entire tribe to thank them for their hospitality.

    However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.

    What effect, if anything, does this faux pas have on the tribe?

    Comment Source:Great job Dan! You blazed through that one. Here's another one from [Terry Tao's blog](https://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/): > There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth). > > [for the purposes of this logic puzzle, “highly logical” means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.] > > Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople). > >One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe. > >One evening, he addresses the entire tribe to thank them for their hospitality. > >However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”. > >What effect, if anything, does this faux pas have on the tribe?
  • 3.

    It's great that you're posting puzzles, Matthew! I suggest posting them with titles like "Just For Fun \(n\)", one discussion per puzzle, so that I can "announce" them one at a time. Right now if you look at Recent Discussions you'll see that "Just For Fun 3" is being announced. I will take one of your puzzles here and make it "Just For Fun 4".

    Superficially it seems that Dan Oneata crushed your first puzzle, depriving it of fun. However, I'm sure there's a whole sub-branch of mathematics devoted to puzzles featuring "I don't know it", "I don't know it", "I knew you didn't know it", etc. So there would be more fun available if someone wanted it.

    Comment Source:It's great that you're posting puzzles, Matthew! I suggest posting them with titles like "Just For Fun \\(n\\)", one discussion per puzzle, so that I can "announce" them one at a time. Right now if you look at [Recent Discussions](https://forum.azimuthproject.org/discussions) you'll see that "Just For Fun 3" is being announced. I will take one of your puzzles here and make it "Just For Fun 4". Superficially it seems that Dan Oneata crushed your first puzzle, depriving it of fun. However, I'm sure there's a whole sub-branch of mathematics devoted to puzzles featuring "I don't know it", "I don't know it", "I knew you didn't know it", etc. So there would be more fun available if someone wanted it.
  • 4.

    However, I'm sure there's a whole sub-branch of mathematics devoted to puzzles featuring "I don't know it", "I don't know it", "I knew you didn't know it", etc. So there would be more fun available if someone wanted it.

    Yeah, these problems are related to "Epistemic Logic". There's a pretty large literature on this subject.

    It's also related to consensus algorithms, secure multiparty computing, and game theory. And of course the lattice of partitions...

    Comment Source:> However, I'm sure there's a whole sub-branch of mathematics devoted to puzzles featuring "I don't know it", "I don't know it", "I knew you didn't know it", etc. So there would be more fun available if someone wanted it. Yeah, these problems are related to "Epistemic Logic". There's a pretty large literature on this subject. It's also related to consensus algorithms, secure multiparty computing, and game theory. And of course the lattice of partitions...
Sign In or Register to comment.