Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Apr 16, 2014 8:52 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 129 posts ]  Go to page Previous  1, 2, 3
Author Message
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Tue Nov 09, 2010 4:25 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Jorbs3210 wrote:
Is it possible to cut an obtuse triangle (a triangle with one obtuse angle) into smaller triangles, all of them acute? If such a dissection can be done, what is the smallest number of acute triangles into which any obtuse triangle can be dissected?

Two - just cut through the obtuse angle, but you'd have to cut through the opposite side at 90 degrees. Does a right-angled triangle count as acute?

Otherwise it's not possible: you always end up with at least one more obtuse or right-angled triangle and you're back to square 1, no matter how you cut it.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Last edited by KelvinS on Tue Nov 09, 2010 5:00 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Tue Nov 09, 2010 4:43 pm 
Offline
User avatar

Joined: Sun Jun 13, 2010 1:00 am
Location: Colorado
Jorbs3210 wrote:
Is it possible to cut an obtuse triangle (a triangle with one obtuse angle) into smaller triangles, all of them acute? If such a dissection can be done, what is the smallest number of acute triangles into which any obtuse triangle can be dissected?

3?

_________________
My Shapeways Shop
My YouTube Videos
My Museum Puzzles


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Wed Nov 10, 2010 7:43 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
No, and no. And it is possible.

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Fri Nov 12, 2010 7:05 am 
Offline
User avatar

Joined: Fri Nov 05, 2010 2:20 am
Location: Wherever
PuzzleMaster6262 wrote:
Sjoerd wrote:
Can you come up with a word, thing, or number that does not lead to 4?


3.1415926535897932384626433...

Or what about $, €, £, and ¥? (the symbols, not what they represent :lol: )

In my opinion, everything ends with g.



lets see.... THREE POINT ONE FOUR ONE FIVE............ has infinite letters

infinity/infinite has 8 letters

eight has five letters

five has four letters!!!!!!!!!!!!!

_________________
A budding puzzle designer!

Check out my Shapeways shop!


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Fri Nov 12, 2010 7:36 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Jorbs3210 wrote:
Is it possible to cut an obtuse triangle (a triangle with one obtuse angle) into smaller triangles, all of them acute? If such a dissection can be done, what is the smallest number of acute triangles into which any obtuse triangle can be dissected?

OK, got it!! The answer's 7:
Attachment:
Triangle.jpg
Triangle.jpg [ 19.64 KiB | Viewed 2172 times ]

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Sat Nov 13, 2010 5:19 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
DINGDINGDINGDINGDING!!! Correct!

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Mon Feb 14, 2011 12:10 am 
Offline
User avatar

Joined: Mon Feb 16, 2009 6:43 am
Location: Italy
I think I've the solution to the Blue Eyes enigma.
It will be hard for me to explain it in english in a comprehensible way, I hope you'll understand my explanation.


We assume that all people can do perfect logical deductions. We also assume that the color of the eyes of the guru isn't important, so that he can't leave.
Let's start analysing 3 simple cases.

