Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 43 44 [45] 46  All

Author Topic: Maths thread.  (Read 132904 times)

0 Members and 1 Guest are viewing this topic.

MiX

  • Baron
  • ****
  • Offline Offline
  • Posts: 59
  • Shuffle iT Username: MiX
  • It's me.
  • Respect: +38
    • View Profile
Re: Maths thread.
« Reply #1100 on: January 26, 2020, 01:40:15 pm »
+1

For the new hat problem, I believe the correct answer for the first part is 50%, isn't it?
Yes, that's correct.

Surely it's more than 50%, right?

You can split each distribution into even-number of hats of each color and odd-number of hats, but since there's 100 hats the chances of there being an even split is higher than 50%, not by much but it still makes the game better than 50%
Logged
I donít think even MiX is townreading MiX.

bitwise

  • Bishop
  • ****
  • Offline Offline
  • Posts: 122
  • Respect: +134
    • View Profile
Re: Maths thread.
« Reply #1101 on: January 26, 2020, 04:23:26 pm »
+1

For the new hat problem, I believe the correct answer for the first part is 50%, isn't it?
Yes, that's correct.

Surely it's more than 50%, right?

You can split each distribution into even-number of hats of each color and odd-number of hats, but since there's 100 hats the chances of there being an even split is higher than 50%, not by much but it still makes the game better than 50%
I don't think so?
For any possible arrangement out of the 2^99 possibilities for the colors of the first 99 people, there's one way to give a hat to the 100th person so that there's an even number of red hats, and one way so that there's an odd number of red hats. So the chance of an total even number of red hats should be the same as odd.
Logged

hhelibebcnofnena

  • Minion
  • *****
  • Offline Offline
  • Posts: 522
  • he/him
  • Respect: +397
    • View Profile
Re: Maths thread.
« Reply #1102 on: January 26, 2020, 05:16:23 pm »
0

Thinking about it, I'm actually a bit confused about resolving the "trivial case".

Consider the layout is BB, WW, WW, BB, and everyone else BW. After the first two players pass, and the third player guesses, how can the second player deduce the difference between them being BW and the middle hidden cards WW or vice-versa?

This one I understand!
The trivial case is that the first WB player after a WW and BB guesses. So the third player would not make any guesses in your scenario.
In addition, you can say that After two WWs and two BBs have passed, any player can make a guess.
Logged
Hydrogen Helium Lithium Beryllium Boron Carbon Nitrogen Oxygen Fluorine Neon Sodium

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 160
  • Respect: +70
    • View Profile
Re: Maths thread.
« Reply #1103 on: January 27, 2020, 03:38:49 am »
0

Thinking about it, I'm actually a bit confused about resolving the "trivial case".

Consider the layout is BB, WW, WW, BB, and everyone else BW. After the first two players pass, and the third player guesses, how can the second player deduce the difference between them being BW and the middle hidden cards WW or vice-versa?

This one I understand!
The trivial case is that the first WB player after a WW and BB guesses. So the third player would not make any guesses in your scenario.
In addition, you can say that After two WWs and two BBs have passed, any player can make a guess.

You are right I did not consider a setup like BB, WW, WW, BB. Unfortunately, hhelibebcnofnena's solution will not work in general, because it will modify the special case when this setup happens at the end of the line. I believe the best solution is to have the second WW player still announce that they are WW at this point and have one player pass in the second round to indicate this special setup. I think I need to work through all cases in a 4 player game, because this case did not appear in a 3 player one (If you have two WW with three players, you always have BB as hidden cards and the other BB player will announce in his turn.).

Here is the complete list for 3 players
Notation
[XX] = hidden cards are XX
(XX) = player announce their cards are XX
PASS = pass -> pass -> pass

Trivial cases (hidden cards revealed in first round)
WW BB BB [WW]:
(WW) -> (BB) -> (BB)
BB WW WW [BB]:
(BB) -> (WW) -> (WW)
WW BB WW [BB]:
pass -> (BB) -> (WW) -> (WW)
BB WW BB [WW]:
pass -> (WW) -> (BB) -> (BB)
WW WW BB [BB]:
pass -> pass -> (BB) -> (WW) -> (WW)
BB BB WW [WW]:
pass -> pass -> (WW) -> (BB) -> (BB)
WW BB WB [WB]:
pass -> pass -> (WB) -> (WW) -> (BB)
BB WW WB [WB]:
pass -> pass -> (WB) -> (BB) -> (WW)

