Post by Warp

Posted: 5/12/2018 6:26 AM

Quote

Nickolas

Joined: 7/13/2014
Posts: 36

Warp wrote:

"The second most irrational number" would refer to the "most irrational" number that's not equal to those. I suppose one could come up with infinite patterns of 1's and 2's in the continued fraction representation, a simple example would be alternating between them. I suppose it could be argued to be "more irrational" than sqrt(2), because the continued fraction approaches that value slower than the one for sqrt(2). Out of curiosity I tried to solve what 1+1/(2+1/(1+1/(2+... equals to, and I got (1±sqrt(3))/2.

Not quite, what's being said is that concept of a second most irrational number (or family of numbers, if you prefer) isn't well-defined. There's no such number in the same way that there isn't a smallest positive real number. Root 2 is [2, 2, 2, ...]. What's a more irrational number by the criterion you proposed at the start of this discussion? Well, there's an infinite amount such numbers, but for example, [1, 2, 2, 2, ...] is more irrational. Is that the second most irrational number, then? Well, no, [1, 1, 2, 2, 2, ...] is more irrational, etc. This sort of reasoning also suffices if you wish to only consider equivalence classes of numbers that have the same convergence characteristics in their continued fraction representation, as p4wn3r mentioned. Is [2, 2, 2, ...] the second most irrational class? No, [(1, 2), (1, 2), (1, 2), (...)] is more irrational. Is that the second most irrational class? Well, no, [(1, 1, 2), (1, 1, 2), (1, 1, 2), (...)] is more irrational. Is that the second most irrational class? Well, no, double the number of 1s between each 2 again, etc. You could likely extend the idea of continued fractions with something similar to a surreal infinitesimal to obtain, by definition, a number less rational than any non-phi number. I suppose that could reasonably be referred to as the second most irrational number, though it wouldn't actually represent a number any more than surreal ε does. (But what is a number anyway?) As to whether that would lead to interesting or useful mathematics ... I have my doubts. Assuming the "surreal continued fractions" can be well-defined, their structure is probably equivalent to something more natural.

Posted: 5/19/2018 6:36 PM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

