Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 5 6 [7] 8 9 ... 11  All

Author Topic: Logic problems  (Read 72118 times)

0 Members and 1 Guest are viewing this topic.

Grujah

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2237
  • Respect: +1177
    • View Profile
Re: Logic problems
« Reply #150 on: January 15, 2013, 04:51:00 am »
0

I also missed the "nobody guesses incorrectly" line, which makes guessing randomly a pretty bad idea. Also have to modify the strategy to #1 or #2 not guessing tells #3 something.

I missed that line too :s
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Logic problems
« Reply #151 on: January 15, 2013, 05:07:01 am »
0

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?
I get to 11/16

Oh, there are just 4 people. 11/16 is 5 people and 5 hats...  Ok, let's rethink this... In this case just assuming the same principle works here (have no doubt that it will)

... gets me to  ... hmm, it's 1/2 here, but that of course can be achieved trivially.  Have to modify...

Edit:

OK, can reproduce 11/16 for 4 people
« Last Edit: January 15, 2013, 05:17:28 am by DStu »
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Logic problems
« Reply #152 on: January 15, 2013, 07:26:37 am »
0

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.
If the people know, if someone else guessed, I suggest the following strategy
Player 1: If nobody says anything for 30 seconds, I say 'black'.
Player 2: If Player 1 has black hat, say nothing, otherwise wait for 20 seconds and then say 'black', if nobody else did.
Player 3: If Player 1 or 2 have black hat, say nothing, otherwise wait for 10 seconds and then say 'black', if Player 4 didn't.
Player 4: Say 'black' if none of Player 1-3 has a black hat.
This would work for all but the 'all white' case... = 15/16
Logged

mith

  • Jester
  • *****
  • Offline Offline
  • Posts: 771
  • Shuffle iT Username: mith
  • Respect: +778
    • View Profile
    • MafiaScum.net
Re: Logic problems
« Reply #153 on: January 15, 2013, 11:12:56 am »
0

Repeating since it's buried at the bottom of page 5:

"For both puzzles: They are given the opportunity to see each others hats (but not their own), and then are taken away to isolated cells. No communication once the hats are given out."
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Logic problems
« Reply #154 on: January 16, 2013, 03:09:27 am »
0

Now, I also get 11/16...
Logged

mith

  • Jester
  • *****
  • Offline Offline
  • Posts: 771
  • Shuffle iT Username: mith
  • Respect: +778
    • View Profile
    • MafiaScum.net
Re: Logic problems
« Reply #155 on: January 16, 2013, 12:45:02 pm »
0

You can do better.
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Logic problems
« Reply #156 on: January 16, 2013, 12:53:27 pm »
0

You can do better.
Than I say 3/4. I think I've proven an upper bound of 4/5, and 12/16 is the only 1/16 left which is smaller than 4/5, each deterministic strategy has an sucessrate which is an mutiple of 1/16, an I doubt that a random strategy will help. qed.

Can  now please someone say something concerning these infinitely many hats?
Logged

mith

  • Jester
  • *****
  • Offline Offline
  • Posts: 771
  • Shuffle iT Username: mith
  • Respect: +778
    • View Profile
    • MafiaScum.net
Re: Logic problems
« Reply #157 on: January 16, 2013, 01:05:16 pm »
0

Your upper bound suggests you've figured out the basic idea, so a hint for getting to 3/4: What would the answer be if there were only three men?
Logged

mith

  • Jester
  • *****
  • Offline Offline
  • Posts: 771
  • Shuffle iT Username: mith
  • Respect: +778
    • View Profile
    • MafiaScum.net
Re: Logic problems
« Reply #158 on: January 16, 2013, 01:07:31 pm »
+1

And a hint on the infinite hats.

Re: DStu's reply 100 - If you are choosing from a countably infinite number of finite sets, the Axiom of Choice is free. When would it not be free?
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Logic problems
« Reply #159 on: January 16, 2013, 01:17:23 pm »
0

Your upper bound suggests you've figured out the basic idea, so a hint for getting to 3/4: What would the answer be if there were only three men?
I thought getting to 11/16 is the basic idea, but I don't find the last case...
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Logic problems
« Reply #160 on: January 16, 2013, 01:25:46 pm »
0

And a hint on the infinite hats.

Re: DStu's reply 100 - If you are choosing from a countably infinite number of finite sets, the Axiom of Choice is free. When would it not be free?

