A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula.
He told me they are using such an algorithm in some of their products and he picks the brain of potential hires to see if they find a more elegant way of doing so. Left a great impression, he really cared about thought processes and communicating! (I didn't end up taking the job for reasons unrelated to the company or the offer.)
Sounds like a traveling salesman problem... Perhaps if you look at a dual graph where the edges are collapsed into nodes and the nodes are stretched out to become edges? Then the problem statement of "visiting each city only once" might become equivalent.
I could be mixing things up here, it's been too long ago. I think this was about a directed graph, so the number of edges is actually N^2 and your walk roughly of that length.
To walk a fully connected graph with a prime number of vertices you can walk first to x+1, then x+2 then x+3 etc. edges by looping around. This a fun special case to prove (basically if you loop by x+i where i coprime to n, it loops after visiting all the vertices, and if n is prime every i is coprime to it)
Whenever you visit a node you need one edge to walk in and one to walk out, except for the first and last node.
So all K_n with even n , you can walk all the edges.
For odd n, you lose one edge per node, except for 2 of them
I think the parent was agreeing with you, but saying that the number of edges on the fully connected (usually called complete) graph on n vertices is 1 + 2 + 3 + … + n = n(n + 1)/2.
It's even great in the sense that a speedometer tends to make people aim for "I need to go 65 mph" instead of "I should not go above 65 mph" which a speed limit is actually intended to mean. The speed limit became a target instead of being a limit.
Traffic flows more smoothly when everyone is going at about the same speed. To achieve this without communication between vehicles, you need some "obvious" speed for everyone to try to drive at. In many contexts the speed limit fits this need pretty well.
There are situations where it doesn't. These are mostly also situations where the speed limit doesn't work terribly well as a limit either. For instance, bad weather or winding roads may mean that driving at or near the limit is unsafe. In that case, sure, it's not good for everyone to coordinate on driving at the speed limit, but it's also not good for everyone to think of the speed limit as the right upper bound for driving to be safe.
So I think that in most situations either (1) treating the speed limit as a rough target as well as a limit is mostly a good idea, or (2) the speed you try to use as a limit should be something other than the nominal speed limit.
Vehicles can all synchronize speed independently based on a well-tuned control law while observing only the distance to the vehicle in front of them. So looking out the window is sufficient for that, if the drivers are not terrible.
If driving at the speed limit on a winding road is unsafe, the speed limit is probably too high for that road. But in practice, it's complex, winding roads that cause people to drive at reasonable speeds, rather than numbers posted on signs.
This is largely because speed limits are too low. In safe conditions, most roadways are built in such a way that a modern vehicle can safely go 10-20mph over the speed limit without difficulty or increased risk. There are several reasons for this.
The point though is that timidity in a driver is actually more dangerous than exceeding the speed limit. Being consistently below the speed limit is a strong sign of timidity.
My driving instructor was (rightly) very hot on the principle that you must always be able to stop within the distance you can see. Speed limits are not set with this in mind.
In the UK, for example, that means that on winding country roads you should often be doing a lot less than the 60mph speed limit.
I agree with your instructor. That said, modern cars can stop in /much/ shorter distances than previously, largely thanks to improvements in tire technology.
Nearly every production vehicle available today can brake from 60mph in less than 140ft, more performance oriented vehicles can do so in under 120ft. The standards for “safe stopping distance” used in the US triple this distance to account for slowed reaction time because drivers are not attentive.
Realistically less than doubling these figures is correct for attentive drivers. 60mph is 88 feet per second, and 1 second is plenty of reaction time for an attentive driver, meaning 200-240ft total stopping distance, closer to double the distance the vehicle is capable of rather than triple.
So if the visibility is less than 200-240ft, you should be going slower than 60mph. 240ft isn’t very far in a car though, it’s roughly the distance traveled in 3 seconds at 60mph. There’s certainly some country roads I’d slow down on, but if you’re paying attention you’re well good on most.
For what it’s worth, the average reaction time of a gamer is 150ms, so a full second is plenty of margin of error.
Also not generally being surrounded on all sides by other unpredictable gamers whose own split-second reactions are going to determine what their safest move should be.
I don't think it's so much about the timidity of the driver, it's the effect on driving slow has on people behind you. Driving below the speed limit increases the amount of drivers who need to do overtaking, which are moments substantially more dangerous than just driving straight. If it weren't for forcing other people to overtake I don't think we'd really care, even if it was a sign of timidity.
Very common to see older people drive slow on the highway because going 100KM/h seems scary to them. This is, of course, absurd, since driving 80KM/hs on a 100KM/h road causes way more moments for bad things to happen because you're forcing everyone to merge into the speed lane, including trucks with bigger blind spots, rather then only the drivers choosing to go above the speed limit. If you do this you should absolutely be fined, and that's not because it's a good metric for timidity (which I agree can be bad for drivers in general), but rather that the action itself causes harm.
> Driving below the speed limit increases the amount of drivers who need to do overtaking,
Nobody "needs" to overtake or is "forced" to doing something dangerous outside safe margins. Seriously, this is blame shifting when somebody does something stupid. When you do, it's 100% on you.
100km/h on a highway with everybody otherwise going 130km/h is rare. This is about a 65mph road (100km/h?) where somebody goes 95km/h and everybody behind them goes berserk. That's an attitude that needs to change, not by the 95km/h driver, but by everybody behind. Going 100km/h is not a right, does not force you to do stupid overtaking maneuvers and the time you lose by going 95km/h is negligible. At least it's substantially less than you'd expect, since there are many other factors that slow you down on a journey. You rarely drive for 3 hours straight, no interruptions, no other traffic on the road. Even if you did, doing 100km/h instead of 95km/h would get you there by 9 minutes earlier. That's the upper limit here, but you are likely going to save less than 5 min. After 3 hours.
We (for some measure of we, but at least the US and most Commonwealth countries) have laws against this. It's called "Impeding the Flow of Traffic". As far as it matters, you are absolutely and directly wrong about your statement here. It's the 95km/h driver that needs to change.
You seem to have an agenda in your comments here, and in some of them I think you have a point, in this one you are overplaying your hand.
50mph on a 65mph road may be "impeding the flow of traffic". 63mph certainly isn't.
I'm a bit confused regarding your insinuation of an "agenda" in my comments? I've been in enough situations where somebody behind me or others on the road was endangering everybody just because the car in front of them wasn't going the $safe_margin_above that they were expecting of everybody. So they go like 3ft behind them and put pressure and stress on people. It's a dangerous mentality that can get people killed. It's not the "slow person" (going at 63mph) that's the danger in that scenario.
I personally find GPs agenda of promoting patience, common sense, and safety on the roads to be both dangerous and offensive. That kind of mentality is only a hop and skip away from becoming a deranged anti-car environmentalist.
> The point though is that timidity in a driver is actually more dangerous than exceeding the speed limit.
This is a bizarre claim, since most accidents/deaths would be avoided by cars being slower. Unless you have data on this, this is just "I like to drive faster" with more words.
Nearly every study on the topic has concluded that faster vehicles get into less accidents, but the accidents they do get into are more likely to be fatal. Conflating accident rate and fatality rate means you can’t see the forest for the trees.
At any rate, neither statistic has anything to do with my claim. Timidity is dangerous because it’s unpredictable and creates a rolling roadblock. The most dangerous thing while driving is /other drivers/. Being able to predict their behavior and avoiding having to overtake both greatly reduce risk. Timidity increases both of these risks significantly.
> Nearly every study on the topic has concluded that faster vehicles get into less accidents
Citations definitely needed. Not just of the studies that perhaps support your point, but of the reviews that do a quantitative overview of that the majority of studies conclude what you claim. Everything else is "I want to drive fast, slow grannies out of my way".
> Parking is a problem in a lot of European cities.
On the flipside, the inner cities are much nicer. You have fewer of those seas of concrete just for parking. I wish it was even more so and street parking as well as open lots would just not be a thing. If you really need to come by car, put it in some underground parkade (for $$$). Cities are too dominated by cars. They should be there for people, not the other way around.
But this is Hacker News where people who build things hang out. If you are fine with the state of the world and are not involved in advancing it, good for you, you can close this discussion. But many people around here are building the next things. And in that context it makes sense to think about what's the future and what's not.
You sound like every other person responsible for the rampant NIHism in Linux and the reason why the "year of the Linux desktop" is in the year 6002 at this rate.
Which exactly describes the problem with today's culture of people watching a 10 minute youtube clip and then thinking they are experts on the subject matter.
But that's exactly what you did! You just counted which fraction of all kids is boys. You threw away that this is about pairs of kids, about april 1 on which one of them has their birthday and is a boy, and we want to know the sex of the other one. You already simplified by applying symmetry reductions. You could have just done print(1/2) and proclaimed that the output was 0.5 which therefore must be the solution.
What's really fun about this problem is that you can have very convincing arguments for 1/2 being the correct answer, and very convincing arguments for 1/3 being the correct answer. And for either you can make subtle reformulations that supposedly illustrate how ridiculous this answer is.
And there is no way to know. There is no gold standard for designing an experiment that would show whether 1/2 or 1/3 is correct. You could set up something that generates millions of pairs of (virtual) kids and then count the pairs that fit. But each of these experiments will have built-in the assumption on which the response is ultimately already predicated on.
The only thing really convincing would be if everybody, all "sides", could agree on an experiment with an outcome that they would feel bound to. Then one could settle this once and for all, whether it's 1/2 or 1/3 or 13/27 or 729/1459 or whatnot. But people will never agree on such an experimental setup.
Which tells me that this is not a mathematical problem. This problem is either underspecified or it's contradictory. If it was uniquely specified then we could just use probability theory with its axioms and inference rules to derive at the correct answer. But we obviously can't, since nobody can agree on how to formally note this down.
> I tell you I have two children and that (at least) one of them is a boy, and ask you what you think is the probability that I have one boy and one girl.
2/3
> I tell you I have two children and that (at least) one of them is a girl, and ask you what you think is the probability that I have one boy and one girl.
2/3
If you don’t, why not?
If you do, what’s your answer to the following question?
> I tell you I have two children and that I’ve just sent you an email with the sex of (at least) one of them, and ask you what you think is the probability that I have one boy and one girl.
What I don’t understand is that when you read the content of that email you will find yourself in either the first situation (I told you that I have two children and that (at least) one of them is a boy) or the second situation (I told you that I have two children and that (at least) one of them is a girl).
In both cases the probability will be 2/3 so why wouldn’t you conclude that the probability is 2/3 without waiting to find out the (irrelevant) details?
The odds only sound equal/the details irrelevant because you are only looking at one outcome from the set. In reality, the email will resolve the probabilities to: (BB: 1/3 BG:2/3 GG:0/3} or {BB:0/3 BG:2/3 GG:1/3}. Although the BG values are the same, the rest of the probabilities are not. Therefore, the details are relevant.
I don't have a great explanation as to why that's intuitively true, but it is. I can try again if things are still confusing. But if so it would help to know if you understand the Monty Hall problem.
The odds don’t “sound equal”. According to you, they are equal (2/3).
Saying
“before opening the email I think the probability that you have one boy and one girl is 1/2 but one of two things will happen, I either find that you have at least one boy and I will conclude that the probability that you have one boy and one girl is 2/3, or I will find that you have at least one girl and I will reach the same conclusion”
is like saying
“under this cup there is either a dime or a quarter, it’s a dime the probability of heads is 1/2 and if it’s a quarter the probability of heads is also 1/2”
and claiming that the probability of heads before I tell you whether it’s a dime or a quarter is something other than 1/2 and changes always to 1/2 when I let you know what it is.
I understand the Monty Hall problem. I also understand this one.
With those assumptions the probability that there are a boy and a girl are 2/3 if I tell you that there is at least a boy and 0 if I tell you that there is at least a girl. The probability that the email says that I have at least a boy are 3/4 (I would only say that I have a girl if I didn’t have any boys). You can calculate the probability that I have one boy and one girl before opening the email as 3/4 * 2/3 + 1/4 * 0 and it equals 1/2 as it should.
You need to look at the odds for all events. You cannot just look at the odds for a just specific event for deciding that the specified gender in the email is irrelevant. The fact that the rest of the odds are different means that it's 1/2 when the email is sent.
Your coin question is totally different. Whether the coin is heads or tails is independent from which coin it is. Whether you mention you have at least one boy is not independent of the gender of the children.
Your last paragraph has correct math. But the math works equally well with "specify a girl if you have one" or "flip a coin and use a random kids gender"
> Your last paragraph has correct math. But the math works equally well with "specify a girl if you have one" or "flip a coin and use a random kids gender"
That’s the point.
The math works well with "specify a boy if you have one" and then the answer to A [I tell you I have two children and that (at least) one of them is a boy, and ask you what you think is the probability that I have one boy and one girl.] is 2/3 and the answer to B [I tell you I have two children and that (at least) one of them is a girl, and ask you what you think is the probability that I have one boy and one girl.] is 0.
The math works well with "specify a girl if you have one" and then the answer to A is 0 and the answer to B is 2/3.
The math works well with "flip a coin and use a random kids gender" and then the answer to A is 1/2 and the answer to B is 1/2.
If every parent with two kids says either “at least one is a boy” or “at least one is a girl” there is no way to make the math work so the answer to A is 2/3 and the answer to B is 2/3.
——-
As I explain in another comment for that the two following conditions need to be met:
P(you tell me that you have at least one boy | you have two boys) = P(you tell me that you have at least one boy | you have one boy and one girl)
P(you tell me that you have at least one girl | you have two girls) = P(you tell me that you have at least one girl | you have one boy and one girl)
There are ways to make the math “work”. For example: if you have two boys or two girls flip a coin and if you get heads talk about the weather, if you get tails say [I have two kids and at least one is a boy/girl], if you have one boy and one girl say [I have two kids and at least one is a …] using a coin flip to decide if you say “girl” or “boy”.
However, they seem quite unnatural and hardly a justification to claim that “any arguments for 1/2 are just wrong.”
No matter how you choose the statement "I have at least one (girl/boy)", (prefer one, flip a coins, etc) once you tell me it's always 2/3 boy-girl. Until you tell me it's 1/2. Any algorithm to choose which to say works as long as it's true and you don't convey more information about the children like "my older child is male".
Your counter arguments are wrong, but you don't seem to even acknowledge that I am saying that. I'm willing to try to explain why, but not if you don't want to learn and just want to insist you are correct. Ask yourself how long you would spend trying to explain Monty Hall to someone who kept insisting it was 1/2 to change.
> Your counter arguments are wrong, but you don't seem to even acknowledge that I am saying that.
I do acknowledge that you're saying that I'm wrong. That's why we're still exchanging arguments! What I don't know exactly is what do you think that it's wrong with my arguments so I try to find where do we agree - and where we don't.
It seems that you don't agree that the answer depends on the (relative) value of P(you tell me that you have at least one boy|you have two boys) and P(you tell me that you have at least one boy|you have one boy and one girl).
> I'm willing to try to explain why, but not if you don't want to learn and just want to insist you are correct.
Well, I could also say that just want to insist that my arguments are wrong but I sincerely hope that you want to learn as much as I do.
> Ask yourself how long you would spend trying to explain Monty Hall to someone who kept insisting it was 1/2 to change.
As long as needed. Souls are saved one at a time. Here we go.
-----
> No matter how you choose the statement "I have at least one (girl/boy)", (prefer one, flip a coins, etc) once you tell me it's always 2/3 boy-girl. Until you tell me it's 1/2. Any algorithm to choose which to say works as long as it's true and you don't convey more information about the children like "my older child is male".
That's wrong and I'm going to try to show you that with an example (the mathematical proof is in the link above). Hopefully I'm not misrepresenting your position - please tell me if I do.
You are in an auditorium with 600 people. Each of them has two kids. (Let's assume there is no strange thing going on like "meeting of parents with twins" and the sex of the kids is equally probable and independent.)
Q: What's the probability that a given person has one boy and one girl?
A: 1/2
Q: How many of them do you estimate that have one boy and one girl?
A: 300
Each of them write into a paper their name and "I have at least one (girl/boy)" (they never lie and if there is a choice the choose however they want: prefer one, flip a coin, etc.).
You have the 600 papers in front of you, but have not read them yet.
Q: What's the probability that a given person has one boy and one girl?
A: Still 1/2
Q: How many of them do you estimate that have one boy and one girl?
A: Still 300
You can win $100 if you guess correctly whether there are more than 350 or less than 350 people with one boy and one girl.
Q: What's your guess?
A: Less than 350, because my estimate is 300.
Q: What will be the probability that a given person has one boy and one girl after you've read the papers?
A: 2/3 because once they tell me it's always 2/3 boy-girl.
Q: How many of them will you estimate that have one boy and one girl after you've read the papers?
A: 400
Q: Do you want you want to change your guess to "more than 350"?
A: No, until I read the papers the probability is 1/2 and my estimate is that 300 people have one boy and one girl.
Q: So you keep your "less than 350" guess even though you know with certainty that in a few minutes you will estimate that the right answer is around 400 and you will wish you had answered "more than 350"?
A: Yes, I'm happy with that. I think I could get the $100 if I answered "more than 350" now but I refuse to do it until I read the papers.
You read the papers.
Q: What's the probability that a given person has one boy and one girl?
A: 2/3
Q: How many of them do you estimate that have one boy and one girl?
A: 400
Q: Do you want to change your guess for the $100 prize?
A: Yes, now I’d like to answer "More than 350". Thanks for letting me change my guess!
Unfortunately you lose, because in a group of 600 pairs of kids we expected around 300 pairs of boy and girl. Writing things on a paper leaves the children unaffected.
I think now I understand. "I will make you make exactly one of two statements and each results in a 2/3 chance of BG" doesn't make sense. "You freely made one of two statements and each results in a 2/3 chance of BG" does. I interpreted "it depends on randomness" as "speak up if you have at least one boy" or "speak up if you have at least one girl", each of which would result in 450 saying something in your example and the math works.
So it comes down to if we decide on the question (however we do that) before we look at the kids or after.
> I interpreted "it depends on randomness" as "speak up if you have at least one boy" or "speak up if you have at least one girl", each of which would result in 450 saying something in your example and the math works.
The point is that original problem says "I tell you I have two children and that (at least) one of them is a boy". It doesn't say "I tell you I have two children and [when you ask me to confirm whether (at least) one of them is a boy] that (at least) one of them is a boy".
Reasoning from the cases "BB", "BG", "GB", "GG" - and discarding the last one to get p(BB)=1/3 - is implicitly using the cases "BB and I tell you that at least one of them is a boy", "BG and I tell you that at least one of them is a boy", "GB and I tell you that at least one of them is a boy", "GG and I tell you something else like at least one of them is a girl".
That breaks the symmetry between the "I tell you that at least one of them is a boy" and the "I tell you that at least one of them is a girl" problems. Using the cases in the previous paragraph the answer for the former is p(BB)=1/3 but the answer to the latter is p(GG)=1.
If you want to have the same solution when you switch girl <-> boy ["one of them is a boy, what is the probability that I have two boys" <-> "one of them is a girl, what is the probability that I have two girls"] you should treat them equally.
A quite natural way to do so would be to consider the eight equiprobable cases (some of them repeated)
BB and I tell you that at least one of them is a boy
BB and I tell you that at least one of them is a boy
BG and I tell you that at least one of them is a boy
BG and I tell you that at least one of them is a girl
GB and I tell you that at least one of them is a boy
GB and I tell you that at least one of them is a girl
GG and I tell you that at least one of them is a girl
GG and I tell you that at least one of them is a girl
but then the answer to both problems is 1/2.
You can make the answer to both problems 1/3 but the eight cases that you would need to consider for that are quite unnatural:
BB and [... discard this line somehow ...]
BB and I tell you that at least one of them is a boy
BG and I tell you that at least one of them is a boy
BG and I tell you that at least one of them is a girl
GB and I tell you that at least one of them is a boy
GB and I tell you that at least one of them is a girl
GG and I tell you that at least one of them is a girl
GG and [... discard this line somehow ...]
I think at this point we agree on the math and disagree on how the original question should be read. You saw an implicit alternative to the statement as "I have two children, at least one is a girl" and assumed in the question the parent was saying exactly one of that or the original statement "I have two children, at least one is a boy", possibly chosen randomly, from among the true answers. I read it as a simple statement true statement with GG just being an undefined state for the statement generation, maybe resulting in nothing being said. We could argue about parsing English, but it seems less interesting which question was being posed if we agree on the math behind each parsing, which I think we do?
> You saw an implicit alternative to the statement as "I have two children, at least one is a girl" and assumed in the question the parent was saying exactly one of that or the original statement
The alternative was made explicit when I asked you what do you think that the probability is for two girls under the alternative.
Given that you think that it's also 1/3 the question is how do you arrive to those 1/3 answers in a coherent way.
> I read it as a simple statement true statement with GG just being an undefined state for the statement generation, maybe resulting in nothing being said.
And with BG and GB being states that generate the statement "I have two children, at least one is a boy".
But then BG and GB cannot generate the statement "I have two children, at least one is a girl".
As a I said there are also ways to justify that the answer to both is 2/3 even though they don't look very nice.
> We could argue about parsing English, but it seems less interesting which question was being posed if we agree on the math behind each parsing, which I think we do?
Maybe we can also agree that this is an undefined situation because the answer depends on how you decide to interpret the question.
More precisely, it depends on your assumptions about the (relative) value of P(you tell me that you have at least one boy|you have two boys) and P(you tell me that you have at least one boy|you have one boy and one girl).
He told me they are using such an algorithm in some of their products and he picks the brain of potential hires to see if they find a more elegant way of doing so. Left a great impression, he really cared about thought processes and communicating! (I didn't end up taking the job for reasons unrelated to the company or the offer.)