As we know, the continued fraction 1+1/(1+1/(1+1/(1+... = phi, ie. the golden ratio. One of the simplest and most traditional ways to see this, ie. to solve the value of the continued fraction is to notice that the first denominator is exactly the same as the whole thing. Thus we can say that if x is the continued fraction, then: x = 1+1/x We can convert that to polynomial form (by multiplying both sides by x and bringing everything to the left side): x² - x - 1 = 0 When you apply your favorite method of solving the quadratic equation, we get the famous result x = (1 ± sqrt(5))/2, which is the definition of phi. One of the two possible solutions is negative, approximately -0.618. But this raises the question of how the continued fraction can give a negative value. Where is the negative answer coming from? Is there a step in the solution that made a wrong assumption, or missed something, giving two values for the continued fraction, one of them negative?

Posted: 5/19/2018 9:19 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Warp, you have already asked pretty much the same thing on April 13th, and two people answered you at the time. Care to explain what was not clear in the previous replies?

Posted: 5/20/2018 1:58 AM

Quote

BrunoVisnadi

Editor, Skilled player (1344)

Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil

Warp wrote:

As we know, the continued fraction 1+1/(1+1/(1+1/(1+... = phi, ie. the golden ratio. One of the simplest and most traditional ways to see this, ie. to solve the value of the continued fraction is to notice that the first denominator is exactly the same as the whole thing. Thus we can say that if x is the continued fraction, then: x = 1+1/x We can convert that to polynomial form (by multiplying both sides by x and bringing everything to the left side): x² - x - 1 = 0 When you apply your favorite method of solving the quadratic equation, we get the famous result x = (1 ± sqrt(5))/2, which is the definition of phi. One of the two possible solutions is negative, approximately -0.618. But this raises the question of how the continued fraction can give a negative value. Where is the negative answer coming from? Is there a step in the solution that made a wrong assumption, or missed something, giving two values for the continued fraction, one of them negative?

I don't know if that's the answer you are looking for, but simply x = 1 + 1/x doesn't imply x = 1+1/(1+1/(1+1/(1+... See how a different infinite fraction can lead to the same equation: x = 1/(-1 + 1/(-1 + 1/(-1 + 1... x = 1/(x-1) 1/x = x-1 1/x + 1 = x

My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3

Posted: 5/20/2018 3:08 AM

Quote

Aran_Jaeger

He/Him

Banned User

Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany

I felt like putting a math challenge in here that I came up with for myself a long time ago, for anyone that feels like figuring out solutions to it. So the basic idea is to generalize the concept of a symmetry axis to ''symmetry curves'' (which could be done in different spaces and dimensions, I guess). But here's the concrete challenge: Given a mapping f living on the (let's say only strictly positive) reals, so f: |R^{+} -> |R, x |-> f(x):= 1/x, the task is to find the set of all continuously differentiable functions g: U -> |R, x |-> g(x) (or curves, respectively), for a (preferably large) open subset U of |R^{+}, such that for every point (x,g(x)), x in |R^{+} arbitrary in U, on this to-be symmetry curve's graph in the 2-dimensional plane |R^2 in which the graph lies, it shall hold that if one draws the unique affine function (i.e. a function h: |R^{+} -> |R of the form x |-> h(x):= a°x+b for some real constants a and b) that is (i) orthogonal in |R^2 to the graph of the slope of the function g at the point x and (ii) goes through the point (x,g(x)), there shall exist exactly 2 intersections of the graphs of h and f, and the Euclidean distance from one of these 2 points of intersections in |R^2 to (x,g(x)) needs to be the same as it is for the other. If possible, one may (try to) represent the set of solutions as a 1-parameter family. As a simple example, the identity id: U -> |R, x |-> id(x):=x, that lives on U = ]1,+infinity[ satisfies the condition as (known symmetry axis of the hyperbola and) special case.

collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)

Posted: 5/29/2018 7:51 AM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

I suppose this is only tangentially related to math, but perhaps it does fit. I recently started wondering about this, and did my calculations and came up with a number, and then asked in a chess forum for other people's opinions, and the final consensus agreed. (Thus, if you google for this you'll probably find the answer. You might want to think about it yourself, though, for the challenge.) In tournament chess, a player can claim draw if the same board position repeats a third time. (Also, in computer chess tournaments a game is usually automatically adjudicated a draw if this happens.) This is the so-called "three-fold repetition" rule. However, there are more rules to "position repeats" than simply the same pieces being on the same squares: For the position to be considered repeated: 1) it has to be the same player to play, and 2) all the possible moves have to be the same. The second restriction considers "being able to castle to king side" and "not being able to castle to king side" to make a difference, even if all the pieces are on the same squares. The same for castling to queen side. Likewise being able to capture en-passant vs. not being able, also makes the position to be considered "different". So my question is: What is the theoretically absolute maximum number of times that the same arrangement of pieces can repeat on the board without the 3-fold repetition rule kicking in?

Posted: 5/29/2018 2:09 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Hmm, twenty-one? One way to go at this problem is to use FEN. In FEN, besides the actual arrangement of pieces on the board, you have one extra field for an en passant square, a flag for which side is moving, four other flags for all possibilities of castling and some numbers for the fifty-move rule and the current move, which are irrelevant for this problem. So, we can play with the en-passant square and the castling and side-to-move flag to reach the same piece arrangement without actually the same position. It is impossible to reach a position with a non-empty en passant square more than once. That's because to allow en passant, you have to make a pawn advance, which cannot be undone. For castling, you'd have 2^4 possibilities, but in a game once you lose the right to castle (by moving the rook, for example), you can never get it back. Therefore, a single game can only reach five different configurations of the castling flags. To reach the maximum, we could do something like this: a) Get a position where all kings and rooks have not moved, and they are the only pieces in the first rank. b) One side advances a pawn two squares from the starting position, allowing an adjacent enemy pawn to capture en passant (1). c) The other side declines en passant and both sides return to the piece arrangement twice (+2). d) The sides triangulate and return to the arrangement twice with the other player moving (+2) e) A rook is moved, losing the right to castle at that side. The arrangement is repeated twice, and the sides triangulate again to reach the position two more times (+4). f) Step (e) can be repeated for the other three rooks (+12) That gives a total of 21 repetitions of the piece arrangement. Returning to a position takes four half-moves, while a triangulation five half-moves. The first time the arrangement is reached is by means of a pawn advance, so the fifty-move rule is reset. Of the other 20 revisits, 5 are achieved through triangulations, so we need to do 15x4 + 5x5 = 85 half-moves, which is less than the 100 half-moves from the fifty-move rule, so the game would not be drawn. The only thing left to check is whether it's possible to do the procedure without getting 3-fold repetition on an intermediate position (when you are moving the pieces to get back to the arrangement you want), but I guess with enough pieces and a sufficient number of squares for them to move, that should not be a problem. The definitive proof would be to construct a game, but I'm too lazy to do that :P

Posted: 5/29/2018 2:56 PM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

p4wn3r wrote:

Hmm, twenty-one?

Correct. Curiously, different chess frontends have varying degrees of accuracy on this, and might report 3-fold repetition too soon (ie. their algorithm for detecting actual 3-fold repetition is lacking). Not all of them have been properly programmed to detect it correctly. I also hear that something like this is also used to test how well chess engines are programmed to detect by-the-book 3-fold repetition. (Although, to be fair, perfect implementation seldom affects the playing strength of the engine, given that having the same piece arrangement repeat just 3 times without it being 3-fold repetition is extraordinarily rare, not to talk about the longer cases. Engines probably at the very least check if it's the same side to play, because that's probably the most probable situation where extra repetitions can happen.)

Posted: 5/29/2018 3:31 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Out of curiosity, has there ever been an instance where this caveat raised problems in an actual tournament? It's common practice that when you're ahead, but have to play a long endgame to take the victory, you start repeating positions (although obviously not three times) to quickly reach move 40, so that you get more time on the clock. I can picture that someone might confuse three-fold repetition rules and accidentally concede a draw, or a player might claim a draw where one does not exist. Has this ever happened?

Posted: 5/29/2018 3:43 PM

Quote

Masterjun

He/Him

Site Developer, Skilled player (1988)

Joined: 10/12/2010
Posts: 1185
Location: Germany