I'm not the expert in set theory, but afaik it's still free if you are choosing from any number of finite sets, at least if these finite sets are ordered, which is the case here. Say white<black

So the other way round take countable number of  uncountabe  large sets

But after all, I still don't see how the AC should give me a strategy to guess correctly, as it's usually pretty non-constructive.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Logic problems
« Reply #161 on: January 16, 2013, 01:40:33 pm »
0

If any of you lack the capacity to solve problems involving infinitely countable hats (I know I do), here's one of my favourite puzzles (this one is by Raymond Smullyan; I had to retranslate the version I have, so sorry if the English is wonky):

In 1918, the day the First World War armistice was signed, three married couples celebrated the occasion dining together. Each husband is the brother of one wife, and each wife is the sister of one husband; that is, there are three brother-sister pairs in the group. We know the following:

-Helen is exactly twenty-six weeks older than her husband, who was born in august.
-The sister of Mr. White, who is married to the brother-in-law of Helen’s brother, got married to him on her birthday, which is in January.
-Marguerite White isn’t as tall as William Black.
-Arthur’s sister is taller than Beatrice.
-John is fifty years old.

What is Mrs. Brown first name?
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

Ozle

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3625
  • Sorry, this text is personal.
  • Respect: +3360
    • View Profile
Re: Logic problems
« Reply #162 on: January 16, 2013, 01:46:09 pm »
+1

Helen
Logged
Try the Ozle Google Map Challenge!
http://forum.dominionstrategy.com/index.php?topic=7466.0

Sullying players Enjoyment of Innovation since 2013 Apparently!

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Logic problems
« Reply #163 on: January 16, 2013, 01:50:00 pm »
0

Helen

I'll wait for the spoilered explanation since, you know, there's a 50% chance to guess randomly :)
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

Ozle

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3625
  • Sorry, this text is personal.
  • Respect: +3360
    • View Profile
Re: Logic problems
« Reply #164 on: January 16, 2013, 02:07:57 pm »
+2

Darn, foiled!

I'd have got away with it if it wasn't for those pesky kids!
Logged
Try the Ozle Google Map Challenge!
http://forum.dominionstrategy.com/index.php?topic=7466.0

Sullying players Enjoyment of Innovation since 2013 Apparently!

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2320
    • View Profile
Re: Logic problems
« Reply #165 on: January 16, 2013, 02:59:02 pm »
0

Hats:

The Axiom of Choice hint isn't so helpful - the Axiom of Choice is true!  People don't flag up when they use any of the ZF axioms, and it's quite possible to happily do things that require Choice before you know anything about it (countable unions of countable sets shocked me the first time it was pointed out). 

The next set of tags is a different hint.  It's not a hint I've ever given before, because I've never tried to help anyone solve this (aside: if you're a mathematician in training, you're strongly encouraged not to read the hint).


Suppose g is a good guess for hat pattern H. When else is g a good guess?
Logged

mith

  • Jester
  • *****
  • Offline Offline
  • Posts: 771
  • Shuffle iT Username: mith
  • Respect: +778
    • View Profile
    • MafiaScum.net
Re: Logic problems
« Reply #166 on: January 16, 2013, 03:06:45 pm »
+1

"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?"

The point of the hint was simply to point out that the choosing here will not be "Pick a color for each person", where the AoC is true without assumption. The solution requires a different application of AoC, and is not valid in a set theory where the AoC is not true.
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Logic problems
« Reply #167 on: January 17, 2013, 04:14:02 am »
+1

Now I have 12/16
The general idea is that everyone tries to make a guess, if it could be that someone guessed wrong, which will be correct, if the other one did not submit a tip and false if the other one guessed wrongly. Hence, the negative results, collapse on particular cases and the positive ones survive.

The following set of rules produces the 12/16 result listed below:
1) If A sees 3x the same color, he guesses "black"
2a) If A has a white hat, B, C, and D know that A can only be wrong if they have all the same color, so if they see the same color twice they guess the opposite color.
2b) If A has a black hat and B sees that C and D have black hats, B guesses 'black' otherwise he doesn't guess at all.
3a) If A and B have black hats, C and D guess "black", if they see that the other one has a white hat.
3b) If A has a black hat and B a white one, C and D guess "white", if they see that the other one has a black hat.

