Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 10 11 [12] 13 14 ... 42  All

Author Topic: Maths thread.  (Read 104014 times)

0 Members and 1 Guest are viewing this topic.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Maths thread.
« Reply #275 on: February 17, 2015, 09:39:21 am »
0

Correct! I assume you tested the first few n by hand to find the pattern?

It's also neat to observe that as n gets large, your winrate approaches 1. At first this problem did not have a limit on how many ties there can be but then the optimal strategy is for both players to always play rock and you always win... so I added n.
Logged

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1263
    • View Profile
Re: Maths thread.
« Reply #276 on: February 17, 2015, 12:57:42 pm »
0

Cool Problem. I got the same solution as scott. You can solve the general case by drawing a payoff matrix and then using the argument that an optimal mixed strategy must be composed of pure strategies that perform equally well against whatever the opponent chooses, then simplify to get a recursive expression for the payout. At which point, I had mathematica calculate the first 10 expected values, noticed the pattern, and proved by induction.
Logged
"All advice is awful"
 —Count Grishnakh

scott_pilgrim

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1032
  • Respect: +2001
    • View Profile
Re: Maths thread.
« Reply #277 on: February 17, 2015, 02:53:28 pm »
+1

Okay, here are some cool hat problems:

1. There are 100 perfectly rational people on an island, each with either a red or a green party hat glued to his head.  Each person can see everyone else's party hat, but not his own.  No one can communicate with each other.  Everyone is informed that everyone is wearing either a red or green hat, and that at least one person is wearing a red hat.  Each day at noon, a ship comes around, and the captain will let anyone leave the island if they can correctly guess their hat color; but if they guess incorrectly they die.  These guesses are publicly known by everyone after the ship leaves.  If there are x people wearing red hats, who will leave the island and when, in terms of x?

2. There are a finite number of people.  Before the game starts, they may discuss a plan with each other, but after the game begins they cannot communicate (except through their guesses).  After the game begins, they stand in a single file line and have a red or green party hat glued to their head, so that each person can see all and only those hats in front of him.  Then the executioner asks each person, starting from the back of the line, what color his hat is, and kills him if he is wrong.  Everyone else in the line hears the guess, but not whether it was correct.  What plan can they come up with to minimize the number of people that die in the worst case scenario?  (Note that not everyone is necessarily acting in the interest of his own survival, just in the interest of minimizing the number of deaths in the worst case scenario.)

3. The situation is the same as in #2, except that there are now a countably infinite number of people, and they cannot hear each other's guesses.  Is it possible for them to come up with a plan that guarantees that only a finite number of people die?
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3401
  • Multiediting poster
  • Respect: +3741
    • View Profile
Re: Maths thread.
« Reply #278 on: February 17, 2015, 03:00:42 pm »
0

I'll let other people think about these problems, I remember seeing them in the Logic problems thread, among many others. Shame that thread died, it was great fun.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

sudgy

  • Cartographer
  • *****
  • Online Online
  • Posts: 3386
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2644
    • View Profile
Re: Maths thread.
« Reply #279 on: February 17, 2015, 03:08:45 pm »
0

1. There are 100 perfectly rational people on an island, each with either a red or a green party hat glued to his head.  Each person can see everyone else's party hat, but not his own.  No one can communicate with each other.  Everyone is informed that everyone is wearing either a red or green hat, and that at least one person is wearing a red hat.  Each day at noon, a ship comes around, and the captain will let anyone leave the island if they can correctly guess their hat color; but if they guess incorrectly they die.  These guesses are publicly known by everyone after the ship leaves.  If there are x people wearing red hats, who will leave the island and when, in terms of x?

I'm guessing that the rational people know the others are rational?  Them not knowing could change quite a bit...
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

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Maths thread.
« Reply #280 on: February 17, 2015, 03:13:34 pm »
+1

I remember these too. I do like the first better with party hats than with eyes though!

1. There are 100 perfectly rational people on an island, each with either a red or a green party hat glued to his head.  Each person can see everyone else's party hat, but not his own.  No one can communicate with each other.  Everyone is informed that everyone is wearing either a red or green hat, and that at least one person is wearing a red hat.  Each day at noon, a ship comes around, and the captain will let anyone leave the island if they can correctly guess their hat color; but if they guess incorrectly they die.  These guesses are publicly known by everyone after the ship leaves.  If there are x people wearing red hats, who will leave the island and when, in terms of x?

I'm guessing that the rational people know the others are rational?  Them not knowing could change quite a bit...
Yep. And they know that the rational people know that the other people are not only rational but also know that the rational people I mentioned first know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they know that they are rational. Or something like that.
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2315
    • View Profile
Re: Maths thread.
« Reply #281 on: February 17, 2015, 04:27:02 pm »
0


