Wikipedia:Reference desk/Archives/Mathematics/2009 March 23

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 23

Birthdays Part 2

This is (sort of) a follow-up to my question above. Let us assume that each day of the year is equally likely as any other to be a randomly selected person's birthday. Thus, all of the days of the year have an equal probability of 1/365. (Again, let's "pretend" that February 29 does not exist as a birthday.) If I randomly selected 365 people and, say, placed them in a room ... shouldn't everyone in that room have a different (unique) birthday? In other words, should all 365 days of the year be represented ... or no? Something tells me "no" ... but, why not? Also, if the answer is indeed "no" ... how many people would it, in fact, take to fill a room such that we would insure all 365 birthdays are represented? Thanks. (Joseph A. Spadaro (talk) 04:32, 23 March 2009 (UTC))

The problem of how many people are needed before probably two have the same birthday is the Birthday problem. The problem of how many people are needed before all 365 days appear is the Coupon collector's problem. McKay (talk) 04:38, 23 March 2009 (UTC)

And the direct answer to the second question is that if you have no information about actual birthdays, you could put the entire population of the world in your room [to implement this, I recommend an inversion transformation :-)] and you still couldn't be sure that all be sure that all 365 birthdays are represented. For all you know, it's possible that a February 16 birthday, like North Dakota, does not really exists -- by chance, nobody alive has that birthday. Sure, the probability of that is about (364/365)^6,750,000,000, which is a pretty small number, but you wanted certainty. --Anonymous, 20:25 UTC, March 24, 2009.

And just to have an idea, it's quite unlikely to get all 365 days among the 365 people: around 1 over 10¹⁵⁵ --84.220.118.44 (talk) 09:01, 23 March 2009 (UTC)

It hinges on the fact that once you have n people in a room, assuming they have different birthdays, then you have only a (365-n)/365 chance that the next person has a different birthday. As n increases, and assuming that the probabilities are independent, the probability of all people having a different birthday decreases significantly. At around 20 you have a 50% probability of two people with the same birthday. -mattbuck (Talk) 14:03, 23 March 2009 (UTC)

What do mathematicians think about legal laws?

I have studied legal philosophy, but am an amateur math hobbyist. One of my favorite books, talking about elastic collisions (physics) says that nature does the calculation in a split second and adjust each balls momentum to ensure that total kinetic energy of the system is conserved. Its a fun book that toys with the imagination through thought experiments (like the example).

Here goes my question: the laws that govern our society were written by lawyers, not mathematicians. Do mathematicians "see" the ugliness and discontinuity of laws and does it bother them? Petit theft and grand theft differ only by a penny. If someone is adjudged incompetent they avoid criminal so-n-so, if they are not judged incompetent they are 100% open to charges or whatever (these examples are just generalizations, they probably aren't accurate if a lawyer reads the math desk).

I never got an education in math, nor became a mathematician, but I have the heart and brain of a mathematician (i.e. love to see how numbers are involved in every single facet in life!)

It takes extremely in-depth scrutiny and analysis to show why Newton's laws break down at some ultra-deep level, however a small subset of all the laws are surprisingly poorly thought (afterall, legal "loopholes" are simply finding a flaw or else a unimagined implication of the law's use, etc...) Is there a relevant wikipedia page on any of this? Is there an author who wrote a book on the topic? Does he or she or his/her book have a wiki page?

I sincerely value the excellent answers I get from the ref desk here, and it helps keep my hobby going when I finish a book and don't know what to start on next.

Thank you,

PS, I tried to keep this completely not about the examples I used; if I could describe whatever I'm looking for, I could google it, if it exists. After about 30 minutes of looking on wikipedia, the closest thing I have found is metamathematics but its a mathematical dissection of math, not of legal laws. Maybe the info I'm seeking doesn't exist? 71.54.173.193 (talk) 08:45, 23 March 2009 (UTC)

There are a lot of mathematicians (even more if you just count people with math PhDs). So their viewpoints on politics, philosophy, law, etc. will vary quite a bit; I don't think you will be able to find any one viewpoint that 75% of mathematicians subscribe to.