Case 1: Assume that there are only 3 people: 1 with brown eyes, 1 with blue eyes and the guru (from now on I will only say Brown and Blue, omitting "with - eyes").
The first day the people will watch each other in the eyes, so Brown will see 1 Blue, while Blue will only see 1 Brown and no other Blue. At noon the guru will say that there's someone (not a specific number) with blue eyes. The only Blue will logically leave during the night, while the only Brown will stay. Why?
The only Brown obviously doesn't know what's the color of his own eyes, but he will stay at least another day because he saw 1 Blue. The deduction of Brown on the first day when he sees 1 Blue is:
1) if Blue leaves the first day, that means that Blue himself saw that Brown has brown eyes, and knowing that there's at least one person with blue eyes, Blue deduces that he himself has blue eyes, and he must leave on the first night.
2) if Blue is still on the island the second day, that means that, also if he has blue eyes, he himself saw another person with blue eyes (remember that we're assuming that there are only 2 people a part the guru: Brown and Blue himself), and he did himself the deduction of point 1, so he expects that the other person with blue eyes leaves the first day, and Blue himself stay until the second day.
Since in this Case we're assuming that there's 1 only blue, the first deduction is valid, the only Brown will stay on the island and the only Blue will leave on the first day.

Case 2: 3 people: 2 with blue eyes and the guru. No brown eyes.
According to the deduction of point 2 of case 1, both the blue eyes will wait until the second days, because they will both expect that the other one will leave on the first day, thinking that the other is the only with blue eyes. Since the second day they still are both on the island, they logically deduce that they both have blue eyes, and they leave during the second night.
Note that it's unimportant when the guru says that there are people with blue eyes, because since the people can see each other, and they're both Blue, they all know that there's at least one Blue.

Case 3: 4 people: 3 with blue eyes (I'll call them X, Y and Z) and the guru. No brown eyes.
The 3 people watch each other, and everyone of them sees other 2 Blue.
They will exactly do the same deductions of Case 1: X sees 2 Blues, and he assume to have himself brown eyes. He will do the same deductions that a person that watch the situation from outside (like us) would do seeing 2 Blue and 1 Brown. This deduction is the same of Case 1 point 2. X thinks that Y will think that there's one only Blue (Z), and that Z himself will think that there's one only Blue (Y), so they will both wait until day 2, since they both expects that the other will leave on night 1. According to what X thinks, on day 2, Y and Z should realize that they both have blue eyes, and they should both leave on night 2. This would happen if there really was 1 Brown, or any other number of Brown... If X was Brown, both X and Y would leave on night 2, and X's deduction would be correct. But since X himself has blue eyes, the other 2 will wait until the third day, because each of them, seeing other 2 Blue, will do the same deduction of X, and will wait until day 3.
On day 3, each of them realize that they all have blue eyes, and they all leave on night 3.

This reasoning is valid for every number of Blue and Brown. Try it if you want.

Conclusions:
-All the Blue always leave the island, independently of their number.
-They all leave the island during the same night.
-The number of the night during which all Blue leave is decided by the number of Blue on the island.

The original enigma says about 100 people with blue eyes, so the solution is that all the 100 Blue leave the island on the 100th night.

Note that the presence of the guru is not strictly necessary. It's necessary only when there is 1 only Blue, because in that extreme case the only Blue can't know that he himself is Blue if the guru doesn't say it.
In all the other cases, since there are at least 2 Blue, they can see each other and can do their deductions.

_________________
Image Image Image


Last edited by Pepsis on Mon Feb 14, 2011 7:04 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Mon Feb 14, 2011 6:15 pm 
Offline
User avatar

Joined: Tue Dec 21, 2010 12:18 pm
Triangle with sides a, b, and c

Area=Perimeter

a, b, and c are each whole numbers.

How many triangles are there for this criteria and what are their a, b, and c values for each.

I know of two thus far.


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Mon Feb 14, 2011 7:30 pm 
Offline
User avatar

Joined: Wed Apr 01, 2009 2:59 pm
Cubysognathus wrote:
Triangle with sides a, b, and c

Area=Perimeter

a, b, and c are each whole numbers.

How many triangles are there for this criteria and what are their a, b, and c values for each.

I know of two thus far.


Neat! By Heron's formula we want (a+b+c)(-a+b+c)(a-b+c)(a+b-c)=16(a+b+c)^2.

Wolfram Alpha says 38 integer solutions -- but as far as I can tell all of them have zeros or negatives for at least one variable... Not sure what I'm doing wrong.


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Mon Feb 14, 2011 7:48 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
Cubysognathus wrote:
Triangle with sides a, b, and c

Area=Perimeter

a, b, and c are each whole numbers.

How many triangles are there for this criteria and what are their a, b, and c values for each.

I know of two thus far.

What a fun question. I wrote a quick python script to check all a,b,c in [1,1000] and came up with these 5 solutions
5 12 13
6 8 10
6 25 29
7 15 20
9 10 17


@ Iranon
Cool idea to use wolfram alpha, but none of my solutions seem to be in their list.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Mon Feb 14, 2011 8:31 pm 
Offline
User avatar

Joined: Tue Feb 16, 2010 1:50 pm
Pepsis wrote:
I think I've the solution to the Blue Eyes enigma.

This reminds me of the Cheating Husbands Puzzle.

_________________
My Mods on Flickr


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Mon Feb 14, 2011 9:07 pm 
Offline
User avatar

Joined: Wed Apr 01, 2009 2:59 pm
GuiltyBystander wrote:
Cubysognathus wrote:
Triangle with sides a, b, and c

Area=Perimeter

a, b, and c are each whole numbers.

How many triangles are there for this criteria and what are their a, b, and c values for each.

I know of two thus far.

What a fun question. I wrote a quick python script to check all a,b,c in [1,1000] and came up with these 5 solutions
5 12 13
6 8 10
6 25 29
7 15 20
9 10 17


@ Iranon
Cool idea to use wolfram alpha, but none of my solutions seem to be in their list.


Awesome. Yeah, those 5 are all of them.
Without trying to expand Heron's formula so much, 4s=(s-a)(s-b)(s-c), where s=(a+b+c)/2. Let (x, y, z) be (s-a, s-b, s-c) respectively. Note that x+y+z=s. Then we have 4(x+y+z)=xyz, and without loss of generality x<=y<=z.

If x=1, 4(1+y+z)=yz after some factoring is equivalent to (y-4)(z-4)=20, so we get solutions (x,y,z)=(1,5,24), (1,6,14), (1,8,9).

If x=2, 4(2+y+z)=2yz after some factoring is equivalent to (y-2)(z-2)=8, so we get solutions (x,y,z)=(2,3,10), (2,4,6).

If x=3, 4(3+y+z)=3yz after some factoring is equivalent to (3y-4)(3z-4)=52, which gives no new integer solutions, just (3,5/3,56/3), (3,2,10), (3,8/3,17/3).

If x>=4, we don't get any integer solutions at all.

So altogether we have that (s-a, s-b, s-c) can be (1,5,24), (1,6,14), (1,8,9), (2,3,10), or (2,4,6).
Respectively, these translate to (a,b,c) = (6,25,29), (7,15,20), (9,10,17), (5,12,13), or (6,8,10).

Hooray!


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Tue Feb 15, 2011 9:06 am 
Offline
User avatar

Joined: Mon Feb 16, 2009 6:43 am
Location: Italy
roger wrote:
Pepsis wrote:
I think I've the solution to the Blue Eyes enigma.

This reminds me of the Cheating Husbands Puzzle.

Yes, it's similar, and the answer to this should be 10 men, because the reasoning is the same of the Blue Eyes riddle.

_________________
Image Image Image


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Sat Feb 26, 2011 2:51 pm 
Offline
User avatar

Joined: Tue Dec 21, 2010 12:18 pm
Great job on the Triangles problem (Area=Perimeter)
I thought there were 6 triangles, but it was only a hunch.

New problem:
9 people of ethnicities leave a bar and make their way home.
3 Chinese, 2 Irish, 2 German, and 2 French.
Because they're drunk they randomly go home to different homes. No more
than one person per home. Out of all possible outcomes what is the average
number that will be at a home that matches their ethnicity. For instance the first
chinese person has 3 houses he can randomly go home to that matches his
ethnicity.


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Sat Feb 26, 2011 4:01 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
Can't think of any intuitive solution. Here's the brute force count. "If you only have a hammer, you tend to see every problem as a nail"
0 27,072
1 79,056
2 103,680
3 84,000
4 44,352
5 19,008
6 4,224
7 1,440
8 0
9 48

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Sat Feb 26, 2011 5:00 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
GuiltyBystander wrote:
Can't think of any intuitive solution.
Me either. I haven't done any expected value problems like this for a couple of years so I'm rusty. I would have done the same count as you.

So lets modify the question so we can't brute force it.

Suppose you have (N * (N + 1)) / 2 colored marbles of N unique colors as well as N unique colored bins. You have N copies of the Nth colored marble and the Nth colored bin fits exactly N marbles.

What is the expected value of the number of marbles in bins that match their color if the marbles are randomly inserted into the N bins?

For a numerical answer, lets take N to be 100. I'd prefer the answer expressed in terms of N :P


EDIT: fixed formula from ((N * (N - 1)) / 2) to ((N * (N + 1)) / 2) which properly counts the number of total marbles needed to fill all buckets. I have also solved the problem. The answer is exceptionally simple but arriving at it was quite hard (for me).

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Sun Feb 27, 2011 5:34 am 
Offline
User avatar

Joined: Wed Mar 15, 2000 9:11 pm
Location: Delft, the Netherlands
bmenrigh wrote:
So lets modify the question so we can't brute force it.

Suppose you have (N * (N + 1)) / 2 colored marbles of N unique colors as well as N unique colored bins. You have N copies of the Nth colored marble and the Nth colored bin fits exactly N marbles.

What is the expected value of the number of marbles in bins that match their color if the marbles are randomly inserted into the N bins?

For a numerical answer, lets take N to be 100. I'd prefer the answer expressed in terms of N :P


EDIT: fixed formula from ((N * (N - 1)) / 2) to ((N * (N + 1)) / 2) which properly counts the number of total marbles needed to fill all buckets. I have also solved the problem. The answer is exceptionally simple but arriving at it was quite hard (for me).



Is it (2N+1)/3 ?

There are L = N(N+1)/2 locations for the balls.
Each ball of colour k therefore has probability k / L to be in a matching bin.
It follows from the Linearity of Expectation that the k balls of colour k contribute k(k/L) to the expected number of correctly matched balls.
Summing over all k, the number of expected matches is (1^2 + 2^2 + ... + N^2) / L.
Using the formula for Square Pyramidal Numbers gives the answer ( N(N+1)(2N+1)/6 ) / ( N(N+1)/2 ) = (2N+1)/3


Similarly, the people in homes problem has an expected (3^2 + 2^2 + 2^2 + 2^2)/9 = 7/3 people in homes matching their ethnicity, which matches the average of GuiltyBystander's brute forced numbers.

_________________
Jaap

Jaap's Puzzle Page:
http://www.jaapsch.net/puzzles/


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Sun Feb 27, 2011 7:21 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
jaap wrote:
Is it (2N+1)/3 ?

There are L = N(N+1)/2 locations for the balls.
Each ball of colour k therefore has probability k / L to be in a matching bin.
It follows from the Linearity of Expectation that the k balls of colour k contribute k(k/L) to the expected number of correctly matched balls.
Summing over all k, the number of expected matches is (1^2 + 2^2 + ... + N^2) / L.
Using the formula for Square Pyramidal Numbers gives the answer ( N(N+1)(2N+1)/6 ) / ( N(N+1)/2 ) = (2N+1)/3


Similarly, the people in homes problem has an expected (3^2 + 2^2 + 2^2 + 2^2)/9 = 7/3 people in homes matching their ethnicity, which matches the average of GuiltyBystander's brute forced numbers.
Excellent! That's what I got too. I wasn't aware of of a formula for Square Pyramidal numbers so this was ugly for me (plus I was working with binomial coefficients such as "3 choose 2"). I got to an inductive step and spent a long time before I resolved it. When I got ((2 * N) + 1) / 3 I was pretty sure it was correct but I wrote a Monte Carlo simulation to be sure.

This problem was hard for me but it looks like you solved it with ease. Great job.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Sun Feb 27, 2011 9:44 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
bmenrigh wrote:
So lets modify the question so we can't brute force it....
Excellent way to one up the problem.

jaap wrote:
Is it (2N+1)/3 ?
Using a brute force hammer to sample millions of examples, my hammer seems to agree for n < 20. Didn't try it beyond that. I need to brush up on my probability formulas. I thought the math would have been more complicated than that.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Sun Feb 27, 2011 10:11 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
GuiltyBystander wrote:
bmenrigh wrote:
So lets modify the question so we can't brute force it....
Excellent way to one up the problem.
I'm not sure what you mean here but hopefully I didn't offend anyone :?

GuiltyBystander wrote:
Using a brute force hammer to sample millions of examples, my hammer seems to agree for n < 20. Didn't try it beyond that. I need to brush up on my probability formulas. I thought the math would have been more complicated than that.
I'm curious how you tackled the problem. I found ~10000 trials to be more than adequate even when N=100. Did you shuffle a list using something like Fisher–Yates algorithm or did you actually bin elements? Here is my simulation:
Code:
#!/usr/bin/perl

use strict;
use warnings;
use List::Util qw(shuffle);

my $N = 100;
my $TRIALS = 10000;

my @ORIG;
for (my $j = 1; $j <= $N; $j++) {
    push @ORIG, ($j) x $j;
}
my $T = scalar @ORIG;

my $total = 0;
for (my $i = 0; $i < $TRIALS; $i++) {
     my @marbles = shuffle @ORIG;

     for (my $j = 0; $j < $T; $j++) {
         if ($marbles[$j] == $ORIG[$j]) {
             $total++;
         }
     }
}

my $X = (($total + 0.0) / ($TRIALS + 0.0));
my $EXP = ((2 * $N) + 1.0) / 3.0;
printf "%d trials of N=%d yielded x=%.04f exp=%.04f (%.02f%% percent error)\n",
    $TRIALS, $N, $X, $EXP, ((($X - $EXP) / $EXP) * 100);

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Mon Feb 28, 2011 2:41 am 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
bmenrigh wrote:
GuiltyBystander wrote:
bmenrigh wrote:
So lets modify the question so we can't brute force it....
Excellent way to one up the problem.
I'm not sure what you mean here but hopefully I didn't offend anyone :?
I'm saying it's a great way to generalize the problem. It takes it to the next step. It's a good thing. I'm not trying to "dis" anyone or anything.

bmenrigh wrote:
GuiltyBystander wrote:
Using a brute force hammer to sample millions of examples, my hammer seems to agree for n < 20. Didn't try it beyond that. I need to brush up on my probability formulas. I thought the math would have been more complicated than that.
I'm curious how you tackled the problem. I found ~10000 trials to be more than adequate even when N=100. Did you shuffle a list using something like Fisher–Yates algorithm or did you actually bin elements? Here is my simulation:
I shuffled using python's random.shuffle. Running it again for n=100 seems to work just fine too. I think you need more than 10k trials though. Here's what my code outputs when I ran it for n = 100; (got coding on the brain so I feel instinctively ending sentences with semicolons :P)
Code:
60            7265
61            7873
62            8399
63            9078
64            9638
65           10000
66            9914
67            9895
68            9851
69            9669
70            9142
The answer should be (2*100+1)/3 = 67 but it's not. Total permutations tested was 203804.
I tried again a few more times with a cutoff of 1000 and got these results.
(best, total perms)
(66, 19815)
(67, 19939)
(67, 19898)
(67, 19747)
(65, 19483)

I was just lazy and didn't want to see if the pattern held for n = [1,100]. That's why I stopped at n = 20. For small n, I was doing millions of samples. If something is worth doing, it's worth overdoing. Then as I incremented n, I saw it was taking longer and longer so I did fewer and fewer samples. I ended up stopping when the most popular answer had 10k "votes" I did this mainly so I could pick it out easily from the output. Here's my code
Code:
import random

n = 20

house = []
for i in range(n):
    house = house + [i]*(i+1)

count = [0]*(len(house)+1)

t = range(len(house))

#while sum(count)<1000000:
while max(count)<10000:
    random.shuffle(t)
   
    r = 0
    for i,j in enumerate(t):
        if house[i]==house[j]:
            r = r + 1
    count[r] = count[r] + 1   

    if sum(count)%10000==0:
        print "%6d%15d" % (sum(count), max(count))
       
print '-----------'

for i,c in enumerate(count):
    if c==0:
        continue
    print "%2d %15d" % (i,c)
print "%2s %15d" % ('',sum(count))
print 'n =', n


After a bit of inspection, I notice that we're calculating slightly different statistics. You're counting average number of correct matches over all of your sample permutations. I'm calculating the mode of correct matches. I want to say that mine is technically more correct, but because the distribution is so even, your's works just as well. This could explain why you say you used ~10k trials and had good results.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Mon Feb 28, 2011 3:20 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
GuiltyBystander wrote:
I'm saying it's a great way to generalize the problem. It takes it to the next step. It's a good thing. I'm not trying to "dis" anyone or anything.
Thanks :D . Written text doesn't convey sarcasm well. If your first instinct reads the sarcasm, no matter how many times you re-read the sentence you can't shake the feeling that it could be sarcasm.

GuiltyBystander wrote:
Here's what my code outputs when I ran it for n = 100; (got coding on the brain so I feel instinctively ending sentences with semicolons :P)
Haha, I do the same thing! That belongs in a "You know you're a coder when..." thread.

Regarding your results:
GuiltyBystander wrote:
Code:
60            7265
61            7873
62            8399
63            9078
64            9638
65           10000
66            9914
67            9895
68            9851
69            9669
70            9142
The answer should be (2*100+1)/3 = 67 but it's not. Total permutations tested was 203804.
Interesting, I would have expected 67 to win. Expected value is a weighted average though so the expected value of the above would be ((60 * 7265) + (61 * 7873) ...) / 203804. I wonder if the distribution you're seeing is Gaussian. I think it should be but I wonder if it's skewed?

GuiltyBystander wrote:
I was just lazy and didn't want to see if the pattern held for n = [1,100]. That's why I stopped at n = 20. For small n, I was doing millions of samples. If something is worth doing, it's worth overdoing.
Oh I totally agree. Usually when given a number to adjust the first thing that pops into my head is usually "I wonder what the MAX is?".

The thing I worry about for this sort of simulation is that "shuffle" is probably just a Fisher–Yates algorithm implementation and the PRNG used is probably a LCG. LCGs have a low-order linear correlation which becomes pretty obvious when selecting a chain of array positions. When you do millions of trials the error due to a bias in your PRNG become more and more significant. My guess is that given even an infinite amount of time, shuffle can't reach all N! permutations because of PRNG bias.

GuiltyBystander wrote:
Here's my code [...]
Considering I wrote my code in perl and you wrote yours in Python I'm impressed how similar they are. I was pleased with my compact implementation but I see it wasn't unique in that regard.

GuiltyBystander wrote:
After a bit of inspection, I notice that we're calculating slightly different statistics. You're counting average number of correct matches over all of your sample permutations. I'm calculating the mode of correct matches. I want to say that mine is technically more correct, but because the distribution is so even, your's works just as well. This could explain why you say you used ~10k trials and had good results.
Well per my comment above, expected value is an average. Now here is another question, what is the probability that when simulated, 65 will reach 10000 hits before any other integer? I find calculating the expected value of the standard deviation / variance very difficult so I think the only way I could answer that is via another simulation.

This reminds me, two years ago I created a fun challenge program where you had to "cheat" a casino by exploiting a PRNG in one of their machines. Perhaps I can modify it so that it isn't interactive and then post here...

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Tue Mar 01, 2011 1:19 am 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
I wanted see if the error would be less with more samples so I ran it for 10M random permutations. The average was 67.0014998.
Code:
62          419462        85.30%
63          446485        90.80%
64          467134        95.00%
65          483817        98.39%
66          491736 *     100.00%
67          491189        99.89%
68          484404        98.51%
69          469717        95.52%
70          448431        91.19%
71          423265        86.08%
72          394222        80.17%
I kind of doubt that the 66/67 numbers are statistically different. At times (around 7.8M samples) they were within .01% of each other. If the bell curve is exactly center at 67, wouldn't you expect the unit 1 buckets on either side to have the same probabilities if it's Gaussian?

bmenrigh wrote:
Interesting, I would have expected 67 to win. Expected value is a weighted average though so the expected value of the above would be ((60 * 7265) + (61 * 7873) ...) / 203804. I wonder if the distribution you're seeing is Gaussian. I think it should be but I wonder if it's skewed?
I guess my statistic-esse is a little rusty and I didn't know the exact definition. It can't be a perfect Gaussian because it's centered at 67 out of the range [0,5050] it can't be perfectly mirrored. I can't make any statistical claims stronger than that.

bmenrigh wrote:
GuiltyBystander wrote:
I was just lazy and didn't want to see if the pattern held for n = [1,100]. That's why I stopped at n = 20. For small n, I was doing millions of samples. If something is worth doing, it's worth overdoing.
Oh I totally agree. Usually when given a number to adjust the first thing that pops into my head is usually "I wonder what the MAX is?".
I was trying to get several samples to look for a trend, but I understand your position too.

bmenrigh wrote:
This reminds me, two years ago I created a fun challenge program where you had to "cheat" a casino by exploiting a PRNG in one of their machines. Perhaps I can modify it so that it isn't interactive and then post here...
lol, that sounds nigh impossible but totally awesome if you could pull it off.


For some strange reason, this problem is reminding me of a fun math contest we had in 7th grade. I need to figure out how to present it better before describing it further. I know middle school math doesn't sound very engaging, but I found this particular assignment fun.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Tue Mar 01, 2011 3:44 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
How fast do you have to drive towards a red stoplight to see it turn green?

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Tue Mar 01, 2011 4:00 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jorbs3210 wrote:
How fast do you have to drive towards a red stoplight to see it turn green?
Assuming the wavelength of red light is 680 nm and the wavelength of green light is 530 nm then to achieve a dopler shift of (680 / 530) you need to be traveling 0.245 c.

sqrt((1 + .245) / (1 - .245)) / (680 / 530) =~ 1

Edit: the astute observer will point out that all that matters is the relative motion between you and the red light along the path the light takes needs to be .0245 c. You could be standing still relative to the surface of the earth and the light is moving towards you.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Tue Mar 01, 2011 4:09 pm 
Offline
User avatar

Joined: Sat Jul 11, 2009 1:09 pm
Location: My House
bmenrigh wrote:
Jorbs3210 wrote:
How fast do you have to drive towards a red stoplight to see it turn green?
Assuming the wavelength of red light is 680 nm and the wavelength of green light is 530 nm then to achieve a dopler shift of (680 / 530) you need to be traveling 0.245 c.

sqrt((1 + .245) / (1 - .245)) / (680 / 530) =~ 1

Edit: the astute observer will point out that all that matters is the relative motion between you and the red light along the path the light takes needs to be .0245 c. You could be standing still relative to the surface of the earth and the light is moving towards you.

The lazy observer would say you could just stay still and wait until the lights change. :wink:

Alex

_________________
If I had ÂŁ1,000,000 more, I'd be a Millionaire

YouTube Account: Cubiksrube113


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Wed Mar 02, 2011 3:39 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
bmenrigh wrote:
Jorbs3210 wrote:
How fast do you have to drive towards a red stoplight to see it turn green?
Assuming the wavelength of red light is 680 nm and the wavelength of green light is 530 nm then to achieve a dopler shift of (680 / 530) you need to be traveling 0.245 c.

sqrt((1 + .245) / (1 - .245)) / (680 / 530) =~ 1

Edit: the astute observer will point out that all that matters is the relative motion between you and the red light along the path the light takes needs to be .0245 c. You could be standing still relative to the surface of the earth and the light is moving towards you.


What is a "c"?

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Wed Mar 02, 2011 3:54 pm 
Offline
User avatar

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
c is the speed of light (in vacuum)


Top
 Profile  
 
 Post subject: Re: Enigmas, Riddles, and Paradoxes... (post yours here!)
PostPosted: Thu Mar 03, 2011 6:14 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
Well, you're very, very close.

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 129 posts ]  Go to page Previous  1, 2, 3

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group