I made a game where no threefold repetition occurs with an arrangement of pieces repeated 21 times: https://lichess.org/kRWGVeUa This repeated position is starting at move 9:

Shown are the castling moves and the en passant. The PGN is:

1. e4 e5 2. d4 d5 3. Nh3 Nh6 4. Na3 Na6
5. Bc4 Bc5 6. Bf4 Bf5 7. Qf3 Qd6 8. dxc5 exf4
9. g4 Bg6 10. Bb3 Bf5 11. Bc4 Bg6 12. Bb3 Bf5
13. Bc4 Bd7 14. Bb3 Be6 15. Bc4 Bf5 16. Bb3 Bg6
17. Bc4 Bf5 18. Rg1 Bg6 19. Rh1 Bf5 20. Bb3 Bg6
21. Bc4 Bf5 22. Be2 Bg6 23. Bd3 Bf5 24. Bc4 Bg6
25. Bb3 Bf5 26. Bc4 Bg6 27. Rb1 Bf5 28. Ra1 Bg6
29. Bb3 Bf5 30. Bc4 Bd7 31. Bb3 Be6 32. Bc4 Bf5
33. Bb3 Bg6 34. Bc4 Bf5 35. Bb3 Rg8 36. Bc4 Rh8
37. Bb3 Bg6 38. Bc4 Bf5 39. Be2 Bg6 40. Bd3 Bf5
41. Bc4 Bg6 42. Bb3 Bf5 43. Bc4 Rb8 44. Bb3 Ra8
45. Bc4 Bg6 46. Bb3 Bf5 47. Bc4 Bd7 48. Bb3 Be6
49. Bc4 Bf5 50. Bb3 Bg6 51. Bc4 Bf5

Fun fact, there are also two other arrangements of pieces which occur 13 times. Other fun fact, at the end, we're only 15 half-moves away from draw due to the fifty-move rule. Edit: I just realized three replies happened while I was busy, yeah so the 15 half-moves are just as p4wn3r said.

Warning: Might glitch to credits I will finish this ACE soon as possible (or will I?)

Posted: 5/29/2018 5:32 PM

Quote

FractalFusion

Editor, Expert player (2073)

Joined: 6/15/2005
Posts: 3282

p4wn3r wrote:

Out of curiosity, has there ever been an instance where this caveat raised problems in an actual tournament? It's common practice that when you're ahead, but have to play a long endgame to take the victory, you start repeating positions (although obviously not three times) to quickly reach move 40, so that you get more time on the clock. I can picture that someone might confuse three-fold repetition rules and accidentally concede a draw, or a player might claim a draw where one does not exist. Has this ever happened?

Wikipedia gives a couple instances of this happening to top players.

Posted: 5/30/2018 1:29 AM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Raymond Smullyan, who passed away last year, is, in my opinion, one of the most underrated logicians ever. He knew extremely well many complicated subjects of mathematical logic and could explain them in simple-to-understand logic puzzles. His most famous work is outlining how Tarski's theorem, which is much more general and easier to prove than Gödel's seriously shakes the foundations of mathematics. The key assumptions in Tarski's theorem are negation and self-reference, which is a common theme in Smullyan's puzzles. They always involve people who always lie or always say the truth, and make statements about themselves or about friends who make statements about them, and sometimes if the puzzle is solvable or unsolvable given some piece of information, and you have to work out what's actually happening. I believe his book The lady or the tiger? is among the best works of mathematics ever written. He starts with elementary puzzles that confuse laymen and quickly develops to more complicated logic puzzles, concluding with some chapters on formal systems in disguise, that has a puzzle which is essentially the proof of Tarski's theorem. The key argument in the proof (the Gödel sentence) can be written very elegantly in the "Smullyan way". Consider an island where every inhabitant is either a knight or a knave. Knights always say the truth, while knaves always lie. Some knights, called established knights, belong to an exclusive club (which is essentially provable sentences). The question is, if you hear someone say "I am not an established knight.", what can you say about that person? Simple, such person has to be a knight, because a knave would never make the true statement that he's not an established knight, so his statement must be true, which means that he's indeed not established. Translating into formal systems, we have a sentence that's true but is not provable. Another beautiful part of the book is the following paragraph: "I must tell you an interesting and revealing incident," said Ferguson. "A student was asked on a geometry examination to prove the Pythagorean theorem. He handed in his paper, and the Mathematics-Master returned it with a grade of zero and the comment, 'This is no proof!' Later, the lad went to the Mathematics-Master and said, 'Sir, how can you say that what I handed you is not a proof? You have never once in this course defined what a proof is! You have been admirably precise in your definitions of such things as triangles, squares, circles, parallelity, perpendicularity, and other geometric notions, but never once have you defined exactly what you mean by the word 'proof.' How, then, can you so assuredly assert that what I have handed you is not a proof? How would you prove that it is not a proof?'" This is a sadly accurate depiction of our educational system, and even many professional mathematicians have trouble understanding this simple idea. You can regularly see people pushing for different axiomatizations of mathematics, with philosophies like constructivism/finitism/whatever. In fact, they are trying to circumvent some assumptions of Gödel's theorem to find better foundations. But, as Tarski already proved long ago, this is a fantasy. The impact of Gödel's theorems do not depend on infinity or on a particular arithmetic. They happen whenever you have a language that can make assertions about the semantics of its own sentences. To circumvent this, you must create something that has absolutely no resemblance to human reasoning. Indeed, as Smullyan tells us at the end of his book: "In the prophetic words of the logician Emil Post (1944), this means that mathematical thinking is, and must remain, essentially creative. Or, in the witty comment of the mathematician Paul Rosenbloom, it means that man can never eliminate the necessity of using his own intelligence, regardless of how cleverly he tries." So, after this long introduction, paying homage to Smullyan, I will propose here the puzzle that gives the book the title "The lady or the tiger?", which is originally a short story about an unsolvable problem. The puzzle follows below: A prisoner is having a lady and tiger trial, but instead of purely chance, he can save himself using logic. There are nine doors. One of the doors has a lady behind and the others are either empty or have tigers behind them. If the prisoner enters the door with the tiger, he dies. If he enters an empty room, nothing happens, and if he enters the one with the lady, he marries her. The lady is a woman the prisoner loves, so he would prefer marrying her. At each of the nine doors there is a sign. If a lady is inside, the sign says the truth. If a tiger is inside, the statement on the sign is false. If the room is empty, the sign can be either true or false. The signs on each of the rooms are: I - The lady is in an odd-numbered room. II - This room is empty. III - Either sign V is right or sign VII is wrong. IV - Sign I is wrong. V - Either sign II or sign IV is right. VI - Sign III is wrong. VII - The lady is not in room I. VIII - This room contains a tiger and room IX is empty. IX - This room contains a tiger and VI is wrong. The prisoner then looks at the signs and concludes "This problem is unsolvable! That's not fair!". "I know", laughed the king. The prisoner replies "Very funny! Come on, now, at least give me a decent clue: is room VIII empty or not?" The king told the prisoner whether Room VIII was empty or not and the prisoner successfully deduced the location of the lady. Which room has the lady?

Posted: 5/30/2018 4:54 AM
(Edited: 5/30/2018 1:08 PM)

Quote

Aran_Jaeger

He/Him

Banned User

Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany

Okay, after taking a sheet of paper to draw out the structure of the logical statements as some directed graph, I get to the following results: Under the additional (to the assumptions and statements part of the presented logical system) given assumptions that (1) it holds true that any statement (that refers to the system) that can be expressed is either true, or false, or undecidable (by only the statements provided by the system, such that any case (true or false) would not lead to any contradiction via statements from the system), and (2) there exists exactly 1 door among these 9 doors that has a Tiger behind it, and (3) for any of these given 9 doors, there's either a Tiger behind it, or the Lady, or nothing (the room behind the door being empty), (4) and I think I possibly might also need the ''tertium non datur'', i.e. that the negation of a false statement is a true statement (and vice versa but I think this might already follow), in the procedure of going through distinguished cases that are one after another separately investigated, one can quickly cut down the number of potential candidates for situations that describe what is behind every door as follows: First of all, one can notice that the statement of the sign of door VIII is the only statement (among all 9 door sign statements) that has no other door sign statement that refers to this door sign statement (since the sign of door I makes a statement about all door sign statements part of odd doors, V makes a statement about the even cases II and IV, and IX makes a statement about VI), so this seems like a good candidate for a starting point for case distinctions. A: Now, by observing that in the case that the rooms behind door VIII aswell as IX are empty, we get a contradiction from the statement VIII independent on if it (as statement that corresponds to an empty room) is true (then by VIII, the Tiger is in the room that corresponds to VIII, but by assumption of the case distinction, the room is empty at the same time, and by my assumption (3), both cannot be the case at the same time and leads to a contradiction due to (1)) or false (in which case VIII claims that the room behind IX is empty, and because the statement VIII in this case is false, this means we gain the statement that the room behind IX is non-empty, contradicting the assumption of the case distinction by (1)). Hence we can conclude that the system is in a situation in which at least 1 of the two rooms, the room behind VIII and the room behind IX, is non-empty, and by (3), there's either the Lady behind 1 of the two doors, or a/the (by (2)) Tiger behind 1 of the two doors, or the Lady and the Tiger distributed to the 2 rooms behind those two doors. B: If we now assume that the room behind VIII is non-empty, then we get to a contradiction, since in case that the Lady is in the room behind VIII, we get by VIII (and the truth of its statement due to the Lady being behind its corresponding door) the statement that the Tiger is also behind this door that corresponds to the sign VIII, and by (3) a contradiction; and in the case that a Tiger is in the room behind VIII, we get by VIII and its statement being false due to a Tiger being in the room behind VIII the new statement that the room behind VIII is either empty or has the Lady, and in neither of these cases there can be a Tiger in the room behind VIII due to (3) which is a contradiction to the assumption of the case distinction due to (1); and these are by (3) the only 2 possible scenarios. Hence (by (3)), we are left with the only remaining possibility, namely that the room behind VIII is empty. And immediately it follows via the first case distinction A that the room behind IX cannot be empty. C: Now if we assume that a Tiger is in the room behind IX, then by the statement IX together with this statement being false due to a Tiger being in the room behind IX, we get a contradiction similarly as before with the assumption of the case distinction that the Tiger is behind IX together with the statement that the room behind IX is either empty or has the Lady. This leaves us with the only possibility left (if there even is any scenario in which all statements part of the system can be satisfied), namely that the Lady is in the room behind the sign IX. Edit: I think it turns out that my assumption (2) can be weakened or isn't needed (but it was the way in which I initially thought the puzzle was meant to to be). 2nd edit: There's a mistake in my above reasoning (and I'll leave this message here as it was, in case someone wants to search and find which mistake it was, but I also mentioned which it was in my post below).

collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)

Posted: 5/30/2018 12:25 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

I did not follow all of your reasoning, but the lady cannot be in room IX. If the lady is in room IX, then the statement IX is true, but IX being true implies that IX has a tiger, so that's a contradiction!

Posted: 5/30/2018 1:06 PM

Quote

Aran_Jaeger

He/Him

Banned User

Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany

Yes, p4wn3r, that is true, and when I went to bed and kept thinking about this puzzle (since it was late and I stopped trying to resolve the entire constellation in which the system was), I realized that the Lady being behind the door IX leads to a contradiction, and then I kept thinking about what mistake I made, and found that my mistake was that the negation of VIII saying ''a Tiger is in the room behind VIII, and the room behind IX is empty'' doesn't need to be restricted to the case in which ''the room behind IX is empty'' is false, since it is also a possibility that instead only ''a Tiger is in the room behind VIII'' is false. And I anticipated that someone else in the meantime would notice and make a mention of it, but yeah now I went through this again, with an improved reasoning which should be correct. - - - Under the additional (to the assumptions and statements part of the presented logical system) given assumptions that (1) it holds true that any statement (that refers to the system) that can be expressed is either true, or false, or undecidable (by only the statements provided by the system, such that any case (true or false) would not lead to any contradiction via statements from the system), and (2) there exists exactly 1 door among these 9 doors that has a Tiger behind it, and (3) for any of these given 9 doors, there's either a Tiger behind it, or the Lady, or nothing (the room behind the door being empty), (4) and I think I possibly might also need the ''tertium non datur'', i.e. that the negation of a false statement is a true statement (and vice versa but I think this might already follow), (5) and it is assumed, that the logical system is such that no contradiction can be deduced, in the procedure of going through distinguished cases that are one after another separately investigated, one can quickly cut down the number of potential candidates for situations that describe what is behind every door as follows: First of all, one can notice that the statement of the sign of door VIII is the only statement (among all 9 door sign statements) that has no other door sign statement that refers to this door sign statement (since the sign of door I makes a statement about all door sign statements part of odd doors, V makes a statement about the even cases II and IV, and IX makes a statement about VI), and it makes a statement about itself, so this seems like a good candidate for a starting point for case distinctions. A: Now, if the Lady is in the room behind VIII, then by VIII (and its statement being true due to the Lady being in the room behind VIII), we get the statement that the Tiger is in the room behind VIII, which by (3) and (1) leads to a contradiction together with the assumption of this case distinction, so either the logical system is contradictory or the assumption is wrong. By (5), the assumption is wrong. The same applies analogously for sign IX. B: If we assume that a Tiger is in the room behind VIII, then by VIII (and its statement being false due to a Tiger being in the room behind VIII), we get the statement that the room behind VIII is either empty or the Lady is in there, which leads to a contradiction by (3) and (1) together with the assumption of this case distinction, so by (5) this assumption is wrong. Again, the same holds analogously for IX. Due to (3) together with the results from A and B, we can conclude that the rooms behind VIII and IX are empty. C: If we assume that the statement VIII is true, then a Tiger must be in the room behind VIII, which together with this room being empty as concluded before constitutes a contradiction by (3), so by (5) this assumption is wrong, and hence, VIII must be false. The same holds analogously for IX. (Since VIII is false, the negation of its statement doesn't lead to a contradiction, since the case that there's no Tiger in the room behind VIII is true, and the room behind IX being empty being true.) I and II make statements about themselves aswell: D: If the Lady is in the room behind II, then by II the room behind II is empty, which together with the assumption of this case distinction states a contradiction by (3), so by (5) this assumption must be false. So by (3) either a Tiger is in the room behind II and II is false (since a Tiger is in the room behind II), or the room behind II is empty and the statement II is true, since if it were false, then by II and (3), either the Lady or a Tiger would be in the room behind II which contradicts the assumption of this case distinction. E: If III is false and if we consider the case that V is true and VII is false (which is 1 of the 2 possible cases in which III is false, since by III either both, V and VII, are true or both are false, and for its negation it must either hold that V is true and VII is false, or V is false and VII is true), then by VII and it being a false statement, we get that the Lady must be in the room behind I together with the statement I being true (since the Lady is in the room behind I), and by V and it being a true statement by assumption, we get one of 2 possible scenarios: E1: IV is true (and II is false or undecidable), and by IV, I is false which together with the conclusions from E constitutes a contradiction by (5), and by (5) again, this assumption must be false given that the assumption from E holds. This leaves only 1 other case given that the assumption from E holds, namely the following: E2: II is true (and IV is either false or undecidable). Now we can choose that a Tiger is in the room behind IV (since IV is not undecidable because it must be false, since otherwise if it were true, then I would need to be false but is true due to the conclusions from E), since given that the assumption E holds, IV must be false anyways (and there's no further sign statement that refers to IV), and we can set all remaining sign statements separately to either true or false without any contradiction being possible to be concluded, as follows: If we set II as true and the room behind II being empty, then this case doesn't contradict the statement II (since the room behind II is empty), and it doesn't contradict the case E2 of the case E (in which III is false). The statement I doesn't contradict the case in which the Lady is in the room behind I. If we choose VI to be true and the room behind it to be empty, then this doesn't contradict the case assumption of E, and doesn't contradict that IX is false, since the case that VI is true does (at least) not contradict one of the cases in which IX is false (namely the case in which VI is true and no Tiger being in the room behind IX). We can also set the room behind III to be empty without causing any contradiction (since I and VI are the only statements refering to III) and the room behind V to be empty alongside its sign V being assumed (in E) to be true (so that we couldn't put a tiger into the room behind this sign V without causing a contradiction). Finally, we also can set the room behind VII to be empty without causing any contradictions, and the state in which the system is would now for this case E be completely described without being able to cause any contradiction: I: True, the Lady is in the room behind it. II: True, room behind it is empty. III: False, room behind it is empty. IV: False, a Tiger is in the room behind it. V: True, the room behind it is empty. VI: True, the room behind it is empty. VII: False, the room behind it is empty. VIII: False, the room behind it is empty. IX: False, the room behind it is empty. Now, under the assumption that (6) it is possible to uniquely determine behind which door the Lady is located, and given that in this 1 non-contradictory case the Lady is behind door 1, the location of the Lady must result to be behind door 1 in any case, since otherwise one couldn't uniquely deduce behind which door the Lady must be. So choosing door 1 is a safe bet for the prisoner to get the desired outcome.

collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)

Posted: 5/30/2018 1:43 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Room I is also an incorrect answer. You are still missing a key insight to solve the puzzle, which, rigorously, is a metapuzzle, because it involves reasoning about itself! We see that the king's hint makes the problem very peculiar. a) The puzzle, with only the signs, is unsolvable. b) The puzzle, with the signs, plus the information of whether room VIII is empty or not, is solvable. Remarkably, we must solve it without knowing what the king actually told the prisoner. How can this happen? What does it mean for a puzzle to be unsolvable? Solving the puzzle is finding the lady. Let us think about a brute-force way to solve this, if you had an extremely fast computer. One way to go about this is to do a search. You set all rooms, putting one lady and the rest either empty or with tigers. For the ones that are empty you specify whether the sentences are true or false. You check all sentences, together with their true and false values. If at least one of them fails, you discard the solution. If the puzzle is solvable, then after you test all possibilities, the only ones that remain have the lady in exactly one room. If the puzzle is unsolvable, as (a) says, two things can happen: i) No possibility satisfies all statements. ii) There are at least two possibilities with ladies in different rooms. But, as (b) says, with an additional constraint, the inside of room VIII, the puzzle is solvable. So, hypothesis (i) must be false. Essentially, this means that, if we take all possibilities that survived the sign test and impose one of the following: "Room VIII is empty" "Room VIII is not empty" Then we are able to cut the solutions, so that only those with a lady on a single room survive. How is that possible? Can you deduce the king's answer from this?

Posted: 5/30/2018 2:16 PM
(Edited: 5/30/2018 2:42 PM)

Quote

BrunoVisnadi

Editor, Skilled player (1344)

Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil

I'm not sure if I reasoned through this correctly, as it ended up being quite simple. I'm assuming the king said VIII is not empty, as I wouldn't be able to make progress otherwise: The Lady cant be in rooms 8 or 9. So 8 has an tiger. In order to 8 to be false, 9 must have a tiger. And in order to 9 to be false, 6 must be right. So we find 3 is wrong, thus (assuming "either" is not exclusive) 5 is wrong and 7 is right. It follows 2 and 4 are wrong, and 1 is right. The lady can't be in doors 3, 5 and 9, because their signs are wrong, and she cant be in door 1 due to sign 7. So she must be on door 7. If "either" is actually exclusive, this doesn't work.

My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3

Posted: 5/30/2018 2:40 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Correct! Here's a rigorous proof as to why the king said Room VIII is not empty. Suppose the king said Room VIII is empty. Then, the prisoner solved the problem and deduced that the lady was at room R1. Since the puzzle was unsolvable before, there must be at least one solution with a tiger on room 8 (since it can't have a lady) and the lady at a room R2, different from R1. Now, sign VIII is: VIII - This room contains a tiger and room IX is empty. If VIII contains a tiger, then this sentence is false, which means that room IX is not empty. Now pick the solution with a tiger at 8 and the lady at R2, and change room 8 so that it's empty, but keep its sentence false. Since room IX is still not empty, and room VIII no longer has a tiger, its sentence is indeed false. Because no other sign refers to the content of room 8, changing it from tiger to empty does not change the truth of other sentences. So, we have found a solution with the lady at R2 and room 8 empty. However, that contradicts the hypothesis that the puzzle is solvable after the king gives us the information. Therefore, the king must have replied that the room is not empty.