Hat Color |  Guess  | Correct?
 A B C D  | A B C D |
 b b b b  | b b     | Yes
 b b b w  |     b   | Yes
 b b w b  |       b | Yes
 b b w w  |     b b | No
 b w b b  | b b w w | No
 b w b w  |       w | Yes
 b w w b  |     w   | Yes
 b w w w  | b       | Yes
 w b b b  | b w w w | No
 w b b w  |       w | Yes
 w b w b  |     w   | Yes
 w b w w  |   b     | Yes
 w w b b  |   w     | Yes
 w w b w  |     b   | Yes
 w w w b  |       b | Yes
 w w w w  | w b b b | No
Logged

mith

  • Jester
  • *****
  • Offline Offline
  • Posts: 771
  • Shuffle iT Username: mith
  • Respect: +778
    • View Profile
    • MafiaScum.net
Re: Logic problems
« Reply #168 on: January 17, 2013, 12:07:37 pm »
+1

Yep, that will work. You approached this a little differently than I did, but it's the same idea:

The trick here is that there is necessarily an equal number of right and wrong answers, but you can set things so that the wrong answers are all clumped together under the same few hat arrangements while the right answers are spread out. The general idea for the solution then is to select some number of "bad" arrangements, where all the other ("good") arrangements differ by 1 hat from at least one of the bad sets, with the rule "If you see that the other three have hats corresponding to one of the bad arrangements, guess the opposite color from what your hat is in that arrangement", which leads to everyone guessing wrong on those, while at least one guesses right on all the others.

We have a general upper bound of n/(n+1) - 4/5 in this case - because the total number of right and wrong answers must be the same. For example, we can't survive 13 of the cases here, because we would need 13 right answers and 13 wrong answers, but with 3 bad cases left there are only 3*4 wrong answers available.

The simplest way to do it with 4 - and this is where the hint came in - is to ignore one of the people entirely and just consider the other three, because with 3 you can also achieve a 3/4 success rate. (Apparently, in the more general problem you can reach the upper bound of n/(n+1) if n = 2^k-1 for some k, by using the corresponding Hamming code.)

Rule: Ignore the fourth person. Among the remaining three, if anyone sees two like hats, guess the opposite.

