Page 57 of 57 FirstFirst ... 747555657
Results 841 to 855 of 855
  1. #841
    Reader in Slood Dynamics Rincewind's Avatar
    Join Date
    Jan 2004
    Location
    The multiverse
    Posts
    21,567
    I have an idea:

    It seems to be P = (p-q)/(p+q). My argument is messy though.
    Imagine there is a hidden sequence of voting which is randomly selection but effectively fixed, then the problem is selecting a starting point which doesn't lead to as many (or more) B votes coming out before A votes. If B's are sparsely distributed (no two consecutive B votes) then you just don't want to start at the B vote or at the the A vote immediately before it. There are p-q of these non-leading A votes and so that gives the proposed formula. When B votes are non-sparse (say there are two B votes in a row) then you just want to avoid the two leading A votes as your starting point. So the result would seem to be robust for the non-sparse case and I would argue general for any distribution. But I'm sure there must be a much cleaner combinatorial argument.
    So einfach wie möglich, aber nicht einfacher - Albert Einstein

  2. #842
    CC Grandmaster Redmond Barry's Avatar
    Join Date
    Aug 2008
    Location
    Westside
    Posts
    3,118
    I have a cold:

    Theres no hidden message here, I really do have a cold. Oh, better make this math related to be on topic. Here goes. If Capa-fan posts in the Politics thread every day for a full year but forgets to spew furious invective on one of those days, how many people are going to rejoice ?
    Ruin is formal, devil's work,
    Consecutive and slow -
    Fail in an instance no man did,
    Slipping - is Crash's law,

  3. #843
    Monster of the deep Kevin Bonham's Avatar
    Join Date
    Jan 2004
    Posts
    37,384
    Rincewind is correct. The result is known as Bertrand's Ballot Theorem and a number of different proofs exist:

    https://en.m.wikipedia.org/wiki/Bert...ballot_theorem

    Here is an extension to a case where A receives at least k times B's tally:

    http://www.math.unl.edu/~sdunbar1/Pr...ottheorem.html

    Oddly, I can't find an extension to a count involving three candidates. Maybe the formula is so disgusting nobody wanted to publish it.

  4. #844
    Reader in Slood Dynamics Rincewind's Avatar
    Join Date
    Jan 2004
    Location
    The multiverse
    Posts
    21,567
    Quote Originally Posted by Kevin Bonham View Post
    Oddly, I can't find an extension to a count involving three candidates. Maybe the formula is so disgusting nobody wanted to publish it.
    For three I think it is...

    P = (p-q-r+q*r*(1/(p+q)+1/(p+r)))/(p+q+r)

    Very similar to the 2 candidate case except you have a correction term in the numerator of q*r*(1/(p+q)+1/(p+r)) which arises from the situation of the two losing candidates receiving consecutive votes effectively requiring just one leading A vote and not two. You might want to test it out with some numerical trials as I might have made a mistake. Actually I'm a bit worried since my formula is positive for 2, 2, 1 which should be zero. So the correction term is not quite right.


    Edit:

    OK I think it is actually...
    P = (p-q-r+2*q*r/(p+max(q,r)))/(p+q+r)
    this certainly equals zero whenever q or r equals p which is an improvement and also seems to work for the small p,q,r cases I can work out quickly. It would be interesting to try out more difficult cases numerically. EG for q = r = p/2 then P is always 1/6.
    So einfach wie möglich, aber nicht einfacher - Albert Einstein

  5. #845
    Reader in Slood Dynamics Rincewind's Avatar
    Join Date
    Jan 2004
    Location
    The multiverse
    Posts
    21,567
    Actually both equations above are wrong. I don't have a formula for the case I was looking at but the nicer case is this...

    If you have an election with three candidates where A gets p votes B received q votes and candidate C received r votes, such that p > q > r. Then what is the probability that p > q and q > r all the way through the voting process (assuming no two votes are lodged simultaneously). Obviously all tallies start at zero but you only check the p > q every time a vote for B is lodged and q > r every time a vote for C is lodged.

    There does appear to be a simple formula for this. You can also generalise pretty easily to N candidates.
    So einfach wie möglich, aber nicht einfacher - Albert Einstein

  6. #846
    CC Grandmaster Capablanca-Fan's Avatar
    Join Date
    Jan 2004
    Posts
    19,310
    Mathematicians Measure Infinities and Find They’re Equal:
    Two mathematicians have proved that two different infinities are equal in size, settling a long-standing question. Their proof rests on a surprising link between the sizes of infinities and the complexity of mathematical theories.
    Kevin Hartnett, Quanta, 12 Sept 2017

    [The heading is slightly misleading. Their work wasn't saying that all infinities are equal; they were not denying that ℵ1 really is greater (has higher cardinality) than ℵ0. As the article says, Cantor proved that. The work of Malliaris and Shelah showed that IF there were any numbers between those two (i.e. the continuum hypothesis is false), they would have to be equal to each other.]
    “If Algeria introduced a resolution declaring that the earth was flat and that Israel had flattened it, it would pass by a vote of 164 to 13 with 26 abstentions.” — Abba Eban on the UN general assembly

    “You will never find a more wretched hive of scum and villainy. We must be cautious.” — Obi-Wan Kenobi on the UN kakistocracy

  7. #847
    Reader in Slood Dynamics Rincewind's Avatar
    Join Date
    Jan 2004
    Location
    The multiverse
    Posts
    21,567
    Quote Originally Posted by Capablanca-Fan View Post
    Mathematicians Measure Infinities and Find They’re Equal:
    Two mathematicians have proved that two different infinities are equal in size, settling a long-standing question. Their proof rests on a surprising link between the sizes of infinities and the complexity of mathematical theories.
    Kevin Hartnett, Quanta, 12 Sept 2017

    [The heading is slightly misleading. Their work wasn't saying that all infinities are equal; they were not denying that ℵ1 really is greater (has higher cardinality) than ℵ0. As the article says, Cantor proved that. The work of Malliaris and Shelah showed that IF there were any numbers between those two (i.e. the continuum hypothesis is false), they would have to be equal to each other.]
    It is somewhat annoying that the article contained a bunch of irrelevant stuff on Cantor and yet does not specify in any real detail what p and t are in a way that a non-specialist could understand. There is a sidebar which contains a lot of set theory jargon but that doesn't help a non set theorist. My reading of Hartnett's article is that the proof showed p and t had equal cardinality, and we already knew that their cardinality was larger than aleph-0 and that p was no larger than t Their proof doesn't greatly impact on the question of the continuum hypothesis as much as a proof of different cardinality would. The implications weren't general as far as I can tell. There still may be one or more cardinalities between the countable and the continuum.
    So einfach wie möglich, aber nicht einfacher - Albert Einstein

  8. #848
    Reader in Slood Dynamics Rincewind's Avatar
    Join Date
    Jan 2004
    Location
    The multiverse
    Posts
    21,567
    Quote Originally Posted by Rincewind View Post
    If you have an election with three candidates where A gets p votes B received q votes and candidate C received r votes, such that p > q > r. Then what is the probability that p > q and q > r all the way through the voting process (assuming no two votes are lodged simultaneously). Obviously all tallies start at zero but you only check the p > q every time a vote for B is lodged and q > r every time a vote for C is lodged.

    There does appear to be a simple formula for this.
    Solution:

    This is the nice version of the problem the formula is P = (p-q)(p-r)(q-r)/[(p+q)(p+r)(q+r)], For N candidates you just build a set of terms. eg for four candidates P = (p-q)(p-r)(p-s)(q-r)(q-s)(r-s)/[(p+q)(p+r)(p+s)(q+r)(q+s)(r+s)], and so on.
    So einfach wie möglich, aber nicht einfacher - Albert Einstein

  9. #849
    Monster of the deep Kevin Bonham's Avatar
    Join Date
    Jan 2004
    Posts
    37,384
    My partner's mother and I both have birthdays early in the year meaning that very soon I will be 46 (born in '72) while she will be 72 (born in '46). This situation will then last nearly all the year, but had either of us been born in late December instead, it would only have lasted a few days.

    For two people born in years of the form 100x+a and 100x+b, where a and b are between 0 and 99 inclusive, this situation occurs in the year 100x+a+b. However, people born in different mathematical centuries (counting a century as starting with 00) have to wait til one of them is at least 100 before it only sort-of comes up - if two people are born in 1999 and 2001, in 2100 the one born in '01 will be 99 and the one born in '99 will be '01 (101).

  10. #850
    Monster of the deep Kevin Bonham's Avatar
    Join Date
    Jan 2004
    Posts
    37,384
    I had a real-life mathematical problem which goes something like this.

    A Jetstar bagdrop queue contains 50 passengers of which you are number 25 in the line. Your flight was originally due to leave in 1 hr 40 minutes but has been delayed to leave in 2 hours 20 mins. Jetstar can clear about two passengers per minute from the front of the queue, but new passengers are arriving in the queue at an average rate of about 2.5 per minute. The counter staff announce that only passengers whose flights leave in a maximum of two hours are to drop off bags because of the need to process passengers quickly. You don't know whether or not this applies to passengers whose flights were originally to leave within two hours but have been delayed.

    Assuming that:

    * your bag will definitely be accepted if you reach the head of the queue a maximum of two hours before your revised departure time
    * if you arrive earlier than that, there is a 50% chance your bag will be accepted and a 50% chance you will be sent to the back of the queue
    * you cannot allow other passengers in the queue to overtake you, or move to a position in the queue other than the back, because this behaviour might appear suspicious
    * moving to the back of the queue from where you at the start takes effectively no time, but if you are sent to the back of the queue after arriving at the front that will take a minute (including the conversation that results in you being sent there)

    ... is it better, in order to minimise average time in the queue, to remain in the queue or to voluntarily move to the back of it right away?

    (I actually decided to remain in the queue because I was more interested in finding out whether they would accept me - which they did - than in minimising time spent in the queue.)

  11. #851
    CC Grandmaster road runner's Avatar
    Join Date
    Apr 2006
    Location
    on the skin of the pale blue dot
    Posts
    12,272
    Quote Originally Posted by Kevin Bonham View Post
    I had a real-life mathematical problem which goes something like this.

    A Jetstar bagdrop queue ...
    meep meep

  12. #852
    CC Grandmaster Capablanca-Fan's Avatar
    Join Date
    Jan 2004
    Posts
    19,310

    Old Babylonian tablet: exact sexagesimal trigonometric table based on ratios

    Daniel F. Mansfield and N.J. Wildberger
    Plimpton 322 is Babylonian exact sexagesimal trigonometry
    Historia Mathematica 44(4):395-419, November 2017 | doi:10.1016/j.hm.2017.08.001

    Highlights
    • Plimpton 322 contains a fragment from a proto-trigonometric table.
    • The Babylonians discovered exact sexagesimal trigonometry at least 1500 years before the ancient Greeks discovered trigonometry.
    • Babylonian exact sexagesimal trigonometry uses exact ratios and square ratios instead of approximation and angles.

    Abstract

    We trace the origins of trigonometry to the Old Babylonian era, between the 19th and 16th centuries B.C.E. This is well over a millennium before Hipparchus is said to have fathered the subject with his ‘table of chords’. The main piece of evidence comes from the most famous of Old Babylonian tablets: Plimpton 322, which we interpret in the context of the Old Babylonian approach to triangles and their preference for numerical accuracy. By examining the evidence with this mindset, and comparing Plimpton 322 with Madhava's table of sines, we demonstrate that Plimpton 322 is a powerful, exact ratio-based trigonometric table.
    “If Algeria introduced a resolution declaring that the earth was flat and that Israel had flattened it, it would pass by a vote of 164 to 13 with 26 abstentions.” — Abba Eban on the UN general assembly

    “You will never find a more wretched hive of scum and villainy. We must be cautious.” — Obi-Wan Kenobi on the UN kakistocracy

  13. #853
    Monster of the deep Kevin Bonham's Avatar
    Join Date
    Jan 2004
    Posts
    37,384
    A group of n people, where n is an even number >2, are seated at two proverbial dinner tables, each of which has n/2 seats. After some time we rearrange them by having a number of them swap places with the same number from the other table. Then later we do this again (the number swapped doesn't have to be the same every time, but the end result of each swap must always be two new groups of n/2). What is the minimum number of rearrangements - irrespective of how many people are moved each time - that must be performed to ensure that every pair of people from the group has been together at a table at least once?

    Example: n=10. The initial groups are (1,2,3,4,5) and (6,7,8,9,10). After the first swap they new groups might be (1,2,6,7,8) and (3,4,5,9,10). Now 1 has been at the same table with everyone except 9 and 10, so we need at least one more swap to ensure 1 has been at the same table as 9 and 10. Can we do it with one more swap or will we need more?

    (If I'm right this problem is actually quite easy to solve for all even n>2.)
    Last edited by Kevin Bonham; 12-06-2018 at 10:50 PM.

  14. #854
    Monster of the deep Kevin Bonham's Avatar
    Join Date
    Jan 2004
    Posts
    37,384
    Solution in white:

    Two swaps if n is a multiple of 4, three swaps otherwise.

    First consider the trivial case n=4. As each table has two seats and each person can only be seated with one other at a time, it will obviously take two swaps, ie (1,2)+(3,4), (1,3)+(2,4), (1,4)+(2,3)

    For higher n, firstly one swap will never suffice since a given person will always have n/2 others who they did not share a table with on the first rotation, but it is not allowed to have 1+n/2 people together on one table.

    However, if n is a multiple of 4, we can simply divide the guests into four equally sized groups and reproduce the solution for n=4. Therefore two swaps is both necessary and sufficient for all such cases.

    Where n is not a multiple of 4, n/2 is odd. From the original rotation, no matter how many guests are moved, the next rotation at a given table will contain m guests who will now share a table with n-m guests who they had not previously shared with, and vice versa, for some value of m.

    Because n/2 is odd, either m>n/4 or n-m>n/4. It's irrelevant which it is so let's assume m>n/4.

    On this basis there are m guests at each table who have not yet shared a table with m guests on the other table. But for both groups of m guests to have shared a table with every other guest following the second exchange, that would require putting 2m guests together on a table, which is not allowed because 2m>n/2. Therefore two exchanges is insufficient.

    However three exchanges is sufficient because we can pick any two guests and allocate them to opposite tables for the first three rotations, apply the solution for a multiple of four to the remainder, and then apply any exchange that assigns these two guests to the same table.


    As that was too easy the obvious extension is to p dinner tables each with n/p guests, where n is some multiple of p. This could then be further divided into various swapping rules (ie can totally rearrange everyone in one go vs can only swap between two tables at a time).

    The National Mathematics Summer School which I attended as a teenager (1988?) could have allocated students at its last-night dinner using a problem such as this, but didn't, possibly because the number of students was prime. Instead students moved between seats between courses following modular arithmetic instructions in a way that was preplanned to land all the numerous romantic couples who had developed in the course of the NMSS next to each other after the final rotation.

  15. #855

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •