Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Tremane wrote:
Oh good now i can question this openly,
I saw some SMW:Hacks here already "The legend continues" or "Kaizo"
so my question was if the "Vip&Wall Series" would also be a good choice.
it has definitely unique mechanics and quirks.
I'm also not a judge, but I can anticipate you that a VIP run in the same category Mister was doing will pretty much definitely be accepted. Is very entertaining, the hack is very good and very different of the SMW stuff we have so far.
However, be aware that the run will be required to be optimal, and it's a fact that SMW's standard of optimization is higher than usual. If you want to get a SMW run published, I recommend taking a long time to learn the game's mechanics before by TASing other hacks, and then starting your VIP run.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
BrunoVisnadi wrote:
Also, The Riddler claims 4870798 is the only 7 digit number with no equations. Isn't (4/8)^(-7) + 0 = (7+9)*8 a solution, though?
Oh, now that you mentioned it, I don't think this solution considers negation of a single number to be a valid operation. Subtraction of two numbers, yes, but negation of one number, no.
Some people posted in the comments this other solution: 4*(8-7)*(0-7+9)=8.
I believe this one is valid, thus, we can in fact be sure every 14 digit long sequence has a equation.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Tub wrote:
The "solution" to last week's Riddler classic infuriates me. So is there a minimum length, where every number can be turned into an equation or not?
This is not a computational problem. Even showing 100% solvability for n says nothing about n+1. And you cannot compute all n.
I tried to find a strategy to turn any sufficiently long string into 0, turning the equation into (stuff) * 0 = (stuff) * 0 * (stuff), but with mere addition and substraction of single digits, that's not always possible up to n = 10.000 (I aborted the search there). I found no way to generalize a more complicated strategy. Did any of you have more luck?
I just realized that if you proof it always works for N, then it always works for every sequence with 2N digits or more.
We can split a sequence with 2N digits in 2 sequences with N digits. Each sequence with N digits starts with 'something' = 'something'. There might be more = symbols, but it doesn't mater. Just tweak it to ('something' - 'something') = ('something' - 'something'), and you have 0 = 0. For sequences with more than 2N digits, just multiply the remain numbers by the 0 you've got.
Since we know that every sequence with 7 digits has a valid equality, we can say for sure that for every sequence with N ≥ 14 digits there is a valid equality.
Edit: I also tried to find a way to sum up to 0 as you mentioned, but with only sum and subtraction it wouldn't work for any n. If the first digit is odd and the others are even, for instance, the sum would always be odd.
Edit2: I'm pretty sure if you test sums and subtracts of every sequence of digits contained by a sequence of size n, (that is, not necessarily summing or subtracting all of the digits) you will find an n that always gives you 0 somewhere.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
I agree with Tub this was a bad problem. Also, The Riddler claims 4870798 is the only 7 digit number with no equations. Isn't (4/8)^(-7) + 0 = (7+9)*8 a solution, though?
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
For item b), I found p = 3*sqrt(3)/(4*pi). I'm not sure if that's correct, as I've pretty much never studied calculus, but later on I'll describe how I got to this answer.
For item c), I hope there is a way to solve it without having to calculate the probabilities for score 2, 3, 4 and 5, and then averaging them.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Bobo the King wrote:
BrunoVisnadi wrote:
Bobo the King wrote:
Classic is a bit more difficult. I'm quite certain that the answer to the first question is five because six darts can be arranged in a regular hexagon, but since this will almost surely not happen, five is the effective answer. I'm going to be really pissed if the answer is six.
I didn't understand, why do you think the answer is 5 instead of 6?? The Riddler explicitly says that the darts can hit the very edge of the board.
Well shucks, why not 7 then? Both 6 and 7 effectively have probability zero of occurring because they demand that coordinates chosen from a continuous distribution land on specific points. But point taken-- since the Riddler is going out of his way to point that out that darts can land on the edge, you're very likely correct. I nevertheless get annoyed when people try to make a distinction between "less than" and "less than or equal to" under a continuous probability distribution.If the official answer posted Friday is indeed five, I'll add it to to my list of grievances against how the Riddler presents these puzzles.
You are correct, I did realize you can get 7 darts, but I thought the score would be 6 because of it is equal to 'n - 1'. However as the nth dart is the dart you miss, in fact, the answer must be 7, not 6.
Indeed the chance of that happening is 0, but 0 is not quite the same as impossible in these situations.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Bobo the King wrote:
Classic is a bit more difficult. I'm quite certain that the answer to the first question is five because six darts can be arranged in a regular hexagon, but since this will almost surely not happen, five is the effective answer. I'm going to be really pissed if the answer is six.
I didn't understand, why do you think the answer is 5 instead of 6?? The Riddler explicitly says that the darts can hit the very edge of the board.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
JXQ wrote:
BrunoVisnadi wrote:
for larger values of n, this pattern doesn't work.
As far as I can tell, it does work. By drawing a series of n-2 parallel lines across the grid that cause the pierced squares to form a pattern of 2 in one direction (either x dimension or y dimension), and 1 in the other dimensional direction, etc., you can fill everything but 4 squares in n-2 lines, and one more line can cover those last four squares. Here's an example for 6x6 using 5 piercing lines:
Indeed, with your method it does work. Mine was slightly different and wouldn't work for larger values of n.
JXQ wrote:
For example, a 3x3x3 grid of cubes could be solved with 6 piercing lines, by using the solution above for each 2D slice of the 3D grid. But none of these 6 lines are optimal because they are all parallel with respect to the new dimension. Could more optimal lines allow for a 5-line solution?
I could find a 5-line solution, but the lines still look pretty 'unoptimal'. It's hard to visualize it in 3d, but I think there might be a 4 line solution.
EDIT: I think I could find a proof that there is no 4-line solution. Pretty sure 5 line is the minimum, then, unless I made some big mistake.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
thatguy wrote:
JXQ: I haven't been able to find a way to cover every cell in an nxn grid with n-1 straight lines, but it's pretty easy to see that you can cover every cell but one. Just start with the configuration you mentioned, each line piercing a single column of squares. Now tilt the first line slightly so it pierces the top square in the second column, then tilt the second line a little more so it misses the top square in its own column, but pierces the top two squares of the third column, and tilt each line progressively more, until the (n-1)th line covers n-1 squares in the nth column - ie, all but the bottom corner.
Trying to pierce all the squares with diagonal lines (by which I mean, ones at a perfect 45-degree angle) also leaves one square. You can do this either with parallel diagonal lines or two sets of diagonals which are mutually perpendicular and are cleverly interwoven - but every time, one square is left behind.
I'm not sure it's possible. I'm pretty certain that if an example did exist, it would have lines which crossed each other - but of course, this introduces inefficiencies to the problem, as some squares would necessarily be pierced more than once.
I think this is a valid pattern of covering an nxn grid with n-1 lines. But I suspect for larger n it might be possible to do it with less than n-1 lines.
Edit: for larger values of n, this pattern doesn't work.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
OmnipotentEntity wrote:
If you take the harmonic series and remove only the terms that contain a 9 will the series converge or diverge? Prove it.
The series converges. Proof: Among all the positive integers that don't have the digit 9, there are 8 1-digit numbers, 8*9 2-digit numbers, 8*9*9 3-digit numbers, ... , 8*9k-1 k-digit numbers, and so on. Therefore the series is bounded above by
8(1)+8*9(1/10)+8*9*9(1/100)+...+8*9k-1(1/10k-1)+...
= 8(1+9/10+(9/10)2+...+(9/10)k-1+...)
= 8(1/(1-9/10)) = 8*10 = 80,
and the summation terms are all positive and go to 0. Therefore it converges.
Same argument if you exclude terms with the digit j, j something other than 9. (For j=0, the 8's in the proof above become 9's.)
It's interesting to think about it, as I'm pretty sure if you remove any sequence of numbers, it will also converge. I wonder what the limit will be if, for instance, we remove only the terms that have a ''1234567890''.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
I did criticize the quality of the game during the DTC, but this vast amount of glitches actually made this TAS awesome to watch. This was very entertaining and suitable to star tier IMO. Technical quality also seems excellent - Yes vote.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
I also found 1.635 for the optimizaition problem, but I'm not convinced it's impossible to improve it. Would it be possible to proof such a solution is optimal, without heavy computational power reliance?
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
thatguy wrote:
Is it the case, then, that the sine of any rational number (or, since we really ought to be talking in radians, a rational multiple of pi) is an algebraic number? And if so, is there an algorithm that can calculate it?
Sin of pi times a rational is always algebraic indeed, due to the formula sin(m+n) = sin(m)cos(n) + sin(n)cos(m). It allows you write sin of (pi/b) as the root of a (b-1)th degree polynomial, and then to sum it to itself a times to get a polynomial of degree b-1 with one root equal to sin(a*pi/b)
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
arandomgameTASer wrote:
K I actually read the post since reading is a very easy skill. I think he makes a lot of good points, and more importantly I think it provides enough evidence for the run to be rejudged.
So, calling for that.
No, he doesn't make a lot of good points. I might have missed a paragraph or 2, but I read almost the whole thing. There might be a few pertinent disagreements on Nach's thoughts, but at the end of the day it's a mater of opinion and how you interpret the facts. 90% of what he wrote though is wrong, previously replied or cheap dramatic offenses to Nach. And he tried to make a martyr of himself at the end which was pretty dumb.
Can we please respect the final decision and accept this submission was rejected, as HappyLee kindly did long ago? If you think PAL games should be judged differently go to the proper thread and talk about it. If you only care about this submission though, please show some maturity. As I said earlier, you can disagree with the decision, but you can't call it absurd. There are enough argument supporting it.
Disagreeing which a judge decision is normal. I'm sure if you look into the last few hundred decisions you will probably disagree with a few. What makes this submission particularly problematic is not that the decision is ''more absurd'', but the submission is 'more relevant', so it attracts much more discussion. There is no reasonable reason to rejudge this, considering that Nach worked on it for a month and 4 other judges were ok with the rejection. Please, get over it.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
To finish the Riddler question, BrunoVisnadi indeed guessed correctly on a previous post that the strategy is improvable to 7/8. This is actually a coding theory problem in disguise:
Let 0=white, 1=black and assign an order to the 7 friends. Map each of the 27=128 possible hat distributions to a binary sequence of 0's and 1's of length 7, e.g. 0110101. This problem then becomes: can at least 1 of the 7 friends correctly guess the sequence given that each one sees every symbol (0 or 1) except their own?
Consider a particular sequence (say 0110101). Say we take a chance and assume that 0110101 is not the sequence. If 0110101 is the actual sequence, then we lose. However, if 0110101 is not the sequence, but 1110101 is, then we can win; friend 1 sees ?110101 and so correctly guesses that it is 1110101. Likewise, we can correctly guess 0010101, 0100101, ..., 0110100, that is, any of the 7 sequences that are one symbol away from 0110101. So for 1 losing sequence, we can generate up to 7 winners (maximum winning rate is thus 7/8).
The strategy is thus: Choose a subset S of the 128 binary sequences, such that the number of sequences that are not in S and are one away from an element of S (and thus sure winners) is maximized. It turns out for n=7 that there is such an S (of size 128/8=16) that exactly achieves the maximum; that is, every element not in S is one away from exactly one element in S. For example:
S={0000000,1101000,0110100,0011010,0001101,1000110,0100011,1010001, 1111111,0010111,1001011,1100101,1110010,0111001,1011100,0101110}
(I.e. all 0's and 1101000 and all its cycles, and then all their complements.)
The strategy: For each friend, if one of the two possibilities is an element of S, guess the one which is not in S; otherwise pass. The strategy wins if the sequence is not in S and loses if the sequence is in S. Win rate: 7/8.
S is what is known as a Hamming code of 7 bits. The Hamming codes are the "optimal" solutions for the S in the strategy above; they occur whenever n=2N-1 and the win rate is (2N-1)/2N. E.g. for n=3, S={000,111}; this is the "guess the other color if you see two hats of the same color and pass otherwise" strategy already described in one of the previous posts and has a win rate of 3/4.
This answer reminded some of my attempts to solve the problem 1 in this Quora reply: https://www.quora.com/What-is-a-brain-teaser-that-is-very-short-and-extremely-hard-for-adults/answer/Nikhil-Bhavar-1
I didn't read its answer yet, but I believe there will be some similarity. I remember trying to find a function so that, for each 64 digits long binary numbers, each number that differs in 1 from that number gets mapped to a different natural between 1 and 64. It's not the same thing you did with 7 digits binary numbers, though.
Also, is there an algorithm to find the 2^(2^N - N - 1) numbers that cover every binary number with 2^N - 1 digits, for higher values of N?
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
It seems to me that in a few levels there were sections done faster by HappyLee and sections done faster by MrWint. Combining them, could a frame rule be beaten?
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
Warp wrote:
Bobo the King wrote:
sin(18) = sqrt(3 - sqrt(5))/8
That doesn't seem to be correct. Note that sin(18°) is approximately 0.309, while your result is approximately 0.109.
What Bobo the King clearly meant was sqrt((3 - sqrt(5))/8).
When I get as the result of a problem a square root inside a square root, I always try to get a equivalent, cleaner expression.
sqrt((3 - sqrt(5))/8) squared gives us, obviously, (3 - sqrt(5))/8. So what else gives this number when squared?
(a*sqrt(b) + c*sqrt(d))^2 = a²b + c²d + 2ac(sqrt(bd)). So let b = 1 and d = 5
a² + 5c² + 2ac*sqrt(5) = (3 - sqrt(5))/8
a² + 5c² = 3/8 and 2ac = 1/8. If we write c as 1/16a in the first expression, we find:
a² + 5/(256a²) = 3/8. This is expected to have 4 solutions for a. And they are +- 1/4 and +- sqrt(5)/4. If a = 1/4 in 2ac = 1/8, then c = 1/4.
That is, we can write sin(18º) as (1 + sqrt(5))/4, as this number squared also gives us (3 - sqrt(5))/8
EDIT: I messed it up, as Warp pointed out. We must have a = -1/4, which gives us sin(18º) = (sqrt(5) - 1)/4
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Arcorann wrote:
Regarding the Riddler, I've seen the problem before; though I didn't immediately remember the optimal solution I was able to reconstruct it surprisingly quickly.
For some general comments, I will point out that the solution described for 3 people implies a lower bound of 75% for 7 people (simply ignore the last four people by making them all pass), which is not optimal. And yes, the value 2N-1 is special for this problem.
Thanks for this observation. I could get slightly better than 75%: 25/32, or 78.125%. I'm pretty sure it can be improved further, perhaps to exactly 7 /8.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Tub wrote:
Ok, apparently this isn't spoiler-free any longer. Let's talk business.
Bruno got the same chance as I did, but his rules are a lot more complicated.
My strategy is: if you see exactly 4 or 6 hats of the same color, guess the other color. Otherwise, pass.
This will win on any 1/6 or 3/4 split, but is guaranteed to lose on 0/7 or 2/5. Works out to 84/128 ~ 65.6%, too.
Bobo the King wrote:
Maybe we can come up with a Bayesian analysis of this problem along the lines of P(my hat is white|I see six black hats) etc.
That P is 0.5, no matter what you do. That path does not lead to a solution.
Well, I figured it was ok to spoil a strategy as other people had already done it with their interpretation of the problem.
Your solution is much simpler indeed. For some reason I made mine in a way that only 1 person would guess in each winning scenario, which now I see, is unnecessary. Also, it's interesting to see that the trade off of ''2/7 of the 2-5 scenarios and 1/7 of 1-6 scenarios'' for ''all 1-6 scenarios and no 2-5 scenarios'' was completely even.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Bobo the King wrote:
Okay, to be explicit about what has been pointed out above, the players are not allowed to communicate during the guessing phase except through their choice of guess/pass. This is suddenly more interesting.
I don't think this kind of communication is allowed. And it is still interesting, because it is possible to get higher chances without it:
First, lets name the friends: 1, 2, 3, 4, 5, 6 and 7.
Strategy:
1) If you see exactly 3 hats of each color, pass.
2) If you see exactly 2 hats of a specific color, and your number is bigger than the number of these 2 people, guess you have this color. If your number is smaller, pass.
This guarantees we will win every 3/4 scenario - which has (35)/(2^6), or more than 54% chance of happening!
In a 2/5 scenario, we will certainly lose if person 7 is on the 'team' with 5 hats, due to rule 2). But we can win otherwise. Consider this rule:
3) If you see exactly one hat of a specific color, and you aren't number 7, pass. If you are number 7, guess you have that color.
Now we won every 2/5 situation in which person 7 is in the 'team' with 2 hats.
Lastly, in a 1/6 scenario, we will lose if 7 is in the team with 6 hats. But if he isn't, we will win, because whoever is in this team will pass, and we can have this rule:
4) If you only see hats of one color, guess you have the other color.
In a 0/7 scenario, we always lose.
So this gives us the following winning chance:
(35)/(2^6) + (3)/(2^5) + 1/(2^6) = 21/2^5 or 65.625%
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
If there were 3 people, there is a strategy to get 75% chance.
If you see 2 hats of different colors, pass.
If you see 2 hats of the same color, guess you have the other color.
For 7 people there is a strategy built with the same idea, but it's more complex. I think I'm getting slightly above 50% chances, but they are surely not optimal.
Editor, Experienced Forum User, Published Author, Skilled player
(1411)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Masterjun wrote:
Well, I'm not really good at these kinds of things, but wouldn't this strategy be higher than 50%:
I'll start. If I see the same number of black and white hats I'll pass, otherwise I'll just randomly guess.
So if I pass, the others will immediately know what color they have and win the game.
Edit: Maybe this kind of strategy can be extended to include the idea of time. For example:
If anyone sees the same number of black and white hats, pass immediately. If nobody passes in the first 10 seconds, [somethingsomething].
Edit2: Actually, the time before a chosen person passes can be used to give information, such as a binary encoding of the hats you see in some order you decided on beforehand. That would make this 100% I think. :P
I think this doesn't follow the riddle's rules. ''you make your guesses or passes in separate soundproof rooms''. So the other people won't know if you passed or not.
EDIT: I think I can see a way of getting a better chance than 50%. Working on it.