There is a anecdote that may be interesting to you. Kurt Gödel immigrated to the United States during World War II and took a citizenship test in 1947. When the presiding judge asked Gödel if the U.S. could become a dictatorship like Germany had, Gödel started to explain how his analysis of the constitution found a loophole that would allow it to happen. The judge, who knew to expect that sort of thing, cut him off and moved the hearing along. — Carl (CBM · talk) 12:14, 23 March 2009 (UTC)

That's a good point. Derrick Niederman wrote a good book that let me appreciate the way that mathematicians think outside of their field. He wrote how politicians and the public think that cutting pork-barrel spending is important, when in fact the national debt is $10 trillion and gave an analogy of the two, explaining the difference in orders of magnitude (which I wish I could specifically recall). Certainly mathematicians would try and make laws that pulled from their analytical reasoning skills. Since I presume mathematicians had no input into making our laws, the laws are void of mathematicians' input, and mathematician-authors could surely point out plenty of fine examples. If nothing else, I read a few great pages on philosophy--some good stuff is over in that little niche of wikipedia--not at all a bad way to start a Monday morning. 71.54.173.193 (talk) 13:01, 23 March 2009 (UTC)

An analysis of the British nationality law was done about thirty years ago or so by some mathematicians as a test case of formalizing law and they turned up all sorts of corner cases which weren't covered or caused contradictions. The British parliament issues a law a day practically and doubles the size of the tax mans' manual every few years, it's about 10 or 15 thousand pages now I believe. It is more the sort of field where a data base specialist or artificial intelligence worker might like to potter I think. It's just too messy and awful. And the interactions with other countries, oh dear, my wife just got a form sent back to her saying she had to fill in a field for country as England rather than United Kingdom, she's photocopying it so when they next reject it she can get all the accepted fields right and tweak the rejected field. Dmcq (talk) 15:50, 23 March 2009 (UTC)

In a version of the Gödel anecdote that I've seen more than once, the judge (making casual conversation) said "Of course that can't happen here" and Gödel started to say "Well actually—" but Einstein kicked him under the table. But I haven't seen an account of what Gödel found. —Tamfang (talk) 17:48, 24 March 2009 (UTC)

That's the version that I've heard (and the version that I tell people)... any recollection where you heard it? I recall reading it in a popular mathematics book a number of years ago but I can't recollect which one. The wikipedia article agrees with Carl's explanation. Eric. 131.215.158.184 (talk) 00:37, 25 March 2009 (UTC)

Where you write "Do mathematicians "see" the ugliness and discontinuity of laws and does it bother them?", I must say (for myself anyhow), yes, wholeheartedly. A good example, I feel, is the bicameral system of US congress. We have a House and a Senate, one representing states by population and the other having two representatives from each state, purely as a result of a political compromise between the large and the small states when the constitution was originally written. We had, at the time (and quite possibly today as well), no reason to believe that a bicameral legislature is a better way to run a government than the alternatives. Almost anything we look at in the US constitution arose because of a political compromise, not from ratiocination of the optimal solution, or for any mathematical or game-theoretic reasons. I can hardly blame the authors of the US constitution for not using game theory, as it didn't exist at the time, but that doesn't make me feel any better about the quality of the constitution.

I doubt we have a page on what mathematicians dislike about the legal system, nor do I think it's an encyclopedic topic, but if you do turn up any authors who have written books on the topic (or related topics) I'd be very interested to hear. Eric. 131.215.158.184 (talk) 19:30, 23 March 2009 (UTC)

I'm a strong supporter of the bicameral legislature, for the simple reason that it makes it more difficult to pass laws. It's still far too easy at that.

I'd be willing to get rid of the Senate in exchange for a countervailing requirement that made legislation equally or more difficult to pass. Or for one that made repeal of laws easier than passing them. --Trovatore (talk) 19:38, 23 March 2009 (UTC)