special case I (first player knows hidden cards after first round)
WB WW BB [WB]:
PASS -> (WB) -> (WW) -> (BB)
WB BB WW [WB]:
PASS -> (WB) -> (BB) -> (WW)
WB WW WB [BB]:
PASS -> (WB) -> pass -> (WB) -> (WW)
WB BB WB [WW]:
PASS -> (WB) -> pass -> pass -> (BB) -> (WB)

special case II (first player does not know hidden cards after first round, these are always 7, independent of the number of players)
WW WB WB [BB]:
PASS -> pass -> (WB) -> (WB) -> (WW)
WW WB BB [WB]:
PASS -> pass -> pass -> (BB) -> (WW) -> (WB)
BB WB WB [WW]:
PASS -> pass -> (WB) -> (WB) -> (BB)
BB WB WW [WB]:
PASS -> pass -> pass -> (WW) -> (BB) -> (WB)

WB WB WB [WB]:
PASS -> pass -> (WB) -> (WB) -> (WB)
WB WB WW [BB]:
PASS -> pass -> pass -> pass* -> (WB) -> (WB) -> (WW)
WB WB BB [WW]:
PASS -> pass -> pass -> pass* -> pass -> (WB) -> (BB) -> (WB)
*This passing is necessary because for 3 players, the n-th player appears before another WB can give additional information.
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 160
  • Respect: +70
    • View Profile
Re: Maths thread.
« Reply #1104 on: January 27, 2020, 10:59:11 am »
0

Below is the complete list for 4 players. It is actually even one turn faster than before (2n+2 turns), because while you may need 2x passing to distinguish between the crucial 7 cases, you can align them such that they never overlap.

Trivial cases
WW WB BB BB [WW]
WW BB WB BB [WW]
WW BB BB WB [WW]
(WW) ...
BB WB WW WW [BB]
BB WW WB WW [BB]
BB WW WW WB [BB]
(BB) ...

WB WW BB BB [WW]
BB WW WB BB [WW]
BB WW BB WB [WW]
pass -> (WW) ...
WB BB WW WW [BB]
WW BB WW WB [BB]
WW BB WB WW [BB]
pass -> (BB) ...

WW* BB WW BB [WB]
WB* BB WW BB [WW]
BB WW* WW BB [WB]
BB WB* WW BB [WW]
BB BB WW WB [WW]
pass -> pass -> (WW) ... *one passing is required to distinguish cases

WB* WW BB WW [BB]
BB* WW BB WW [WB]
WW WB* BB WW [BB]
WW BB* BB WW [WB]
WW WW BB WB [BB]
pass -> pass -> (BB) ... *one passing is required to distinguish cases

WW BB WB WB [WB]
BB WW WB WB [WB]
pass -> pass -> (WB) ...

WB BB BB WW [WW]
BB WB BB WW [WW]
BB BB WB* WW [WW]
BB BB WW* WW [WB]
pass -> pass -> pass -> (WW) ... *one passing is required to distinguish cases

WB WW WW BB [BB]
WW WB WW BB [BB]
WW WW WB* BB [BB]
WW WW BB* BB [WB]
pass -> pass -> pass -> (BB) ... *one passing is required to distinguish cases

WW WB BB WB [WB]
WB WW BB WB [WB]
WB BB WW WB [WB]
BB WB WW WB [WB]
pass -> pass -> pass -> (WB) ...

Special cases I
WB WW WB BB [WB]
WB BB WB WW [WB]
PASS -> (WB) ...

WB WB WW BB* [WB]
WB WB WW* WB* [BB]
WB WB BB* WB* [WW]
WB WB BB WW* [WB]
PASS -> (WB) ... *up to 2x passing is required to distinguish cases

WB WW* WB WB [BB]
WB BB* WB WB [WW]
PASS -> (WB) -> (pass) ...

Special cases II
WW* WB WB BB [WB]
WB* WB WB BB* [WW]
BB* WB WB WW [WB]
WB* WB WB WW* [BB]
WW* WB WB WB [BB]
WB* WB WB WB [WB]
BB* WB WB WB [WW]
PASS -> pass ... if [WW] player 2 passes, if [BB] player 3 passes
Logged

