3 ducks have landed in a circular pond. What is the probability there is a diameter such that the semicircle on one side contains all of them?
Repeat for 4 ducks.
Note: consider the ducks to be randomly chosen points in a circle.
Before I worked on this problem, it occurred to me that the answers might be different for different methods of randomness. All the solvers so far, assumed ducks land along a random ray. Anywhere along the ray is considered the same.
But what if ducks land at random x and y coordinates? To simulate this, I let x and y be uniform from -1 to +1 and then ignored values that would be outside the circle. I thought the results would be different, but in fact they were the same:
3 ducks: 0.75
4 ducks: 0.50
For my algorithm to determine if all angles result in all ducks being on the same side:
sort all angles in increasing order;
then subtract the smallest value from all so that one of them is 0;
now there is no confusing subtracting across the 0/360 line;
check each inter-duck angular "distance";
since they are sorted, if any distance is over 180, then they are all on the same side of some diameter.
------
import random
import math
def angl(dy,dx):
if dx == 0:
if dy ==0:
return 0
elif dy > 0:
return 90
elif dy < 0:
return 270
a = math.atan(dy/dx) * 180 / math.pi
if dy >= 0 and dx >= 0: # quadrant I
result = a
elif dy >= 0 and dx < 0: # quadrant II
result = a + 180
elif dy < 0 and dx < 0: # quadrant III
result = a + 180
elif dy < 0 and dx >= 0: # quadrant IV
result = a + 360
return int(result)
def issameside(aList):
""" bool: input a list of angles between 0 and 360 return True if they are all on the same side of a diameter. Algorithm, sort all angles in increasing order then subtract the smallest value from all so that one of them is 0. then check each inter-duck angular distance. Since they are sorted, if any distance is over 180 then they are all on the same side of some diameter. """
ducks = len(aList)
locs = sorted(aList)
locs = [ locs[:][i] - locs[:][0] for i in range(ducks) ]
distances = []
for i in range(ducks):
if i == ducks -1:
distances.append(360-locs[i])
else:
distances.append(locs[i+1]-locs[i])
if max(distances) >= 180:
return True
else:
return False
reps = 100000
ducks = 3 # or change this to 4
countTotal = 0
countSuccess = 0
for j in range(reps):
xy_coords = []
angles = []
landed = 0
while landed < (ducks):
x = (random.uniform(-1,1))
y = (random.uniform(-1,1))
if x**2 + y**2 > 1:
continue
landed += 1
xy_coords.append([x,y])
angles.append(angl(y,x))
countTotal += 1
if issameside(angles):
countSuccess +=1
print(ducks, countSuccess, countTotal, countSuccess/countTotal)
|
Posted by Larry
on 2023-01-25 13:24:36 |