Puzzle time - How many bits
-
wrote on 11 Jul 2021, 23:29 last edited by jon-nyc 7 Nov 2021, 23:30
Klaus and Horace expect to be in a situation of severely limited communication, at which time Klaus will know which two of 16 football teams played a game, and Horace will know who won.
How many bits must be communicated between Klaus and Horace in order for the former to find out who won?
-
wrote on 11 Jul 2021, 23:32 last edited by
So I assume the obvious solution requires 4 bits and you are asking us how to get by with less?
-
wrote on 11 Jul 2021, 23:34 last edited by Klaus 7 Nov 2021, 23:36
Does H know what K knows? Does H know what K wants to know? Can they have a common strategy they both know about?
-
wrote on 11 Jul 2021, 23:43 last edited by
What is K wearing?
-
wrote on 11 Jul 2021, 23:53 last edited by
-
wrote on 12 Jul 2021, 00:18 last edited by jon-nyc 7 Dec 2021, 00:18
Yes find something smaller than 4.
I found 3 cleanly, and one solution that maxes at 3 with expected value 2.5 but it might be cheating. Haven’t seen official solution.
And of course they can have a strategy in common and are both aware of the 16 teams.
-
wrote on 12 Jul 2021, 01:15 last edited by
May be I can cheat by pre-compiling a dictionary of all possible outcomes and then use the timing of signal transmission to index into that dictionary. In that case only one “pulse” needs to be sent at the right time, which you can then argue is merely “one bit.”
-
May be I can cheat by pre-compiling a dictionary of all possible outcomes and then use the timing of signal transmission to index into that dictionary. In that case only one “pulse” needs to be sent at the right time, which you can then argue is merely “one bit.”
wrote on 12 Jul 2021, 01:46 last edited by@axtremus said in Puzzle time - How many bits:
May be I can cheat by pre-compiling a dictionary of all possible outcomes and then use the timing of signal transmission to index into that dictionary. In that case only one “pulse” needs to be sent at the right time, which you can then argue is merely “one bit.”
-
wrote on 12 Jul 2021, 01:48 last edited by
In engineering school I used to wonder why you couldn't, in theory, send an unlimited amount of information on a superconducting channel just by setting the voltage a very precise amount, say 3.141592674......
-
In engineering school I used to wonder why you couldn't, in theory, send an unlimited amount of information on a superconducting channel just by setting the voltage a very precise amount, say 3.141592674......
wrote on 12 Jul 2021, 09:18 last edited by@jon-nyc said in Puzzle time - How many bits:
In engineering school I used to wonder why you couldn't, in theory, send an unlimited amount of information on a superconducting channel just by setting the voltage a very precise amount, say 3.141592674......
Wouldn't the measurement influence the voltage? I guess that would be the main reason. Also, if you measure current, you'd at some point measure single electrons, which are discrete.
-
Does H know what K knows? Does H know what K wants to know? Can they have a common strategy they both know about?
wrote on 12 Jul 2021, 09:37 last edited by@klaus said in Puzzle time - How many bits:
Does H know what K knows?
In that case, one bit would be sufficient. If both know it must be team A or team B, then H can send 0 for team A or 1 for team B.
-
wrote on 12 Jul 2021, 09:40 last edited by
-
wrote on 12 Jul 2021, 09:53 last edited by jon-nyc 7 Dec 2021, 09:53
@klaus said in Puzzle time - How many bits:
@klaus said in Puzzle time - How many bits:
Does H know what K knows?
In that case, one bit would be sufficient. If both know it must be team A or team B, then H can send 0 for team A or 1 for team B.
The puzzle states that K knows the two teams but not the winner and H knows only the winner but not the other team. What they both know in advance are the 16 possible teams and whatever strategy they devise.
-
wrote on 12 Jul 2021, 10:27 last edited by Klaus 7 Dec 2021, 10:32
Hm. I think this one would work with two bits, but it would only work in 75% of all cases.
:::
K asks one of two boolean questions:
- Even? - is the winning team on an even position
- Lower? - is the winning team among the lower half of team numbers
Transmitting the question requires one bit, the answer requires one bit.
Of course, K is screwed if both teams have equal parity and are in the same half.
:::and here's an extension of the idea with three bits that presumably works in 100% of all cases.
:::
K sends a second bit which asks H to either shuffle the team order or not before answering the question.
The shuffling is such that equal parity and equal half cannot happen in both the unshuffled and shuffled order. I'm not quite sure whether that's even possible, but let's call this a solution just for fucks sake!
::: -
wrote on 12 Jul 2021, 10:36 last edited by
I dont think you could get the second answer to work.
-
@jon-nyc said in Puzzle time - How many bits:
In engineering school I used to wonder why you couldn't, in theory, send an unlimited amount of information on a superconducting channel just by setting the voltage a very precise amount, say 3.141592674......
Wouldn't the measurement influence the voltage? I guess that would be the main reason. Also, if you measure current, you'd at some point measure single electrons, which are discrete.
wrote on 12 Jul 2021, 12:22 last edited by@klaus said in Puzzle time - How many bits:
@jon-nyc said in Puzzle time - How many bits:
In engineering school I used to wonder why you couldn't, in theory, send an unlimited amount of information on a superconducting channel just by setting the voltage a very precise amount, say 3.141592674......
Wouldn't the measurement influence the voltage? I guess that would be the main reason. Also, if you measure current, you'd at some point measure single electrons, which are discrete.
Yes, you can get precision only down to the Planck scale and then you're limited by Heisenberg's uncertainty principle.
-
@klaus said in Puzzle time - How many bits:
@jon-nyc said in Puzzle time - How many bits:
In engineering school I used to wonder why you couldn't, in theory, send an unlimited amount of information on a superconducting channel just by setting the voltage a very precise amount, say 3.141592674......
Wouldn't the measurement influence the voltage? I guess that would be the main reason. Also, if you measure current, you'd at some point measure single electrons, which are discrete.
Yes, you can get precision only down to the Planck scale and then you're limited by Heisenberg's uncertainty principle.
wrote on 12 Jul 2021, 12:25 last edited by@axtremus said in Puzzle time - How many bits:
@klaus said in Puzzle time - How many bits:
@jon-nyc said in Puzzle time - How many bits:
In engineering school I used to wonder why you couldn't, in theory, send an unlimited amount of information on a superconducting channel just by setting the voltage a very precise amount, say 3.141592674......
Wouldn't the measurement influence the voltage? I guess that would be the main reason. Also, if you measure current, you'd at some point measure single electrons, which are discrete.
Yes, you can get precision only down to the Planck scale and then you're limited by Heisenberg's uncertainty principle.
My point was more immediate: Voltage is measured by sending a small current through a resistor. That current would necessarily cause a drop in the voltage.
-
wrote on 12 Jul 2021, 12:29 last edited by
Yes, I just go straight to the theoretical limit of known physics. :man-shrugging:
-
wrote on 12 Jul 2021, 14:36 last edited by
Here's a solution that gets it with three bits every time:
:::
K and H have prearranged a mapping of teams to 4 bit binary codes. K sends a two bit message to H indicating a bit where the two teams' digital representation differs. H responds with the value of that bit. That gives K the answer in 3, every time.
:::
-
wrote on 12 Jul 2021, 14:42 last edited by
An addendum to that that keeps max 3 but makes the expected value less than 2.5:
:::
Instead of always sending 2 bits to indicate the differing digit every time, send only one bit if it's bit 0 or 1. In other words, send:
0 -> 1st bit
1 -> 2nd bit
10 -> third bit
11 -> 4th bitI don't feel like calculating the exact expected value, but given that many pairs of digital words will differ in multiple places, you can always choose to send the more efficient representation when possible. Therefore it should be < 2.5.
:::