But that doesn't explain why the two chambers apportion power to the states in completely different ways. The problem is caused by the necessity, when putting together a new system of government, of keeping everyone's level of power pretty much the same as it already is (otherwise you won't get it approved). You are then stuck with that system for a long time, despite the fact that it only really made sense at the time it was made. --Tango (talk) 19:48, 23 March 2009 (UTC)

Hm? But it does make sense now. Oh, it's probably not the optimal solution, but you'll never get that. It's better than a naive unicameral solution, which would make legislation too easy to pass, as it is in the (effectively unicameral) UK. --Trovatore (talk) 20:13, 23 March 2009 (UTC)

How does it make sense for the fair way of apportioning votes to be completely different in each chamber? Does the UK have more pointless legislation than the US? If you want to make it harder to pass laws, just have a unicameral system which requires a supermajority to do anything. --Tango (talk) 20:32, 23 March 2009 (UTC)

Who has more pointless legislation (but honestly it's not pointless legislation I'm worried about, but rather pointed legislation imposed by a minimum winning coalition) I won't venture to say. I think it's a flaw in the UK system that it is too easy for the government in power to impose its will, that's all I'm saying.

A unicameral system with a supermajority might be acceptable; certainly I'd be willing to consider it. But the mere fact that a unicameral system with simple majority is theoretically neater-looking is not sufficient reason for me to support it. --Trovatore (talk) 20:47, 23 March 2009 (UTC)

Certainly the "everyone's power must stay the same" problem is a big deal... I wish I knew a way around it. See DC Voting Rights Act, fourth bullet, for an example... the only way to give the DC a vote (surely Democratic) in the House is to balance it with giving Utah an extra vote (surely Republican)....

As for apportioning power differently in the two houeses, that can be (plausibly) justified. Perhaps there is a reason to make the houses heterogenous with respect to each other, say, so that it is harder to pass legislation as Trovatore advocates. Having both houses apportion power similarly makes legislation easier to pass because it increases the likelihood that the same party is in power of both houses simultaneously. Possibly the benefits of heterogeniety outway the cost of having one of the houses have non-optimal power apportionment. Eric. 131.215.158.184 (talk) 22:25, 23 March 2009 (UTC)

There are a lot of alternatives to bicameral, not just unicameral. We can always just increase the number of houses... is there a particular reason why 3 or 4 is worse than 2? Or better? Sure, at some point the complexity overwhelms the system, but it's hard to say at what point the added complexity balances against any marginal benefit of having more houses (assuming that there is a benefit at all). And the moment that you have more than one house, you have a huge number of choices of the relationship between the houses. One could conceive of a system of major and minor legislation, where either house has the authority to pass minor legislation, but both houses must agree to pass major legislation (mmm... I can see some problems with that). Voting rules can be different within the two houses: one requires supermajority and the other does not. Or a supermajority within one house overrules a non-supermajority within the other. Or only one house can initiate legistlation. Or only one house can ammend existing legislation.

Another arbitrary facet that plays a pivotal role in modern politics: state boundaries. States have their present boundaries in large part due to quirks of US history. But the relative sizes and demographics of the states play a massive role in modern politics and the division of power and control between the states. Although "optimal" is hard to quantify here, it seems quite reasonable to claim that pure chance did not give us the optimal location of state boundaries. Of course, that raises the question of why power should be apportioned into smaller regions at all, or why those reasons should be geographically based, instead of based on ideological differences, wealth differences, educational differences or any number of other relevant features. Eric. 131.215.158.184 (talk) 22:12, 23 March 2009 (UTC)

You mention the difference between theft and grand theft, which isn't as big of a deal, because you're put in front of a judge who is given subjective power. Tax law is a lot less subjective. A good example, something I saw recently, is the new Housing Stimulus package we have in the US. If you are a first time home buyer (haven't owned a home in 3 years) and you make less than $75,000 as a single or $150,000 as a couple, you will get an $8,000 tax credit. Now what about the people making $77,000? They should try and make at least $2,000 less so that they can get $8,000 more. They also are not accounting for regional/cost of living differences. In some parts of the country a salary of 75K will afford you the largest house on the block and in other parts you'll probably have to live in one of the worse neighborhoods to afford anything, and it'd still be small.

While mathematically it could use lots of improvements, it doesn't bother me because I know they are intentionally try to make it simple since tax code is complex enough.Anythingapplied (talk) 20:19, 23 March 2009 (UTC)

You're joking about the tax code aren't you? Firstly the past is a guide to the future so if it has been made complex it will be made more complex. Also the evidence is against you in the uk, it is growing fast and is coming on to about half the size of the current Encyclopaedia Britannica. Dmcq (talk) 18:46, 24 March 2009 (UTC)

The Sorites paradox is possibly the best example of a theft/grand theft situation, and its a problem which have troubled philosophers for centuries. Essentially here you have a function from a continuous and possibly multi-value input to a discreet set and there probably is no ideal solution. For the tax codes again an optimal solution may be hard to find, but a monotonic solution would be an improvement.--Salix (talk): 20:29, 25 March 2009 (UTC)

There are logical laws that indicate that these points of uglyness must be there. See ie. Gödel's incompleteness theorems, which puts strong limits on formal systems. And Arrow's impossibility theorem, which shows the impossibility of a "fair" voting system, and iirc can be adapted to a theorem about resource allocation. Taemyr (talk) 20:43, 23 March 2009 (UTC)

What, if anything, do Gödel's incompleteness theorems have to do with politics or law? Algebraist 21:05, 23 March 2009 (UTC)

Are you alluding to the apportionment paradox? I don't think that follows from Arrow's theorem (it was proven much later). Eric. 131.215.158.184 (talk) 21:54, 23 March 2009 (UTC)

Gödel's results apply to logical systems sufficient for basic arithmetic - has any government ever existed that was capable of doing basic arithmetic? --Tango (talk) 22:10, 23 March 2009 (UTC)

I've actually taken law as one of the prime examples of where the mathematical and scientific styles of thought break down. Since law deals with morality, compromise, pragmatism, and fast decision-making, a theoretical framework is hard to produce. Morality is viewed differently by every person, and some people think it's arbitrary in the first place, but it has to form the foundation of a lot of our legal system. The rest is maintaining the social order. Since nobody agrees on either, we have to take a bizarre middle ground in a lot of cases just to get anything done, and we have to base the decisions made on insufficient evidence and the partially-formed ideas of people with a lot of other work to do. It would be like trying to mathematicize a game of tennis where no player could agree on the rules, but the game had to be decided by lunchtime. It's just not possible. I would see law, in formal terms, as more a giant pile of heuristics. We can't make them consistent without pissing off most of the population (hence compromise), we can't make them optimal without unlimited information and insight, and there's really no point in legislating for things that won't happen. Who cares what the law has to say, if anything, on whether flying pigs should need pilots' licenses? They don't exist! This will not come to court anyway! In a purely logical system, however, that would be just as important a decision as any other - logic provides no way of evaluating the importance of one fact over another. And of course, there are the formal problems mentioned before, such as Arrow's paradox and the Liar's paradox. In the first, it is clear that the unique optimal voting system is formally impossible, and in the second it is clear that there are some questions that can be asked, but not answered, in any reasonably powerful formal system. Black Carrot (talk) 22:29, 23 March 2009 (UTC)

What, if anything, does the liar paradox have to do with politics or law? Algebraist 15:11, 24 March 2009 (UTC)

That's an excellent question. I can't remember what I was thinking when I wrote that. I think my impression was that there is a way to embed the liar paradox or something similar into a legal dispute in such a way that the court would have to make a ruling, but could have no logical basis for doing so, a bit like the Hanging Man paradox. I'm having trouble coming up with an actual example, though. Black Carrot (talk) 19:06, 24 March 2009 (UTC)

Here's a rather unpleasantly contrived example. What if someone, under oath, testified that they were telling a lie? Does that count as perjury? Of course, in the real world they would probably "cut the knot" and find him in contempt of court if they paid attention at all, but it's the best I've got at the moment. Black Carrot (talk) 19:10, 24 March 2009 (UTC)

They would probably be found in contempt to talking about something not relevant to the trial - or just told to get on with answering the questions. --Tango (talk) 15:01, 25 March 2009 (UTC)

Wonderful disccuion Thanks! I have printed this section and ordered two books from my library based on some of the ideas shared. Great diversity of opinions also, I always appreciate seeing more than one viewpoint--it piques my quest for truth! 71.54.173.193 (talk) 18:39, 26 March 2009 (UTC)

What books? Black Carrot (talk) 22:41, 26 March 2009 (UTC)

Joke: A cop checks the local Lover's Lane after reports that there are girls under legal age of consent consorting with men there, which is a prosecutable offence. He finds a car parked in the dark. In the car sit a man smoking and a teenage girl knitting. The cop demands to know how old the girl is. The man looks at his watch and replies She'll be 18 in half an hour. Cuddlyable3 (talk) 21:05, 27 March 2009 (UTC)

vertex connectivity of a graph

Hello. I want to prove that the following construction of a graph G with n vertices and e edges gives us a graph with maximum possible vertex connectivity which is $\left\lfloor {\frac {2e}{n}}\right\rfloor$. First construct a regular graph on n vertices where each vertex has degree $\left\lfloor {\frac {2e}{n}}\right\rfloor$. Now add the remaining $e-{\frac {n}{2}}\left\lfloor {\frac {2e}{n}}\right\rfloor$ edges arbitrarily. The resultant graph has vertex connectivity $\left\lfloor {\frac {2e}{n}}\right\rfloor$.

I can understand that such a graph would have a vertex v of degree $\left\lfloor {\frac {2e}{n}}\right\rfloor$ and removing the adjacent vertices of v would thus disconnect the graph but I want to prove that removing fewer vertices can never disconnect G. How can I do that please?--Shahab (talk) 16:24, 23 March 2009 (UTC)

As stated, this procedure obviously fails. For example, with n=e=6, one such G is a pair of triangles, which is not even connected. I'm not sure yet if requiring connectivity of the $\left\lfloor {\frac {2e}{n}}\right\rfloor$-regular graph gets you anywhere. Algebraist 16:31, 23 March 2009 (UTC)

Update: it doesn't. There are 3-regular connected graphs which are not even 2-connected. Algebraist 16:43, 23 March 2009 (UTC)

There's another problem, too. n and $\left\lfloor {\frac {2e}{n}}\right\rfloor$ may both be odd, in which case there is no regular graph with that degree. A suggestion for a different construction: form a clique of the desired connectivity, connect every other vertex to each clique vertex, and use up any leftover edges by connecting pairs of non-clique vertices. —David Eppstein (talk) 17:03, 23 March 2009 (UTC)

OK. I see this construction is faulty. I was reading from this book(Pg 78). David, why will removing the vertices in the clique disconnect the graph? Non-clique vertices may be forming a path.--Shahab (talk) 18:20, 23 March 2009 (UTC)

I don't understand the implicit claim in the second sentence of the original post. The complete graph on n=k vertices and e=k(k-1)/2 edges is k-vertex connected and (k-1)-edge connected, right? However, k is quite a bit larger than floor( 2e/n ) =floor( k/2 ) = k-1, right? In particular, K4 has n=4, e=6, k=4 > floor(2e/n) = 3. Is it asking for a graph that somehow manages to NOT be highly connected? JackSchmidt (talk) 18:02, 24 March 2009 (UTC)

2e/n=k-1 in that case. Where I come from (Bollobas's text book agrees with me), the complete graph on k vertices by definition has vertex-connectivity k-1. This slightly perverse definition ensures that the connectivity is always at most the minimal degree, which is of course at most floor(2e/n). Algebraist 18:11, 24 March 2009 (UTC)

Combinatorics is significantly harder for people who cannot handle counting more than 2 thing or doing simple arithmetic. Ok, with your two corrections to my understanding, I think it makes sense. Then David Eppstein's argument shows how to keep the connectivity high while filling in the rest of the nodes and edges. Ok, all good. The answer to the OP's second question is then simply "because it can't have more than the maximum connectivity," right? Someone else should answer it, as I find most of combinatorics baffling. JackSchmidt (talk) 19:07, 24 March 2009 (UTC)