Wikipedia:Reference desk/Archives/Mathematics/2015 June 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 29

Logic puzzle

I can't search for answers to this, as I don't know what to call it.

Imagine a sparsely filled in grid with one location being the prize cell. X knows the x coordinate. Y knows the y coordinate. (1) Y says "I do not know where the prize is. And I know you do not know where the prize is". (2) X thinks and then says "I did not know where the prize was, but now I do". (3) Y then says "Now so do I".

How do you solve this? 1a permits you to eliminate all y coords with only one cell in them - else Y would know which cell. 1b obviously eliminates all x coords with only one cell in them - else X would know which cell. Additionally I think it eliminates all y coords with a cell that is solo in a x coord. But then I run out of steam.

In the example below

* * * A * * * * B *
C * * * * * * * * *
* * * D * E * * * F
* * * * * * G * * *
* * * * H * * * J *
* * K * * * * * * *
* L * * * * * M N *
* * * P * Q * R * *

1a eliminates CGK 1b eliminates FHL and thus DEF HJ LMN

That leaves ABPQR. What next? (BTW, I know the answer, I just can't work out why it is the answer.) -- SGBailey (talk) 07:48, 29 June 2015 (UTC)

For the first clue, Y does not know where the prize is, so Y must know a y-coordinate which matches more than one letter. Y also knows that X does not know where the prize is, which means that for each letter in the row Y has been given, there is another letter in the same column (otherwise, if that were the correct answer, then X would know it). So 1a eliminates C, DEF (since if the answer was F, then X could know it, any Y knows that X cannot know it), G, HJ (ditto for H), K, LMN. Which leaves just AB and PQR. I'll let you finish off working it out, but bear in mind you cannot get the answer until you apply the final clue (i.e. you can only know the answer after both X and Y know it). MChesterMC (talk) 08:34, 29 June 2015 (UTC)

You have just repeated the analysis that I presented in the question, leaving as an exercise the part of the solution that I haven't worked out how to do. I'm afraid I didn't find that helpful. -- SGBailey (talk) 09:32, 29 June 2015 (UTC)

Can you explain this logic further... Suppose Y knows it is in the DEF row, but doesn't know which one it could be. When X says he doesn't know which it is, that eliminates F. You state that it also eliminates D and E because it cannot be F. Why? If it were D, Y wouldn't know if it was D or E and X wouldn't know if it was A, D, or P. If it was E, Y wouldn't know if it was D or E and X wouldn't know if it was E or Q. 209.149.113.185 (talk) 19:11, 29 June 2015 (UTC)

(2) tells us that after excluding all those that (1) excludes, X should know where it is. So, of ABPQR it couldn't be A or P which share an x coordinate. Then (3) tells us that once we exclude all those that (2) exlcudes, Y knows where it is. Therefore, of those allowed by (2), BQR, it must additionally have a unique y coordinate. That leaves B. 129.234.186.11 (talk) 11:13, 29 June 2015 (UTC)

Thank you. A "very involved" solution. Do these kind of problems have a name? -- SGBailey (talk) 12:45, 29 June 2015 (UTC)

You just want a recursive solution. The solution takes the board and eliminates all rows and columns with a single solution. Then, recursively solve that board. To make it stop, do not make a recursive attempt if no columns or rows were removed. 209.149.113.185 (talk) 18:44, 29 June 2015 (UTC)

That's not enough to solve it. That only gets you down to ABDEMNPQR. You also need that Y knows the answer once he knows that X knows, to solve it. StuRat (talk) 19:12, 29 June 2015 (UTC)

Since each person's strategy is based on assuming the other player is rational (and quite intelligent, in this case), this gets into game theory. StuRat (talk) 19:17, 29 June 2015 (UTC)

I really don't think game theory applies. Game theory is when people actually have a choice of what to do. Here the actors don't have a choice, they're merely reporting everything they know, and they're assumed to be perfect deducers. -- Meni Rosenfeld (talk) 21:25, 29 June 2015 (UTC)

Doesn't the fact that the conclusions they draw are dependent on the actions of others (the accuracy and honesty of their statements, in this case) qualify ? StuRat (talk) 22:38, 29 June 2015 (UTC)

I don't think so. "Dependence" on the other's accuracy and honesty is only meaningful if there is a counterfactual possibility that the other party is not accurate or honest. If each person had a probability of being incorrect, and a choice of whether to be honest or not, and a payoff table that depends on both of their actions, then it would be game theory. But here there is no choice - the people are merely following the script of the problem statement.

You could try to force this problem into game theory formulation, but - game theory analysis generally starts with a description of the game, and then deduces the best actions; here we are not given a description of the game, we are just given the actions that actually take place. Formulating it as game theory would take you further from a solution, not closer - once you did this, you will still have to solve the problem using normal logic as we did here. The tools of game theory simply don't help. It's like being asked to calculate 3*4, and trying to solve it by phrasing it as a decision theory problem where the player gets the most utility by choosing the correct answer for 3*4. You'd still need to calculate 3*4 to find his best action. -- Meni Rosenfeld (talk) 10:10, 30 June 2015 (UTC)

I don't know of a name for it, but a problem of this kind called the "Cheryl birthday problem" caused quite a bit of hype a short time ago. -- Meni Rosenfeld (talk) 21:25, 29 June 2015 (UTC)

Broadly, it's a type of logic puzzle. The "Cheryl birthday" problem mentioned by Meni has an artile Cheryl's_Birthday, and it is indeed very similar. Another logic puzzle that hinges around people reporting what they know is this one [1]. SemanticMantis (talk) 21:50, 29 June 2015 (UTC)

Thank you Semantic, I have to admit defeat. Do you have the solution? Widneymanor (talk) 07:47, 1 July 2015 (UTC)

@Widneymanor: You mean the blue eyes problem? You need to prove by induction that if there are n blue-eyed people, then they will all leave exactly on day n.

Incidentally, when I first heard this problem, it was about wives cheating on their husbands, and the husbands murdering them when they find out. -- Meni Rosenfeld (talk) 13:18, 5 July 2015 (UTC)

"Unseriesable " Number?

Hi
I would like to know, if there is a definition to a real unseriesable number.
Meaning that there isn't any series that its limit is that number.
23:15, 29 June 2015 (UTC) — Preceding unsigned comment added by Exx8 (talk • contribs)

Every real number is the sum of some infinite series. Is that what you were asking? I'm not quite sure. --Trovatore (talk) 23:32, 29 June 2015 (UTC)

For any real number $V$ there is a trivial sequence $v$, whose limit is $V$: $\lim _{i\to \infty }v_{i}=V$ — a constant sequence $(v_{i})_{i\in \mathbb {N} }$ defined by $v_{i}=V$. If we take a sequence of differences:

$d_{i}={\begin{cases}v_{i}&{\text{for }}i=1\\v_{i}-v_{i-1}&{\text{for }}i>0\end{cases}}\ \ =\ {\begin{cases}V&{\text{for }}i=1\\0&{\text{for }}i>0\end{cases}}$

then the sum of $d$ series is clearly $V$:

$\sum _{i=1}^{\infty }{d_{i}}=V$

Of course there are also other sequences convergent to $V$, for example a sequence of longer and longer decimal approximations, and each such sequence defines a series summing up to $V$.

For $\pi$ it might be a sequence
$v=(3,3.1,3.14,3.141,3.1415,3.14159,\dots )$
and a corresponding series
$d=(3,0.1,0.04,0.001,0.0005,0.00009,\dots )$
--CiaPan (talk) 05:12, 30 June 2015 (UTC)