Posted: 5/30/2018 8:10 PM
(Edited: 5/30/2018 8:34 PM)

Quote

FractalFusion

Editor, Expert player (2073)

Joined: 6/15/2005
Posts: 3282

You can show that the hint is that room 8 is not empty as follows: Before the king gives the hint, the lady could be in room 1, since the sign on room 1 is true in this case, and the truth or falsehood of the other signs is irrelevant (the other rooms could be empty). Similarly, the lady could be in room 7. (You can also work out that the lady could be in rooms 3, 4, or 5, but only two cases are needed here.) So without the hint, the prisoner cannot determine where the lady is. If the hint was that room 8 is empty, then this gives no new information at all (no signs refer to the contents of room 8) and the prisoner could not have deduced the location of the lady. So the hint has to be that room 8 is not empty. Then (following BrunoVisnadi's post), the prisoner deduces that the lady is in room 7. (The prisoner can also deduce that rooms 1 and 6 are empty and that rooms 2, 8, 9 have tigers.) Edit: Changed the wording above. Actually you can tell that the sign on room 8 is false, but that can be deduced even without the hint.

Posted: 5/30/2018 8:31 PM

Quote

Aran_Jaeger

He/Him

Banned User

Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany

I'm going to respond in a more detailed manner about this topic later, since it appears that there's quite many different aspects to talk about that I cannot cover properly in a timely manner currently, but I wanted to point out a few things beforehand. First of all, there's quite some room for interpretation left for how the puzzle is meant to be understood (no Tiger being involved being a possibility?, exactly 1 Tiger being involved?, multiples Tigers possibly being involved?, ''either or'' meaning OR?, ''either or'' meaning XOR?,...), which can result in different versions of the puzzle that one can investigate here (and different initially given systems of axioms from which all deductions build up could also possibly lead to either different results or no conclusive results being possible to be deduced). Other observations are that the king's statement doesn't need to be true, and that it isn't specified from what (or rather: on the basis of what statement) the prisoner deduces the location of the Lady. Other than this, yes I made mistakes again in my 2nd post's approach at the part B regarding the negation of the conjunction of 2 separate statements, but the concluded constellation for me doesn't appear to lead to any contradictions (other than non-uniqueness), so in case the conclusion is false, can one identify where exactly a contradiction appears?

collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)