(This is basically ghostofmars' rule 2a, but applied to both halves of the problem by ignoring A entirely.)
« Last Edit: January 17, 2013, 12:13:02 pm by mith »
Logged

Jack Rudd

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1323
  • Shuffle iT Username: Jack Rudd
  • Respect: +1379
    • View Profile
Re: Logic problems
« Reply #169 on: January 17, 2013, 01:03:38 pm »
+1

In 1918, the day the First World War armistice was signed, three married couples celebrated the occasion dining together. Each husband is the brother of one wife, and each wife is the sister of one husband; that is, there are three brother-sister pairs in the group. We know the following:

-Helen is exactly twenty-six weeks older than her husband, who was born in august.
-The sister of Mr. White, who is married to the brother-in-law of Helen’s brother, got married to him on her birthday, which is in January.
-Marguerite White isn’t as tall as William Black.
-Arthur’s sister is taller than Beatrice.
-John is fifty years old.

What is Mrs. Brown first name?

I've got some of the way, but I can't seem to get further off the top of my head.


OK, assuming that Arthur, John and William are the men, and Beatrice, Helen and Marguerite the women, what do we have?

Suppose the sister of Mr White is Beatrice. Then Mr White cannot be Arthur (because Arthur's sister isn't Beatrice), nor can he be William (because William is William Black), so he is John. Thus the men are Arthur Brown, William Black and John White. Also, Beatrice is not married to Helen's brother (because Mr White's sister is married to the brother-in-law of Helen's brother), so must be married to Marguerite's brother. Thus Marguerite is married to Helen's brother and Helen to Beatrice's brother - but this would make Helen Mrs White, when we already know Marguerite is Mrs White.

Therefore the sister of Mr White is Helen. (This fits in with her date of birth - 26 weeks before a date in August is nearly always a date in January.) Now who is Mr White? Suppose he's John. In that case, John is the brother of Helen, Arthur the brother of Marguerite and William the brother of Beatrice. This would in turn imply that John is married to Marguerite, Arthur to Beatrice and William to Helen. In which case the women are Marguerite White, Helen Black and therefore Beatrice Brown.

Alternatively, Mr White could be Arthur. In which case our men are Arthur White, John Brown and William Black. Arthur married Marguerite and his sister is Helen, so the man who married Beatrice has Marguerite as a sister and the man who married Helen has Beatrice as a sister.
Logged
Centuries later, archaeologists discover the remains of your ancient civilization.

Evidence of thriving towns, Pottery, roads, and a centralized government amaze the startled scientists.

Finally, they come upon a stone tablet, which contains but one mysterious phrase!

'ISOTROPIC WILL RETURN!'

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Logic problems
« Reply #170 on: January 17, 2013, 04:11:18 pm »
0

You are globally right, yes. The end of the puzzle is somewhat more subtle though.
« Last Edit: January 18, 2013, 01:32:50 am by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

Axxle

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1664
  • Most Valuable Serial Killer
  • Respect: +1965
    • View Profile
Re: Logic problems
« Reply #171 on: January 17, 2013, 06:24:52 pm »
0

What plan do the maidens come up with that night?

Probably not optimal:

You could elect some master maiden.  Use switch 1 as dummyswitch which does not carry any information.  If usual maiden enters the room and switch 2 is "down", and she hasn't switched it already, switch it
if switch 2 is "up", or this maiden has already switched switch 2, switch switch 1.
if master maiden enters room and switch 2 is "up", switch it to "down"
otherwise use switch 1

Now if the master maiden has turned the switch2 down for 50 times, all other maiden have entered the room.


Estimated maiden in rooms ~N^2 log N I think.


Almost. Nicely done; except... You know know if switch 2 started up or down. So if it started up, then Master would count 1 even when there hasn't been a maiden yet. So you could add 1 extra to that (which your count of 50 does), but then if switch 2 happens to start down instad, you would never reach 50, it would stay at 49 forever.


I did add 1, as there are only 49 other maidens, the mastermaiden obviously has been in this room, as she is at the moment and has been there 49 times before...

Edit: OK, I did add 1, but I didn't finish reading you're post...
Edit2: On the other hand, we already waited N^2log N, and it only take N log N for everyone to enter the room, so probably we're fine with 49...

Granted, once you reach 49 you're pretty likely to be safe... but there is a way to be sure.It's still your basic answer; just with a minor change.
Have each regular maiden signal twice instead of just once. Master maiden counts to 99 instead of 49.

Right.
I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.
Logged
We might be from all over the world, but "we all talk this one language  : +1 card + 1 action +1 buy , gain , discard, trash... " - RTT

eHalcyon

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 8689
  • Respect: +9187
    • View Profile
Re: Logic problems
« Reply #172 on: January 17, 2013, 06:36:07 pm »
0

I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.

A witch captures 50 maidens. She puts them all in a dungeon and tells them: "Tomorrow morning I will separate you into 50 separate cells, so you will not be able to communicate or see each other in any way after tonight. Then every once in a while, a few times a day or so, I will randomly choose one of you and take you to my tower.

The information isn't exact enough that you can do that.  I don't think it is guaranteed that any of them will be taken the first day.  Depends on how you read the problem, I guess.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Logic problems
« Reply #173 on: January 17, 2013, 06:37:55 pm »
0

I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.

A witch captures 50 maidens. She puts them all in a dungeon and tells them: "Tomorrow morning I will separate you into 50 separate cells, so you will not be able to communicate or see each other in any way after tonight. Then every once in a while, a few times a day or so, I will randomly choose one of you and take you to my tower.

The information isn't exact enough that you can do that.  I don't think it is guaranteed that any of them will be taken the first day.  Depends on how you read the problem, I guess.

That's the problem: no maid can be sure that she's the first to be taken to the switch 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.

Axxle

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1664
  • Most Valuable Serial Killer
  • Respect: +1965
    • View Profile
Re: Logic problems
« Reply #174 on: January 17, 2013, 06:49:50 pm »
0

I think it would be a lot faster to have the maiden who goes into the tower Day 1 to set the switch in the proper off position.

A witch captures 50 maidens. She puts them all in a dungeon and tells them: "Tomorrow morning I will separate you into 50 separate cells, so you will not be able to communicate or see each other in any way after tonight. Then every once in a while, a few times a day or so, I will randomly choose one of you and take you to my tower.

The information isn't exact enough that you can do that.  I don't think it is guaranteed that any of them will be taken the first day.  Depends on how you read the problem, I guess.

That's the problem: no maid can be sure that she's the first to be taken to the switch room.
Doesn't matter As long as there's at least one a day, you can declare Day 1 as off switch day.
Logged
We might be from all over the world, but "we all talk this one language  : +1 card + 1 action +1 buy , gain , discard, trash... " - RTT
Pages: 1 ... 5 6 [7] 8 9 ... 11  All
 

Page created in 0.252 seconds with 21 queries.