I still find this vaguely mysterious.
Logged

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1263
    • View Profile
Re: Maths thread.
« Reply #282 on: February 17, 2015, 07:24:33 pm »
+2

Okay, here are some cool hat problems:

1. There are 100 perfectly rational people on an island, each with either a red or a green party hat glued to his head.  Each person can see everyone else's party hat, but not his own.  No one can communicate with each other.  Everyone is informed that everyone is wearing either a red or green hat, and that at least one person is wearing a red hat.  Each day at noon, a ship comes around, and the captain will let anyone leave the island if they can correctly guess their hat color; but if they guess incorrectly they die.  These guesses are publicly known by everyone after the ship leaves.  If there are x people wearing red hats, who will leave the island and when, in terms of x?


Ok, so if there's only one person with a red hat, they know day 1 and guess. Then everyone else knows that they all have a green hat and guess and leave.

If there are two people, then on the first day no one guesses, but on the second day both people with red hats realize that the other guy didn't guess and so they must also have a red hat. They guess and then everyone knows day 3, guess and leave.

This pattern continues. It takes x+1 days to get everyone off the island.


2. There are a finite number of people.  Before the game starts, they may discuss a plan with each other, but after the game begins they cannot communicate (except through their guesses).  After the game begins, they stand in a single file line and have a red or green party hat glued to their head, so that each person can see all and only those hats in front of him.  Then the executioner asks each person, starting from the back of the line, what color his hat is, and kills him if he is wrong.  Everyone else in the line hears the guess, but not whether it was correct.  What plan can they come up with to minimize the number of people that die in the worst case scenario?  (Note that not everyone is necessarily acting in the interest of his own survival, just in the interest of minimizing the number of deaths in the worst case scenario.)


I can guarantee at most one death.

First person says green if there are an odd number of greens in front of him, red if there are an even. This guy takes one for the team, and may die. Person 2 knows the parity of the green hats in front of the person behind them. If it's the same as the parity in front of them, then they know their hat is red; if not, it's green. Etc.


3. The situation is the same as in #2, except that there are now a countably infinite number of people, and they cannot hear each other's guesses.  Is it possible for them to come up with a plan that guarantees that only a finite number of people die?

Do they hear whether the other people die?
Logged
"All advice is awful"
 —Count Grishnakh

scott_pilgrim

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1032
  • Respect: +2001
    • View Profile
Re: Maths thread.
« Reply #283 on: February 18, 2015, 01:31:04 am »
0

3. The situation is the same as in #2, except that there are now a countably infinite number of people, and they cannot hear each other's guesses.  Is it possible for them to come up with a plan that guarantees that only a finite number of people die?

Do they hear whether the other people die?

I don't think so, but the original problem statement I'm looking at doesn't specify...
Logged

Ratsia

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 168
  • Respect: +112
    • View Profile
Re: Maths thread.
« Reply #284 on: February 18, 2015, 01:40:56 am »
+1

I'm guessing that the rational people know the others are rational?  Them not knowing could change quite a bit...
Besides rationality, I guess you need to assume a specific utility function for them. In particular, they have to value life over death so much that needing to spend several, potentially close to a hundred, days on an island where everyone else is perfectly rational does not warrant an early guess with some non-zero probability of dying. Perhaps not being able to talk with them helps to endure it.
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2138
  • Respect: +2694
    • View Profile
Re: Maths thread.
« Reply #285 on: February 18, 2015, 01:53:37 am »
+1

3. The situation is the same as in #2, except that there are now a countably infinite number of people, and they cannot hear each other's guesses.  Is it possible for them to come up with a plan that guarantees that only a finite number of people die?

Do they hear whether the other people die?

You can solve it assuming no one hears any other guesses, and assuming a sufficient mathematical belief system.

Edit: I looked up the solution for the case where they are allowed to hear each other's guesses. In this scenario, you can limit the deaths to at most          one           .
« Last Edit: February 18, 2015, 01:57:34 am by Titandrake »
Logged
I have a blog! It's called Sorta Insightful. Check it out?

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1488
    • View Profile
Re: Maths thread.
« Reply #286 on: February 18, 2015, 02:34:02 am »
+2


3. The situation is the same as in #2, except that there are now a countably infinite number of people, and they cannot hear each other's guesses.  Is it possible for them to come up with a plan that guarantees that only a finite number of people die?
the answer is somewhere in this forum
Logged

SwitchedFromStarcraft

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1088
  • Respect: +853
    • View Profile
Re: Maths thread.
« Reply #287 on: February 18, 2015, 10:21:51 am »
0


