
Posts
142 
Joined

Last visited

Days Won
1
Content Type
Profiles
Forums
Calendar
Gallery
Blogs
Posts posted by mmiguel


I can determine which one the lier is by asking "What answer will the Random God give when answering this question?" Lier is the one who answers differently (don't need to know what "da" or "ya" means)
i believe your question as it is, is not answerable in general, since the random god can change his answer if you ask him multiple times (a truthful or lying god, would need to know *which* occurrence of you asking the random god you are talking about in order to give a meaningful answer.
i think there is no way to guarantee that the random god will answer differently from the liar, hence you cannot say that the liar will provide a different answer, because the random god can answer however he pleases in his own unfathomable way.

Three gods A , B , and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A , B , and C by asking three yesno questions; each question must be put to exactly one god. The gods understand English, but will answer in their own language, in which the words for yes and no are “da” and “ja”, in some order. You do not know which word means which.
There are 3 smaller, easier puzzles that may serve as hints to building up the answer to this one.
I will post the first one below. Those with pride, feel free to not look.
Noting their locations, I place two aces and a jack face down on a table, in a row; you do not see which card is placed where. Your problem is to point to one of the three cards and then ask me a single yesno question, from the answer to which you can, with certainty, identify one of the three cards as an ace. If you have pointed to one of the aces, I will answer your question truthfully. However, if you have pointed to the jack, I will answer your question yes or no, completely at random.

Can we assume that they know what questions I am about to ask before I ask them?
Hmm....
That could make things complicated because we can get into a circular: "but he knows that I know that he knows that I know that ....", which I would prefer to avoid.
The correct answer allows you to identify which Gods are which regardless of what they think you are thinking.

How omniscient are the 3 Gods?
By this I mean
Can the three identify each other?
and
Can the truth and lying God reliably predict what the random God is going to say if asked?
Edit: can they reliably predict what the random God will say in future?
Is the random God capable of changing his mind one he has decided to go down the path of truth or the path of lies? i.e is is possible to ask him the same question twice and get different answers
They are omniscient.
They each know which God is which.
Random can provide different answers to the same question.
I guess I don't see any harm in them knowing what Random will say if for example you were to use question 1 to ask what Random would say question 2 or on question 3.

Assuming if you ask a god a question they can't answer, they'll say nothing or something completely different that means, like, 'error'...
Ask two of them "If I ask you next 'Is the sky blue', will you answer da or ja?"
If one can't answer, he is the random answerer, otherwise both will answer which ever is yes and the third is the random.
Third question, ask one that answered yes to the first question, "Is the sky blue?" to discern if liar or truth teller.
A question that cannot be answered  sounds like a paradox.
Likely not to get much useful info out of a paradox.
Random can always answer, since he doesn't even need to listen to your question, he can ignore you, flip a coin or roll a die and give you whatever answer he chooses.

A. Is your answer to this question a lie? OR B. Is your answer to this question the truth? Anyone you ask A will answer No and anyone you ask B will answer Yes. This will let you know which word is yes and which is no.
I think this is where I would start. Still working on Q#2 and 3.
Not all will answer that way with certainty, just 2 of 3.

Three gods A , B , and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A , B , and C by asking three yesno questions; each question must be put to exactly one god. The gods understand English, but will answer in their own language, in which the words for yes and no are “da” and “ja”, in some order. You do not know which word means which.

Alex painted a letter on each of nine cans and set them on a fence rail.
There was one duplicate letter.
Using them a target practice, he shot the cans in the following order: 5 6 3 4 2 9 1 8 7.
Amazingly, before and after each shot, the letters on the cans still on the fence spelled an English word.
The initial was was ... ?
startling
starling
staring
string
sting
sing
sin
in
i

Find 11 common English words, each of
which is a subsequence of the string
PLUFIEMDATNGORPAPNLCHGE. The words
are all related by their meanings.
As an example, IMPALE is a subsequence
since its letters occur, in sequence,
from left to right in the string
PLUFIEMDATNGORPAPNLCHGE. Unfortunately,
IMPALE isn't one of the words in the
answer to this puzzle.
ace ache aga agape age ago agog agora ah ale an ana anal angle angora anon apace apache ape apple arc arch are at ate atone atop dace dale dan dance dane dangle dapple dare darn data date do doc doe dog doge doh dole don done dong dope dor dr drag drape each eagle ear earache earl earn eat eatage edge eg egg ego eh em engage engorge enrage eon era ere erg eta etal etch etna face fag fan fang far farce fare fat fatal fate fear feat fed fedora fee female fen fence feral fern fetal fetch fete fiance fiat fiche fierce fig filch file fin final finale finance finch fine finn fir fire fit foal foe fog fop for forage force fore forge franc france gag gage gal gale gang gap gape go goal gone gong gore gorge grace grange grape graph he ice id idle idol im image imago imp impale in inane inch inn ion iran ire it itch lace lag lance lane lap lapp larch large latch late lath lathe lea leach lean leap learn leat led ledge lee leg legal lemon leone let liar lice lid lido lie lied lien lima lime limo limp linage line lino lion lip lira lire lit lithe litre loan loch log lone long lop lope lore ludo lug lump luna lunch lune lung lunge lur lurch lure lute mac mace mag male man manage mane mange mangle mango manor map maple mar mara march mare marl mat match mate math me moan mole mop mope moral morale more morn morph mr nag nap nape ne no noah non none nor oh ole on once one opal or oral orang orange ore pa pace pagan page pal pale pan panache pane pang panga pap papa papal par parch pare pat patch pate path pea peace peach peal pear pearl peat pedal peg pele pen penal penance pence people pep per perch pet petal pi piano pie piece pied pier pierce pieta pig pile pimp pimple pin pinch pine ping pion pip pipe pit pitch pith piton place plan plane plate plato plea pleat pledge plied plop plug plum plumage plume plump plunge plural pluto poach pole ponce pop pope porch pore porn prance prang pre pug puma pump pun punch pup pupa pupae pupal pure purge purl purple put race rag rage ran ranch rang range rap rape re tag talc tale tan tang tap tape the to toe tog ton tone top topple torah torch tore torn trace trance tranche trap ufo up urge urn utah

True, but can anyone answer that question?
try the question on me, i'll try to answer yes and we'll see if i am stopped
lol

OP says "I am thinking about one of my cards." That is an act of selection. It followed an algorithm of some sort. Flipping a coin, shuffling them face down then turning one over, taking the one closest to her as I tossed them across the table, saying eenie meenie money mo ... not thinking at all, praying, in some way, deterministic or not, she made a selection. And, inescapably, how that selection was made affects the answer. So the answer as the OP stands is, "depends."
Without knowing her selection algorithm, how does one arrive at 3/7 as 'right'?
If she thought of the lowerranking card, the probability of both cards being aces is unity: spade ace plus one of the red aces are the only possibilities. OP doesn't say the thoughtof card was the lower one in rank, true; it says nothing about the thoughtof card. 3/7 is 'right' if the thoughtof card was the result of a coin toss. But OP does not say she tossed a coin.
I understand your basic question; I have wondered it myself. Absent any description of the reporter's algorithm, is there a leastrestrictive default assumption that becomes preferable? I could, along with you, make a case for random choice (coin toss) to be that preferred, assumed algorithm. But unless that premise is understood and generally accepted among problem writers and solvers, and not just a few of us, it does leave answers uncertain.
In my boygirl puzzle I had some fun making this point, by imposing a random selection of reporter algorithms.
I like this topic, and those boygirl puzzles made me think about this a lot a couple years ago.
Here is what I think of it, and you may agree with me or not, either way, I find this thought provoking.
I think:
The fundamental difference between part A and part B above is that in that in one case, a statement was made about a specific object (part B), while in the other case, no statement was made about any specific object.
I see this manifest in your solutions 3, 4, and 5 as well.
In 3, we identify one of the cards i.e. the card identified as the first one drawn, and make a statement about that object.
In 4, we also identify one of the cards, i.e. the card identified as the last card drawn, and make a statement about that object.
In 5, we identify one of the cards i.e. the card identified as the one corresponding to heads (for example)
In 6 and 7, the statement is not applied to any specific card.
What I was trying to get at, is that by her "thinking" about a specific card, she has made a selection, and has thus made a statement about a specific card, i.e. the card identified as the one she thought about at this specific point in time.
This concept, that making a statement about a specific object changes the probability problem is very neat to me.
The real idea behind it, is being able to distinguish between objects, and the impact of that on the probability model.
Here is how I think about it in a more general context than this problem:
We are talking about two objects, which must differ in some way (for if they did not, how would you even know they are two objects and not one?).
We can represent them as an ordered 2tuple (x,y).
When we say something about a specific object, we distinguish them in some way, and we can interpret the meaning of the index of the tuple as an indicator of any differing characteristic.
Let's think of some differing characteristics, and apply them here:
x is short and fat
y is tall and lean
you can say the index here (index 0 in the tuple is position x, index 1 in the tuple is position y), can be interpreted as an indicator of fatness.
if the index is 0, the object is fat, if 1 the object is lean.
you can also interpret it as an indicator of shortness.
if the index is 0, the object is short, else the object is tall.
the reason i'm bringing this up, is that you can apply this concept to any distinguishing characteristic.
one such characteristic might be, (friend of problem solver from above problem is thinking about the object).
in general terms, you can take any differing characteristic and map it into an ordering scheme for this 2tuple.
if in a probability problem, we make a statement about a specific object, then we can define a sample space of outcomes, which can be represented as tuples containing the potential states of the two objects, ordered by whatever distinguishing characteristic may be inferred from the statement about the specific object.
let's say that specific object was x (i.e. the object in index 0).
We may modify the sample space to remove all possible outcomes in which the element in index 0 of the tuple does not satisfy the the statement.
now assume no distinguishing statement is made about either object  this is like Part A above. for lack of a better ordering interpretation, let's use whatever ordering system we used from the case in which a statement about a specific object was made.
What outcomes are we allowed to eliminate now from the sample space, given the generic statement about no specific object?
We eliminate all outcomes where neither x nor y (i.e. object in index 0 nor object in index 1) satisfy the statement. This is a completely different change to the sample space than the other case, and the probability conclusions will be different in general.
Thus, a small, subtle detail, changes everything. And it all comes down to being able to distinguish between objects, which in most cases is satisfied by making a statement about one concrete object, and not making the same statement about the other.
Maybe that wasn't the cleanest explanation, but I think I got the meat of it in there.

ah! haha
i suppose i should spend more time reading the prompt then, i guess i was solving the wrong problem
well... i guess my interpretation is not inconsistent with original problem statement, if 1on1 is interpreted as a onetoone mapping i.e. a pair.
"Assume all encounters are 1on1 and random."
i can definitely see how one would see this and assume that in any "round" only 2 people are selected from the population, and said to have "met".
oh well, twas a good exercise of thought.

You: assuming everyone is paired together in such an encounter, with the exception of maybe one odd man out
Me: I worked under the assumption...And that meetings occur one at a time.
ah! haha
i suppose i should spend more time reading the prompt then, i guess i was solving the wrong problem

Yes. See my spoiler above.
In the general case I alluded to above, with K (even) killers and P pacifists, P/ (K+1) pacifists survive on average.
When K=P=10 initially, by joining the pacifists you make P=11, and on average 1 pacifist will stand and can attend the killers' funerals. You have 1/11 chance of being that survivor. If you join the killers, you make K=11 (odd) so it is certain that exactly1 killer is standing at the end. He wipes out any pacifists still breathing when killers 9 and 10 shoot each other. Again, you have 1/11 chance of being the surviving person.
can you share the derivation of P/(K+1)?

And yes I do still think that my chances of survival are still 1/3 in that situation.
My chance of dying in any given encounter does depend on the total number of people, but, if we are thinking end game, it doesn't matter to my final survival what happens to those 100,000 pacifists. My survival depends on the two killers meeting each other before one of them meets me. So the only meetings that affect my survival are (K1,K2), (K1,Me) and (K2,Me). So based on those meetings I have a 1/3 chance or survival.
I worked under the assumption that there comes a point where either there is a single killer left or no killers and some number of pacifists and thus no more meetings are important.
Also, I only considered meetings that affected my survival as important and thats how I came up with (n1)/(n+1).
Am I on the right track or way off?
well in your last post, i had thought you said that (n1)/(n+1) were the chances of surviving any round, but maybe i misinterpreted.
well, i need to think about your response...
i agree that with 2 killers and 100000 pacifists, the last important turn has 3 possibilities.
but have we established that those 3 possibilities are equally likely?
what if there are 100 killers and you are the only pacifist?
your formula says you have 99/101 chance of surviving (pretty good chance), which doesn't seem believable to me.
what if there are 3 killers and you are the only pacifist?
in this case, you basically have to die, no matter what.
in my formula, the chance of survival would be
1  k/(n1) = 13/3 = 0
in yours, it's 1/2

How many initial pacifists would there have to have been for there to be only 100,000 pacifists remaining when the killers numbered but two? What are your chances of being among those 100,000?
In short, what if the puzzle had said Killville has K (an even number) killers and P pacifists when you arrive. You may join the killers, and act like one, or you may join the pacifists and remain unarmed. Which party would get your vote?
BTW, RG is correct to observe that your survival can be defined as follows: among the six events, KK, KK, KK, KK, KK, Kyou, the Kyou event must happen last.
Other events (Kother pacifists) can transpire at any time. They don't harm you, but they don't decrease the killer population either.
chances of survival are probably not very high either way.
but, i showed mathematically in a prior post (unless someone finds a flaw in my reasoning, which is of course very possible), that the chance of surviving a single encounter (assuming everyone is paired together in such an encounter, with the exception of maybe one odd man out), increases as the total number of pacifists increase while the number of killers remain the same.
it is thus in your best interest to make any possible decision you can to result in as many pacifists being alive in each round as possible.
it's like the evolutionary strategy of a school of fish  band together so that although the chances of a shark getting a meal are large, within the school itself, the likelihood of any particular fish getting eaten in a single shark encounter decreases.
being a killer erodes your "protection" faster.
you may likely die either way, but you have a slightly better chance of surviving if you don't kill others, letting them live in order to take a bullet for you later in the future.
Pacifist

This depends on how she selects the card to talk about, and that otherwise she would not speak.
That is, she "thinks about" one of the cards, and the statement is true of that card.
Possibilities include:
1. the higherranking card,
2. the lowerranking card,
3. the first card dealt to her,
4. the second card dealt to her,
5. a random selection, e.g. one based on the result of a coin toss,
6. her way of saying I just looked at both cards and it turns out that at least one of them is a red ace,
7. her way of responding to my question: is at least one of your cards a red ace?
When a reporter describes some aspect of an outcome, the conditional probabilities about that outcome are affected by the algorithm the reporter follows when she makes her report.
For example, see
1. 3/11
2. 1 (certainty)
3. 4. and 5. 3/7
6. and 7. 5/13 (same as first puzzle)
each of those adds some assumptions about her method of selection which were not given in the problem.
what is the fundamental premise uniting 3, 4, and 5 to make them have the same answer? (3/7 is the correct answer to part B btw).
is it possible to use that same premise without adding additional detail other than what was stated explicitly in the problem?

This one is cool!
http://en.wikipedia.org/wiki/Richard's_paradox
The paradox begins with the observation that certain expressions in English unambiguously define real numbers, while other expressions in English do not. For example, "The real number whose integer part is 17 and whose nth decimal place is 0 if n is even and 1 if n is odd" defines the real number 17.1010101..., while the phrase "London is in England" does not define a real number.
Thus there is an infinite list of English phrases (where each phrase is of finite length, but lengths vary in the list) that unambiguously define real numbers; arrange this list by length and thendictionary order, so that the ordering is canonical. This yields an infinite list of the corresponding real numbers: r_{1}, r_{2}, ... . Now define a new real number r as follows. The integer part of r is 0, thenth decimal place of r is 1 if the nth decimal place of r_{n} is not 1, and the nth decimal place of r is 2 if the nth decimal place of r_{n} is 1.
The preceding two paragraphs are an expression in English which unambiguously defines a real number r. Thus r must be one of the numbers r_{n}. However, r was constructed so that it cannot equal any of the r_{n}. This is the paradoxical contradiction.

5/13
The Kings and Aces form T7 = 28 hands.
13 hands have at least 1 red ace.
5 of them have two aces.
To make this shortlived thread more interesting, part B is below:
You decide to repeat this game, and follow the same procedure as above in order to deliver her two cards to her.
This time, she looks at the two cards and says: "I'm thinking of one of the cards in my hand right now, and it is a red Ace!"
What is the probability that both of her cards are Aces of any color?

completely irrelelvant.
(Assuming that when I leave the town the only possible meetings left involve no deaths and all meetings occur one at a time.)
No matter which I choose to be I have about a 9% chance of surviving. That is without counting any meeting that didn't involve me or a killer dying. Because none of the other meetings affect my chance of surviving at the end.
Basically it comes down to me vs. killers. Whether I'm a killer or a pacifist I cannot meet a killer or else I die.
So I need there to be 5 meetings of killers for me to survive. For each set of possible meetings, that count, my chance of survival is (n1)/(n+1) where n is the number of killers left that aren't me. Which gives us...
9/11 * 7/9 * 5/7 * 3/5 * 1/3 = 1/11 or .0909... or 9.0909...%
And that is my take on it.
Let's say there were 2 killers left, and 100,000 pacifists (I know, can't be more than 10  have patience).
Do you really think your chances of dying here are
(21)/(2+1) = 1/3?
Of all the other people out there they could kill, why would the killers be so likely to kill you?
Answer:
Because your chance of dying is not (n1)/(n+1), but depends on number of nonkillers out there too.

this is basically the same algorithm i came up with, for finding a single king.
I would use method II, which allows you to see who any given competitor defeated
while king not found
{
pick a competitor at random.
delete everyone that this competitor defeated (this should be proportional to n operations)
if competitor is last one
{
he is king
}else{
delete him too
}
}
on average, deleting everyone a competitor is defeated reduces the number of competitors left by some proportion.
Thus the number of times this must be done is proportional to the log of n.
Each time this is done, there are something proportional to n operations due to deletions.
The time complexity is there for O(n*log(n)), as phil stated.
I don't think there is an algorithm with better time complexity for finding a single tournament king.
This algorithm does not find all tournament kings though.
Nice work phil!
Let's say we pick random competitor A.
Let W(A) be the set of competitors who won against A and L(A) be the set of competitors that lost to A.
Selection of A allows us to partition the competitors into three groups:
W(A),
A,
and L(A).
Notice that it is true for any member of W(A), that they defeated A directly, and defeated everyone in L(A) indirectly i.e. they defeated A who defeated whoever we are talking about in L(A).
Thus for any member of W(A), to determine that they are a king, we merely need to prove that they defeated everyone else in W(A) directly or indirectly.
That is, pretending that W(A) is the only thing in the whole world (ignoring A and L(A)), find a tournament king there.
This is the same thing as the initial problem, except we reduced the problem size!
Keep doing this until you have eliminated all but 1 competitor.
By the logic above, he has defeated everyone else either directly or indirectly, and is a tournament king.
QED

I ran every combination for N = [4,5,6]. There were no cases where the king didn't score against another player either directly or indirectly. I'm pretty sure that will hold for N > 6...
Can I cheat and use all three methods?
Use method 2 and method 3 for a given player with method 1 until a win is found against method 3 player or no win found.
w = M2[p].count If w = 0 then k = false  exit If w = N  1 then k = true  exit l = N  w  1 k = true For i = 1 to w f = false For j = 1 to l r = M3[p][j] If M1[ M2[p][i] , r ] = r Then f = true j = l End If Next If f = false Then k = false j = w End if Next If k = true then "Congrats on being a TOURNEY KING"
I think this would work... what would the lookup count be?
Looks like you are trying to prove that at least one tournament king exists regardless of who wins who.
I would use mathematical induction.
Prove that this is true for something simple, like n=2.
Then prove that the truth of the statement for n, implies the truth of the statement for n+1.
i.e., pretend you already know it is true for arbitrary n, then prove that it must also be true for n+1.
Based on double loop, I think this is O(n^2) algorithm.
Your second post has a double loop too, so I think they are both O(n^2).

Call the Beats table B. If Q beats P, we'll say "Q B P"
Copy Beats table, call it B2. If Q beats someone who beats P, we'll say "Q B2 P"
For Q in 1...N
....For P in 1...N (skip Q)
........if Q B P
............for each R in 1...N (skip Q and P)
................if P B R
....................set Q B2 R
....count = 0
....For P in 1...N (skip Q)
........if Q B P  Q B2 P, increment count
....if count = N1, Stop, declaring Q to be a TK. (or print is a TK)
If you want all TKs, then don't stop, just print and keep going through all Q in 1...N
The time is order of n^3 in either case.
Analogous algorithm on Lostto lists is also n^3 for one TK.
I'm not proud...
edit: gack, formatting.
this looks like it works and has O(n^3) time complexity

Phil, imagine competitor P, who beat everybody but Q, and Q lost to everybody but P.
Q is a tournament king, even though he lost to almost everybody.
this is true, and one can think of a contrived example where in each step of elimination, you can only eliminate one or two participants.
this would give time complexity O(n^2), which isn't all that great.
however, the famous sorting algorithm quicksort has a similar weakness for certain initial orderings.
in practice, it is well known to have O(n*log(n)) time complexity on average, although for certain initial conditions can have O(n^2).
given the similarities to quicksort, I would say that phil's algorithm justly deserves the O(n*log(n)) label.
Evil Genies
in New Word Riddles
Posted · Edited by mmiguel
I thought this might be fun, but maybe it will flop.
A person finds a magic lamp with an evil genie inside.
The person may ask for any wish to be granted.
The genie, spiteful for having to serve a pitiful little human with his phenomenal cosmic powers, wants to make his master regret every wish that is made.
Posters, assume the role of either the genie of the human.
Rules:
I. Both genie and human are powerless to change these rules
II. As the human , you should wish for something that most people would actually find desirable.
III. Everything the human explicitly wished for must come true, and all harm (physical, mental, psychological, ...etc) that the spiteful genie inflicts should ultimately derive from a creative interpretation of the wish (e.g. deliberately ignoring common implications in speech that are not explicitly stated, or taking things out of context, ...etc). E.g. it's cheating if a person wishes for a million dollars, and the genie gives him a million dollars and also dumps a bucket of lava on his head (lava has nothing to do with the wish). It's not cheating if a person wishes for eternal life, and the genie prevents them from ever dying, but allows their body to to continue to age and weaken normally forever into some grotesque shamble that doesn't even look human  in this case, the person's eventual regret derives from making the wish in the first place.
IV. The genie cannot control his master's mind. This may sound good for the master, but it prevents the genie from being able to grant wishes like: I wish to always be happy forever.
V. Off limits: Wishing for more wishes, wishing for multiple things in one wish. The wish should be one thing possibly followed by further clarifications that specify the one thing. Cannot undo wishes.
Challenge:
Humans: Find an uncorruptible wish.
Genies: Corrupt every wish
Let's see who wins!
Here's one to start with:
"I wish to be the most intelligent person ever"