hhelibebcnofnena

  • Minion
  • *****
  • Offline Offline
  • Posts: 522
  • he/him
  • Respect: +397
    • View Profile
Re: Maths thread.
« Reply #1105 on: January 27, 2020, 03:47:46 pm »
0


WW WB WB [BB]:
PASS -> pass -> (WB) -> (WB) -> (WW)

BB WB WB [WW]:
PASS -> pass -> (WB) -> (WB) -> (BB)

WB WB WB [WB]:
PASS -> pass -> (WB) -> (WB) -> (WB)


How are these three cases different from the perspective of the first player? In other words, how is that final guess made?
Logged
Hydrogen Helium Lithium Beryllium Boron Carbon Nitrogen Oxygen Fluorine Neon Sodium

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 160
  • Respect: +70
    • View Profile
Re: Maths thread.
« Reply #1106 on: January 28, 2020, 03:30:25 am »
0


WW WB WB [BB]:
PASS -> pass -> (WB) -> (WB) -> (WW)

BB WB WB [WW]:
PASS -> pass -> (WB) -> (WB) -> (BB)

WB WB WB [WB]:
PASS -> pass -> (WB) -> (WB) -> (WB)


How are these three cases different from the perspective of the first player? In other words, how is that final guess made?

Here is a fixed scheme using the improvements of the 4 player solution to make it 1 turn shorter
WW WB BB [WB]:
WB WB WB [WB]:
BB WB WW [WB]:
PASS -> pass -> pass -> ...
WW WB WB [BB]:
BB WB WB [WW]:
PASS -> pass -> (WB) -> pass if [WW] -> ...
WB WB WW [BB]:
WB WB BB [WW]:
PASS -> pass -> (WB) -> pass -> pass if [WW] -> ...
Logged

hhelibebcnofnena

  • Minion
  • *****
  • Offline Offline
  • Posts: 522
  • he/him
  • Respect: +397
    • View Profile
Re: Maths thread.
« Reply #1107 on: January 28, 2020, 02:10:30 pm »
0

Okay, I think I finally understand what ghostofmars is saying. Thanks for laying out all the cases. Clearly, 5+ players runs along the same lines as 4 players.
Logged
Hydrogen Helium Lithium Beryllium Boron Carbon Nitrogen Oxygen Fluorine Neon Sodium

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Maths thread.
« Reply #1108 on: January 28, 2020, 03:45:12 pm »
+1

For hat-problem number 2 I don't know the probability, but the strategy that produces better than a 50% chance is:
If you see an even number of hats of each color, guess whichever color you see fewer of. If you see an odd number, don't guess.

And, for hat problem number 1:
Decide ahead of time to always guess odd or always even. Then everyone is guessing the same hat distribution.  This produces a 50% chance of victory, because there's an equal number of even and odd distributions.
« Last Edit: January 28, 2020, 04:01:12 pm by theorel »
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3441
  • Multiediting poster
  • Respect: +3778
    • View Profile
Re: Maths thread.
« Reply #1109 on: January 28, 2020, 07:19:50 pm »
0


And, for hat problem number 1:
Decide ahead of time to always guess odd or always even. Then everyone is guessing the same hat distribution.  This produces a 50% chance of victory, because there's an equal number of even and odd distributions.

I think this is the right idea, but there isnít the same number of odd and even distributions. So we would actually have to check what are the odds of having an odd number of white hats, total, and compare with the odds of having an even number. Then everybody agrees to guess the hat color that leads to a total number of white hats that is odd/even, depending on their previous result.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1040
  • Shuffle iT Username: heron
  • Respect: +1160
    • View Profile
Re: Maths thread.
« Reply #1110 on: January 28, 2020, 09:06:59 pm »
+1


And, for hat problem number 1:
Decide ahead of time to always guess odd or always even. Then everyone is guessing the same hat distribution.  This produces a 50% chance of victory, because there's an equal number of even and odd distributions.

I think this is the right idea, but there isnít the same number of odd and even distributions. So we would actually have to check what are the odds of having an odd number of white hats, total, and compare with the odds of having an even number. Then everybody agrees to guess the hat color that leads to a total number of white hats that is odd/even, depending on their previous result.

No, see the exchange earlier with MiX and bitwise. bitwise is correct.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3441
  • Multiediting poster
  • Respect: +3778
    • View Profile
Re: Maths thread.
« Reply #1111 on: January 29, 2020, 12:04:49 am »
0