3. The situation is the same as in #2, except that there are now a countably infinite number of people, and they cannot hear each other's guesses.  Is it possible for them to come up with a plan that guarantees that only a finite number of people die?
the answer is somewhere in this forum
Incorrect.  Given a "countably infinite" starting population, the answer is actually                                      moat                                                                                     .
Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7839
    • View Profile
Re: Maths thread.
« Reply #288 on: February 18, 2015, 10:24:23 am »
0

Incorrect.  Given a countably infinite number of people, and if only finitely many of them die, then clearly the remaining countably infinite people will sink the ship.
Logged

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2737
  • Shuffle iT Username: Watno
  • Respect: +2967
    • View Profile
Re: Maths thread.
« Reply #289 on: February 18, 2015, 10:24:37 am »
0

It's also                         yes                         
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3401
  • Multiediting poster
  • Respect: +3741
    • View Profile
Re: Maths thread.
« Reply #290 on: February 18, 2015, 10:37:29 am »
+2

Gentlemen, you can't meme in here, this is the Maths room!
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7839
    • View Profile
Re: Maths thread.
« Reply #291 on: February 18, 2015, 10:38:49 am »
+6

Gentlemen, you can't meme in here, this is the Maths room!

Can we (me)^n for other values of n?
Logged

SwitchedFromStarcraft

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1088
  • Respect: +853
    • View Profile
Re: Maths thread.
« Reply #292 on: February 18, 2015, 01:08:57 pm »
0

Gentlemen, you can't meme (m)^e(n)^e in here, this is the Maths room!
FTFY
Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1027
  • Shuffle iT Username: heron
  • Respect: +1152
    • View Profile
Re: Maths thread.
« Reply #293 on: February 18, 2015, 06:36:39 pm »
0

Wait you need the axiom of choice for #3 right?
Logged

SwitchedFromStarcraft

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1088
  • Respect: +853
    • View Profile
Re: Maths thread.
« Reply #294 on: February 18, 2015, 08:12:15 pm »
+1

Wait you need the axiom of choice for #3 right?
For some reason the phrase hit me oddly, and conjured card names, or sci-fi movie artifacts, or something.

Axiom of choice
Chalice of harmony
Wand of opprobrium
Scepter of apportionment
Construct of delight
Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2737
  • Shuffle iT Username: Watno
  • Respect: +2967
    • View Profile
Re: Maths thread.
« Reply #295 on: February 18, 2015, 08:37:37 pm »
0

Wait you need the axiom of choice for #3 right?
You don't. You need countable choice though, I think.
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1027
  • Shuffle iT Username: heron
  • Respect: +1152
    • View Profile
Re: Maths thread.
« Reply #296 on: February 18, 2015, 08:56:08 pm »
+1

Okay well for #3 then

Call two colorings of hats similar if they different in finitely many hats. Similarity is an equivalence relation, so the sets of similar colorings partition the set of all colorings. The people choose a coloring from each set of similar colorings (this is the part where the axiom of choice is used). So, everyone looks at all the hats ahead of them and sees which set of similar colorings they belong to (which is possible because they can see all the hats somehow), and then they assume that the actual coloring of hats is the one that they chose earlier. Since these colorings are similar, only finitely many people will die.

This sort of thing is why I don't like the axiom of choice; it leads to all sorts of nonsense.
Edit: So apparently choice and countable choice are different, I didn't know that. They both seem kind of not true sounding to me though.
« Last Edit: February 18, 2015, 08:57:46 pm by heron »
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1488
    • View Profile
Re: Maths thread.
« Reply #297 on: February 19, 2015, 02:18:24 am »
0

Okay well for #3 then


This sort of thing is why I don't like the axiom of choice; it leads to all sorts of nonsense.
Edit: So apparently choice and countable choice are different, I didn't know that. They both seem kind of not true sounding to me though.

Maybe the cause of the nonsene is also that the solution disregards relativity theory.

:e the diference between original an and countable is that the original states choice for all set of sets, what we clearly don't need here in this extreme form, as we only have countably many sets to chose from
:e2 wait, thats not true, there should be uncountble many colorings, and the shouldnt make it much better...
« Last Edit: February 19, 2015, 02:28:37 am by DStu »
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2315
    • View Profile
Re: Maths thread.
« Reply #298 on: February 19, 2015, 02:30:28 am »
0

Are you sure this is countable choice?  Each equivalence class is countable, but there are uncountably many equivalence classes.
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1488
    • View Profile
Re: Maths thread.
« Reply #299 on: February 19, 2015, 02:57:03 am »
0

Also, how can you know in which class you are if you can just see the hats in front of you, but not the infinitely many behind? Or can you?
Logged
Pages: 1 ... 10 11 [12] 13 14 ... 42  All
 

Page created in 0.102 seconds with 21 queries.