Posted: 5/30/2018 9:36 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

What I can tell you is that you are assuming this

Aran Jaeger wrote:

(1) it holds true that any statement (that refers to the system) that can be expressed is either true, or false, or undecidable

I know there are some logics where this holds, but this puzzle was thought in the context of classical logic, where this doesn't happen. The truth of a statement and its decidability are two different things. If you have a consistent system, you can have statements that are not reachable by inferences from its axioms. These statements can be true or false. If it is possible for us to assign a true or false value to it and keep consistency either way, we say the statement is "independent". As an example, take geometry without Euclid's fifth axiom. It's still a formal system. But if you want a system that's consistent (in the classical logic sense), you must decide whether the statement of Euclid's fifth axiom is true or false. If you say it's true you have Euclidean geometry. If it is false, you have elliptic or hyperbolic geometry (which one depends on what truth value you assign to other statements). The fact that you cannot reach Euclid's fifth axiom by the other four means that it's independent of them, not that it is undecidable. Nevertheless, if you are in a consistent system, it is either true or false, there's no third option. Decidability involves statements that are always true in any consistent formal system, but nevertheless cannot be proven from the axioms (and for any sufficiently expressive system, they will always exist, because of Gödel/Tarski theorems). The tricky thing about the puzzle is that it includes a statement about its own solvability, but in that sense, solvability should be treated in a classical sense. All statements are indeed either true or false, the question is whether their truth can be determined uniquely from the hints. I never thought about the problem when you allow a third truth value.

Posted: 5/30/2018 9:51 PM

Quote

Aran_Jaeger

He/Him

Banned User

Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany

Well, I think I didn't go into much detail there to explain what I meant, but no, I didn't mean ''decidability'' as a 3rd truth value, but rather exactly what you were refering to, namely if one can use existing statements from the system and combine them to get/reach out to an answer on if some given statement about the system is true or not, so basically ''if it matters to which of the 2 truth values we set this statement with respect to potential contradictions that might appear or not''. As an example, if we had 2 constellations that differ only in 1 part, namely that for some given room behind 1 of the 9 doors, there's a Tiger in it and in the other case the room is empty, but both cases satisfying all conditions asked for. Then if one would ask the question ''which of the 2 is the case?'', then one could not exclude either of the 2 cases, could not bring any of the 2 to a contradiction in order to exclude them, and hence the truth value of this statement could be either of the 2 without causing any problems, but without further specifying which ''model'' or ''completed system version'' one deals with (such that 1 of the 2 possible, irrelevant cases is determined), one cannot decide which is (or needs to be) the case. I guess in here,

(1) it holds true that any statement (that refers to the system) that can be expressed is either true, or false, or undecidable

one can interpret this such that it means that the truth value of the statement is either ''true'', ''false'', or ''undecidable'', but I just meant that either of these as statements about the given statement (''the statement is true'', ''the statement is false'', ''the statement is undecidable'') apply, but only 1 of them at a time/for a given statement (except that assuming an undecidable statement to be true or false will not allow to determine which is the case). I just wanted to explain that I didn't mean that every statement about the system necessarily needs to be provably true or provably false, and can be either of these without the system being capable to deduce which of the 2 it is.

collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)

Posted: 5/31/2018 1:02 AM

Quote

FractalFusion

Editor, Expert player (2073)

Joined: 6/15/2005
Posts: 3282

Aran Jaeger wrote:

no Tiger being involved being a possibility?, exactly 1 Tiger being involved?, multiples Tigers possibly being involved?

p4wn3r stated above:

p4wn3r wrote:

One of the doors has a lady behind and the others are either empty or have tigers behind them.

This is the clearest statement regarding the number of ladies (one) and the number of tigers (anything from zero to eight) that are involved in this problem, and this is what is intended. This problem was not meant for anyone to assume that there is exactly one tiger, which is not solvable in a classic manner. Now unfortunately p4wn3r had some strange wordings like "the door with the tiger" (should be "a door with a tiger" since there could be more than one, or none at all) and "If a lady is inside" (technically valid but clearly it is the lady, the only one in this problem), which may have led to this misunderstanding.

Aran Jaeger wrote:

''either or'' meaning OR?, ''either or'' meaning XOR?

The guideline I use in logic problems is this: If it says "A or B", where it is possible that both A and B could be true, I always assume OR (inclusive or) unless the problem specifically says otherwise (e.g. "but not both"). Whether it says "either" does not matter.

Aran Jaeger wrote:

Other observations are that the king's statement doesn't need to be true, and that it isn't specified from what (or rather: on the basis of what statement) the prisoner deduces the location of the Lady.

This would be overthinking the problem. I actually thought about these possibilities when trying to solve the problem; however, I quickly came to the conclusion that either the problem is fair (as in, it is solvable with classical logic) or else I'm not going to play along.

Posted: 5/31/2018 1:41 AM
(Edited: 5/31/2018 3:35 AM)

Quote

Aran_Jaeger

He/Him

Banned User

Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany

Well it was not clear to me at least. [quote p4wn3r] A prisoner is having a lady and tiger trial, but instead of purely chance, he can save himself using logic. There are nine doors. One of the doors has a lady behind and the others are either empty or have tigers behind them. If the prisoner enters the door with the tiger, he dies. If he enters an empty room, nothing happens, and if he enters the one with the lady, he marries her. The lady is a woman the prisoner loves, so he would prefer marrying her. [/quote] Do you see in here what might have confused me? I'll explain: This part [quote p4wn3r] One of the doors has a lady behind and the others are either empty or have tigers behind them. [/quote] depending on how it would be translated into formal expressions with parentheses, could be understood as ''if you pick any 1 of the 9 doors, then the room behind it is empty, (exclusive) or if you pick any 1 of the 9 doors, then it has at least 1 Tiger in the room behind it'', but it could also be understood such that for any given door the room behind it is either empty or exactly 1 Tiger is behind it, but it could also be understood such that for any given door the room behind it is either empty or ''tigers are behind it''. In particular though, it does not say ''One of the doors has a lady behind and the others are either empty or have a tiger behind them''. Now, since p4wn3r afterwards referred to ''the tiger'' later on, and since I assumed due to the many different meanings that the former statement could have had (and I thought maybe he just didn't want to go so much into detail there and quickly express a rough overview of the situation), that I should go with the latter description that made it seem like there exists only 1 Tiger (such as there alongside it also only existing 1 Lady), and because the latter description to me seemed to not allow for as many different interpretations, it felt more safe to me to go by that instead, but that was just my reasoning. I concluded from the use of ''the tiger'' instead of ''a tiger'' that multiple Tigers existing simultaneously was excluded, and from a Tiger being mentioned at all, together with the use of ''the tiger'', I was assuming that there was at least 1 Tiger involved. Also, I did not look up the link that p4wn3r provided, since I wanted to look into the puzzle the way p4wn3r presented it and also didn't want to risk seeing a solution to possibly already be presented on the page he linked. Edit: Regarding the way you handle or interpret ''A or B'', that is the same way I do it (except of the ''either'' part being relevant to me), and this way not being used in the presented puzzle formulation made me think with the ''either'', p4wn3r referred to the exclusive case. 2nd edit: It might be overthinking the problem if one observes that the final statement (coming from the king) is qualitatively different from all previous premises that were stated above/before, but from a consistency perspective, one might aswell have either stated all given statements as the initial ones or all in the format of a communication between the king and the prisoner to begin with, so I don't think it is so far fetched to think of the possibility that there could be a meaning for this separation between the 1 final statement from the previous rest. But yes, I guess since the puzzle is meant to be embedded into some story, a communication (between involved characters) could likely be expected as part of the puzzle, but then again, if one involves communication between characters, it might make about as much sense to tell the puzzle in this character communication format at the beginning aswell as at the end. 3rd edit: The thing is, there's so many different logics apart from the classical one (at least this page makes it look like it: https://en.wikipedia.org/wiki/List_of_Hilbert_systems ), that there might aswell be other ones which allow to get to conclusive valid (with respect to the given choice), ''fair'' problems. However, I agree that it seems far fetched to initially assume anything other than the classical one.

collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)

Forum Off topic some math challenges.

Forum

Off topic

some math challenges.