And, for hat problem number 1:
Decide ahead of time to always guess odd or always even. Then everyone is guessing the same hat distribution.  This produces a 50% chance of victory, because there's an equal number of even and odd distributions.

I think this is the right idea, but there isnít the same number of odd and even distributions. So we would actually have to check what are the odds of having an odd number of white hats, total, and compare with the odds of having an even number. Then everybody agrees to guess the hat color that leads to a total number of white hats that is odd/even, depending on their previous result.

No, see the exchange earlier with MiX and bitwise. bitwise is correct.

Am dumb. Didnít want to do the summation, didnít realize there was another way to figure the answer to my question. Will have to remember this one.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 160
  • Respect: +70
    • View Profile
Re: Maths thread.
« Reply #1112 on: January 30, 2020, 07:24:48 am »
0

For hat-problem number 2 I don't know the probability, but the strategy that produces better than a 50% chance is:
If you see an even number of hats of each color, guess whichever color you see fewer of. If you see an odd number, don't guess.
This cannot be the best strategy. Consider e.g. the 5 player scenario: You have 2 cases of all same hats, which you get wrong; 10 cases where only a single player has a different hat, which you get right; and of the remaining 20 cases, which have a 3-2 distribution, you get only 50% correct. So overall you get 20/32 = 62.5% correct answers.
This is less than the 3 player solution (guess the opposite color if everyone else has the same hat), which is correct 75% of the time. So player 4 and 5 passing and otherwise using the 3 player strategy is stronger.
Logged

MiX

  • Baron
  • ****
  • Offline Offline
  • Posts: 59
  • Shuffle iT Username: MiX
  • It's me.
  • Respect: +38
    • View Profile
Re: Maths thread.
« Reply #1113 on: January 30, 2020, 07:31:45 am »
0

For hat-problem number 2 I don't know the probability, but the strategy that produces better than a 50% chance is:
If you see an even number of hats of each color, guess whichever color you see fewer of. If you see an odd number, don't guess.
This cannot be the best strategy. Consider e.g. the 5 player scenario: You have 2 cases of all same hats, which you get wrong; 10 cases where only a single player has a different hat, which you get right; and of the remaining 20 cases, which have a 3-2 distribution, you get only 50% correct. So overall you get 20/32 = 62.5% correct answers.
This is less than the 3 player solution (guess the opposite color if everyone else has the same hat), which is correct 75% of the time. So player 4 and 5 passing and otherwise using the 3 player strategy is stronger.

Doesn't it make sense that you'd win more with less hats? You can't just put that 3 player solution with 5 players, because there's more hats. Turns out "guess the opposite color if everyone else has the same hat" is the same as theorel's solution but for 3 players: in both cases, only the person who sees an even amount of hats guesses, and they guess the color they see less. So theorel's solution can be optimal.
Logged
I donít think even MiX is townreading MiX.

hhelibebcnofnena

  • Minion
  • *****
  • Offline Offline
  • Posts: 522
  • he/him
  • Respect: +397
    • View Profile
Re: Maths thread.
« Reply #1114 on: January 30, 2020, 09:13:04 am »
0

For hat-problem number 2 I don't know the probability, but the strategy that produces better than a 50% chance is:
If you see an even number of hats of each color, guess whichever color you see fewer of. If you see an odd number, don't guess.
This cannot be the best strategy. Consider e.g. the 5 player scenario: You have 2 cases of all same hats, which you get wrong; 10 cases where only a single player has a different hat, which you get right; and of the remaining 20 cases, which have a 3-2 distribution, you get only 50% correct. So overall you get 20/32 = 62.5% correct answers.
This is less than the 3 player solution (guess the opposite color if everyone else has the same hat), which is correct 75% of the time. So player 4 and 5 passing and otherwise using the 3 player strategy is stronger.

Doesn't it make sense that you'd win more with less hats? You can't just put that 3 player solution with 5 players, because there's more hats. Turns out "guess the opposite color if everyone else has the same hat" is the same as theorel's solution but for 3 players: in both cases, only the person who sees an even amount of hats guesses, and they guess the color they see less. So theorel's solution can be optimal.

I think the idea is that if three of the players ignore the other two, and if those two players never guess, the five player game essentially becomes a three player game. Therefore, the optimal strategy for any number of players must be at least as good as, if not better than, the optimal strategies for all smaller amounts of players.

But also, the logical extension of the three player solution is to use the same strategy for higher numbers of players. "If you see only same-color hats, guess the opposite color, otherwise, don't guess." As the number of players increases, the chances that someone will make a guess decrease exponentially, but the probability that said guess is correct only increases.
« Last Edit: January 30, 2020, 09:18:01 am by hhelibebcnofnena »
Logged
Hydrogen Helium Lithium Beryllium Boron Carbon Nitrogen Oxygen Fluorine Neon Sodium

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Maths thread.
« Reply #1115 on: January 30, 2020, 10:17:04 am »
0

For hat-problem number 2 I don't know the probability, but the strategy that produces better than a 50% chance is:
If you see an even number of hats of each color, guess whichever color you see fewer of. If you see an odd number, don't guess.
This cannot be the best strategy. Consider e.g. the 5 player scenario: You have 2 cases of all same hats, which you get wrong; 10 cases where only a single player has a different hat, which you get right; and of the remaining 20 cases, which have a 3-2 distribution, you get only 50% correct. So overall you get 20/32 = 62.5% correct answers.
This is less than the 3 player solution (guess the opposite color if everyone else has the same hat), which is correct 75% of the time. So player 4 and 5 passing and otherwise using the 3 player strategy is stronger.

Doesn't it make sense that you'd win more with less hats? You can't just put that 3 player solution with 5 players, because there's more hats. Turns out "guess the opposite color if everyone else has the same hat" is the same as theorel's solution but for 3 players: in both cases, only the person who sees an even amount of hats guesses, and they guess the color they see less. So theorel's solution can be optimal.

I think the idea is that if three of the players ignore the other two, and if those two players never guess, the five player game essentially becomes a three player game. Therefore, the optimal strategy for any number of players must be at least as good as, if not better than, the optimal strategies for all smaller amounts of players.

But also, the logical extension of the three player solution is to use the same strategy for higher numbers of players. "If you see only same-color hats, guess the opposite color, otherwise, don't guess." As the number of players increases, the chances that someone will make a guess decrease exponentially, but the probability that said guess is correct only increases.
So,
I did not consider giving players different strategies...I believe my strategy is correct if all players have to use the same strategy, and the number of hats is 3 mod 4.  There is a different optimal strategy if the number of hats is 1 mod 4.  In fact, with the original strategy the 3-2 case wouldn't get anywhere near a 50% win-rate...because you don't know what to guess.  If you choose randomly, then 3 people are choosing, so first they have to agree which is only a 1/8 chance, then they have to be right, which drops it to 1/16, of the remaining 20.  So, anyways, the total correct cases ends up around 35%
The correct all-same-strategy for 1 mod 4 hats is: if you see an odd number of hats of each color, guess the smaller quantity.  Unless you see all the same color, then guess THAT color.  That strategy hits 22/32 for 5-players.

I'll have to think if you can do better than just let 3 players play the game, maybe by using certain patterns to determine whether they play the game. 
I'm assuming that the abstention is intentional like they have to simultaneously vote White, Red, or Abstain.  If abstention is passive, then you can use timings to do better.
Otherwise, I'm pretty sure 75% is the best you can get.
« Last Edit: January 30, 2020, 10:39:07 am by theorel »
Logged

bitwise

  • Bishop
  • ****
  • Offline Offline
  • Posts: 122
  • Respect: +134
    • View Profile
Re: Maths thread.
« Reply #1116 on: January 30, 2020, 01:39:28 pm »
0

For hat-problem number 2 I don't know the probability, but the strategy that produces better than a 50% chance is:
If you see an even number of hats of each color, guess whichever color you see fewer of. If you see an odd number, don't guess.
This cannot be the best strategy. Consider e.g. the 5 player scenario: You have 2 cases of all same hats, which you get wrong; 10 cases where only a single player has a different hat, which you get right; and of the remaining 20 cases, which have a 3-2 distribution, you get only 50% correct. So overall you get 20/32 = 62.5% correct answers.
This is less than the 3 player solution (guess the opposite color if everyone else has the same hat), which is correct 75% of the time. So player 4 and 5 passing and otherwise using the 3 player strategy is stronger.
I calculated it with a program and found that for 127 people, that strategy would win about 53.5% of the time. hhelibebcnofnena is right in that having more players can only help (since you could just completely ignore some players if it doesn't). I will say as a gentle hint that you can do better than 75%. Happy to give more hints or talk things through but I'm trying to be careful about spoiling the problem.  :)
Logged

hhelibebcnofnena

  • Minion
  • *****
  • Offline Offline
  • Posts: 522
  • he/him
  • Respect: +397
    • View Profile
Re: Maths thread.
« Reply #1117 on: January 30, 2020, 03:05:57 pm »
0

For hat-problem number 2 I don't know the probability, but the strategy that produces better than a 50% chance is:
If you see an even number of hats of each color, guess whichever color you see fewer of. If you see an odd number, don't guess.
This cannot be the best strategy. Consider e.g. the 5 player scenario: You have 2 cases of all same hats, which you get wrong; 10 cases where only a single player has a different hat, which you get right; and of the remaining 20 cases, which have a 3-2 distribution, you get only 50% correct. So overall you get 20/32 = 62.5% correct answers.
This is less than the 3 player solution (guess the opposite color if everyone else has the same hat), which is correct 75% of the time. So player 4 and 5 passing and otherwise using the 3 player strategy is stronger.
I calculated it with a program and found that for 127 people, that strategy would win about 53.5% of the time. hhelibebcnofnena is right in that having more players can only help (since you could just completely ignore some players if it doesn't). I will say as a gentle hint that you can do better than 75%. Happy to give more hints or talk things through but I'm trying to be careful about spoiling the problem.  :)

I was just clarifying what I thought ghostofmars was saying.
Logged
Hydrogen Helium Lithium Beryllium Boron Carbon Nitrogen Oxygen Fluorine Neon Sodium

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 160
  • Respect: +70
    • View Profile
Re: Maths thread.
« Reply #1118 on: January 31, 2020, 04:14:06 pm »
0

I found a way to go beyond 75%.

Let's define the 3 player results as correct (C) with 75% chance and false (F) with 25% chance. Then you can construct a 9 player solution with three teams X, Y and Z, in the following way
-X announces their result if Y and Z would be both correct.
-Y announces their result if Z would be wrong.
-Z announces their result if Y would be wrong.
C C C = 42.2%
C C F = 14.1%
C F C = 14.1%
C F F =  4.7%
F C C = 14.1%
F C F =  4.7%
F F C =  4.7%
F F F =  1.6%
        -----
        79.7%

The bold letters are announced results and the strikethrough cases fail.

I'm not sure that is the best combination, but I extrapolated that idea by adding more players and get something like 86%.
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 160
  • Respect: +70
    • View Profile
Re: Maths thread.
« Reply #1119 on: February 03, 2020, 05:17:28 pm »
0

So I thought about more about the method and by optimizing the size of the teams, you will probably get to ~90% success rate. @bitwise: I wonder if what you are looking for is just this optimization or whether there is an even better technique we should find?
Logged

bitwise

  • Bishop
  • ****
  • Offline Offline
  • Posts: 122
  • Respect: +134
    • View Profile
Re: Maths thread.
« Reply #1120 on: February 03, 2020, 07:42:09 pm »
0

There is a provable best value that can be reached that is higher than 91%. But already getting to around 90% sounds pretty good! If it's not tedious to list out, it would be nice to see. The best solution might be hard to discover without a particular bit of domain knowledge, so it's neat to see improvements derived from first principles.

Another light hint for the best solution: The choice n=127 is important to have an easily provable best value. I'm not sure what the best answer is for 128 or 129, for example.
Logged

hhelibebcnofnena

  • Minion
  • *****
  • Offline Offline
  • Posts: 522
  • he/him
  • Respect: +397
    • View Profile
Re: Maths thread.
« Reply #1121 on: February 03, 2020, 09:03:37 pm »
0

Another light hint for the best solution: The choice n=127 is important to have an easily provable best value. I'm not sure what the best answer is for 128 or 129, for example.

Thoughts on the light hint:
Clearly one less than a power of two. Possibly also significant that it's a mersenne prime, but probably just anything one less than a power of two will do. I figured that was significant, because otherwise you would have just used 100 again. But I don't know where to go from there.
Logged
Hydrogen Helium Lithium Beryllium Boron Carbon Nitrogen Oxygen Fluorine Neon Sodium

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 160
  • Respect: +70
    • View Profile
Re: Maths thread.
« Reply #1122 on: February 04, 2020, 03:22:10 am »
0

I worked out the details, I get 88.8% chance of success with the strategy outlined above.

Say p is the probability team X is correct and k the analogous probability for team Y and Z. Then the resulting probability that the combination of team X, Y, and Z is correct if they follow the strategy is p k^2 + 2 k (1-k). This leads to the following optimal team sizes for a given total number of players.
  N    X   Y=Z    p        k    pk^2+2k(1-k)
  9    3    3   75.00%   75.00%   79.69%
 15    9    3   79.69%   75.00%   82.32%
 21   15    3   82.32%   75.00%   83.81%
 27   21    3   83.81%   75.00%   84.64%
 33   27    3   84.64%   75.00%   85.11%
 39   21    9   83.81%   79.69%   85.59%
 45   27    9   84.64%   79.69%   86.12%
 51   33    9   85.11%   79.69%   86.42%
 57   39    9   85.59%   79.69%   86.72%
 63   45    9   86.12%   79.69%   87.06%
 69   51    9   86.42%   79.69%   87.25%
 75   45   15   86.12%   82.32%   87.47%
 81   51   15   86.42%   82.32%   87.67%
 87   57   15   86.72%   82.32%   87.88%
 93   63   15   87.06%   82.32%   88.11%
 99   69   15   87.25%   82.32%   88.23%
105   75   15   87.47%   82.32%   88.38%
111   81   15   87.67%   82.32%   88.52%
117   87   15   87.88%   82.32%   88.66%
123   93   15   88.11%   82.32%   88.82%
135   93   21   88.11%   83.81%   89.02%
141   99   21   88.23%   83.81%   89.11%
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1040
  • Shuffle iT Username: heron
  • Respect: +1160
    • View Profile
Re: Maths thread.
« Reply #1123 on: February 04, 2020, 02:38:44 pm »
0

I found an optimal strategy:


Index the players 1-127.
Each player computes the XOR of the indices of the players with red hats.
If it is 0, they guess that they have a red hat.
If it is their own index, they guess that they have a black hat.
Otherwise, they abstain.

Thoughts on how to come up with this strategy:
Since each guess is correct with 50% probability, in order to maximize the chance of winning we need to make it so that when someone guesses wrong, everyone else does too, and when someone guess right they are the only one to guess.
The easiest example of this sort of behavior is a situation where a player guesses that they have a red hat if all other players have a black hat.
Then everyone guesses wrong if there are all black hats, and exactly one person guesses correctly if there is exactly one red hat.

Basically, we need to tile the space with clusters consisting of a center state (where everyone guesses wrong) and all the adjacent states.
Due to the way that switching a hat color twice doesn't change the state, it seemed natural to use some sort of XOR condition.
So, I picked the states where everyone guesses wrong to be the states where the XOR of the indices of red hats to be 0.
You could pick a different number besides 0 if you want.


That said, here is a similar problem from the most recent putnam:

Let Z^n be the integer lattice in R^n. Two points in Z^n are called neighbors if they differ by exactly 1 in one coordinate and are equal in all other coordinates.
For which integers n ≥ 1 does there exist a subset S of Z^n satisfying the following two conditions?
(1) If p is in S, then none of the neighbors of p is in S.
(2) If p is not in S, then exactly one of the neighbors of p is in S
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2695
    • View Profile
Re: Maths thread.
« Reply #1124 on: April 10, 2020, 09:30:18 pm »
0

I've been trying to answer this (more philosophical) question, and I'm having a hard time answering it.  What is a number?  Mathematicians have come up with a bajillion different useful objects, and have called some of them "numbers" and others not.  Why is it that they have named some numbers, but not others?  When you look up definitions they normally talk about counting or measuring, but at most that only applies to the real numbers.  Why do we call complex numbers numbers?  Quaternions?  Most people describe them as an extension of the complex numbers and consider them numbers.  But they're not used to measure or count, and are mainly used to represent rotations.  In this case they are isomorphic to 2x2 matrices in some sense, which we don't consider numbers.  Normally we say that isomorphism means things are the same mathematically, but there are plenty of things isomorphic to, say, the integers that we would not call numbers.

Sorry for rambling on, but the short of it is this: what distinguishes the things that mathematicians call numbers from those that they don't call numbers?
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm
Pages: 1 ... 43 44 [45] 46  All
 

Page created in 0.099 seconds with 20 queries.