Mathematics desk
< September 5	<< Aug \| September \| Oct >>	September 7 >

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.

September 6

Lottery games similar to australia's "soccer pools"

I, like many people, dream of striking it rich in the lottery. Most of the games are ones of pure chance, with far-fetched odds and low expected value. The one exception I've noticed here in australia is the "soccer pools".

For those unaware, this game is essentially a 6-from-38 lottery - except that the numbers aren't random, but are selected based on the results of the week's match list. Like the lottery, the top prize jackpots if there are no winners. Given that the winning numbers are essentially based on draws, not wins, the idea, as I see it, is mostly to eliminate the lopsided games. Football can be unpredictable... which is why most weeks, no one wins top division.

Anyways, my question is: Can anyone point me to similar games in other sports? I believe TAB run a somewhat similar aussie rules competition. Do any similar "pools" games exist in either the rugby codes, cricket, netball, hockey or basketball? Include online games based abroad. Eliyohub (talk) 05:09, 6 September 2011 (UTC)[reply]

Hungary has similar national soccer pool called hu:Totó. (This does not answer your question because you asked for other sports.) You have to guess one of three choices for each of the fourteen matches selected this week: home team wins, guest team wins, draw. The winning categories are correctly guessing ten, eleven, twelve, thirteen matches out of the first thirteen matches, and the highest jackpot is for correctly guessing all fourteen matches. As the difficulty of this depeds a lot on the matches chosen, very often nobody guesses all thirteen right, and occasionally nobody gets a twelve either, but there are weeks when tens of people must share the highest class jackpot (all fourteen matches). There are other national sports betting games, but as far as I know, Totó is the only one that works like a lottery pool in that a ratio of the income is shared among the winners and there is a growing jackpot pool if nobody wins. – b_jonas 07:33, 6 September 2011 (UTC)[reply]

Correction. The game is not weekly: sometimes there are more than one rounds for a week. – b_jonas 07:35, 6 September 2011 (UTC)[reply]

Conjugacy class?

How can I deduce the size of the conjugacy class of　　 ${\frac {1}{2}}+{\frac {\sqrt {3}}{2}}k$ 　　in the quaternion subgroup 　　 $\{\pm 1,\pm i,\pm ({\frac {1}{2}}\pm {\frac {\sqrt {3}}{2}}k),\pm ({\frac {1}{2}}i\pm {\frac {\sqrt {3}}{2}}j)\}$ 　　(the rotation symmetries of an equilateral triangle, with twelve elements in total)? Fundamental homomorphism theorem perhaps? Thanks. Brirds (talk) 05:38, 6 September 2011 (UTC)[reply]

I'm more used to working with generators and relations so with

u=i,v={\frac {1}{2}}+{\frac {\sqrt {3}}{2}}k

, relations are v⁶=1, u²=v³, vu=uv⁵. The conjugacy classes then work out to {1}, {v³}, {v,v⁵}, {v², v⁴}, {u, uv², uv⁴}, {uv, uv³, uv⁵}.--RDBury (talk) 06:58, 6 September 2011 (UTC)[reply]

Thanks. Is it possible to deduce, directly from the rules of quaternion operations, the size of this conjugacy class without performing conjugations? The inverse of　

{\frac {1}{2}}+{\frac {\sqrt {3}}{2}}k

　in this group (which is also the other element in this conjugacy class) is　

{\frac {1}{2}}-{\frac {\sqrt {3}}{2}}k

　, and there are four elements in this group　

\pm ({\frac {1}{2}}\pm {\frac {\sqrt {3}}{2}}k)

　with order = 4. Is there a reason why the other two elements cannot be in this conjugacy class? Brirds (talk) 07:37, 6 September 2011 (UTC)[reply]

Never mind. I've found the solution. Thanks. Brirds (talk) 10:27, 6 September 2011 (UTC)[reply]

Tile stacking

The following is ultimately a computational problem, but I suspect this board is a bit better suited to it.

Let $A(x_{0},\,y_{0};\,x_{1},\,y_{1})$ denote the set in the real plane of all points (x, y) such that $x_{0}\leq x\leq x_{1}{\text{ and }}y_{0}\leq y\leq y_{1}$

Given a set of N such tiles, $A_{i}$ , defined by the coordinates $(x_{i,0},\,y_{i,0};\,x_{i,1},\,y_{i,1})$

Let C(x, y) denote the total number of tiles that include the point (x, y), and further let $M_{i}$ denote the maximum value of C(x, y) for any location (x, y) within $A_{i}$ .

We define the intersection set F on the $A_{i}$ to be the collection of points (x, y) such that for every (x, y) there exists a least one tile $A_{i}$ such that (x, y) is in $A_{i}$ and C(x, y) = $M_{i}$ .

This intersection set can itself be described by at most N tiles having coordinates $(a_{i,0},\,b_{i,0};\,a_{i,1},\,b_{i,1})$ .

Now for the question...

I am looking for an efficient algorithm to find the set $(a_{i,0},\,b_{i,0};\,a_{i,1},\,b_{i,1})$ given $(x_{i,0},\,y_{i,0};\,x_{i,1},\,y_{i,1})$ . In the limiting cases where the tiles are completely disjoint or completely nested it is fairly simple. However, when one has multiple partial overlaps it seems to get tricky pretty quickly. I'm hoping that there is some relatively simple recursive approach that might lead to an answer. In case there is any doubt, this is not a homework question. Dragons flight (talk) 13:05, 6 September 2011 (UTC)[reply]

Is it sufficiently efficient to store a list (initially empty) of (tile,count) pairs, and then add each tile as (tile,1) and also calculate its intersections with all existing tiles and store them as (intersection,count+1)? (Then obviously loop over the list at the end to collect those with the highest count.) If there are "few" intersections this is

O(N^{2})

, which I'm sure is optimal. If there are many intersections, I don't know what the bound is on the number of intersections you can create, but I don't think it's exponentially many (for rectangles). --Tardis (talk) 03:39, 9 September 2011 (UTC)[reply]

Actually, it seems it is exponential, at least for some patterns — I drew rectangles with integer lower-left corners and dimensions each drawn from

[0,2^{16})

, and by the 126th tile I had 42906214 total tiles created. Still, this might work if you have only a few dozen tiles or if they overlap more simply. --Tardis (talk) 06:46, 9 September 2011 (UTC)[reply]

Computer programmer here. I can't understand the problem written in mathese like that, can you state it in English, please ? (Yes, this is the Math Desk, but this question is a bit of both, and I may be able to contribute.) StuRat (talk) 04:20, 9 September 2011 (UTC)[reply]

Simply put, we have a set of rectangles and we wish to identify the set of points (which is itself the union of a set of rectangles) that are in the maximum number of input rectangles. (There may be a tie among various widely separated (sets of) points.) --Tardis (talk) 07:24, 9 September 2011 (UTC)[reply]

That's not exactly what we're looking for, as I understand it—we're trying to find, for each rectangle R, the set of points in R that are contained in more rectangles than any other points in R. They might not be contained in as many rectangles as some other points that are not in R, but we still want to find them. —Bkell (talk) 11:32, 9 September 2011 (UTC)[reply]

Oops — I failed to parse the definition of

M_{i}

and decided it was global. Then I should add "among the points in some input rectangle that contains them", right? (And note that ties also apply per-input.) --Tardis (talk) 12:37, 9 September 2011 (UTC)[reply]

OK, then the next question is if there are a small, finite number of "points". That is, if we have a finite range, say 10 units in each direction, and a finite resolution of, say, 0.1 units in each direction, leading to 100×100 or 10,000 possible points, then we could take the approach of testing every point to determine the number of rectangles in which it lies.

However, if we are dealing with an infinite number of points or a large, finite number (say a trillion), then this approach won't work in all cases. However, we could still use this method as a "polling" approach, hoping to hit the "sweet spot". In such a case we would need to calculate the probability that any given number of test points would hit that spot, and decide if that's the best approach or if we need to use more CPU time to ensure the exact solution.

Note that if you assume that, using the "polling" method, the polling point in the largest number of rectangles is probably near the actual point in the largest number of rectangles, then you could define a tighter grid, with a smaller increment, centered on that polling point, and thus improve accuracy with each iteration, in that manner. StuRat (talk) 16:34, 9 September 2011 (UTC)[reply]

About a trillion is actually the right ballpark. With some intelligence that can probably be improved upon, but I think sampling would still be way, way too slow, especially since a low error rate is important. Dragons flight (talk) 18:44, 9 September 2011 (UTC)[reply]

I agree that sampling a trillion points would be way too slow, but sampling a million, then determining which grid square is best among those (and sampling a million points within that grid) should give you the same resolution, but be much quicker. Or we could do 100 sample points with 6 iterations. Just what are the numbers you're working with, as far as ranges for X and Y of the "universe", number of rectangles we need to check against, and the acceptable error rate ? If you have some sample data, I'd like to give my approach a try against it. StuRat (talk) 01:38, 10 September 2011 (UTC)[reply]

After some hours of working on this I think I have a solution that is good enough. $O(N^{3})$ unfortunately, but that's probably the best one can expect. Given any collection of tiles, I can solve the problem while considering at most $(2N-1)^{2}$ non-overlapping rectangular regions. I'm also sure that this is still pretty far from the best possible solution, but it seems to be good enough for the cases I have to work with. Dragons flight (talk) 11:36, 9 September 2011 (UTC)[reply]

Well, let's hear it! The fact that you call them non-overlapping suggests that you might be you parsing each intersecting pair into up to 5 disjoint rectangles (the intersection and each side of the "v" on each side), although I'm not sure how that handles degenerate tiles. --Tardis (talk) 12:37, 9 September 2011 (UTC)[reply]

Collect all your X's and all your Y's. Sort each list. Now tile the space with the non-overlapping tiles

(x_{i},\,y_{j};\,x_{i+1},\,y_{j+1})

. Assuming you have no repeat X or Y then that's

(2N-1)^{2}

tiles. For each of these, count the intersections with each of the original N rectangles. Look at the counts to find the ones that match the solution. Dragons flight (talk) 18:53, 9 September 2011 (UTC)[reply]

No need to pre-sort them. For example, if I only cared about X, I would go through each X and count how many of each one there are. As I do so, I perform an insertion sort (I'd use a binary tree). I have a list of every X used and a count of how many rectangles use each X as a corner. Then, for each rectangle, add 1 to each X in my list that is between the corner X's. Overall, you'd get that done in

O(nlogn)

. The side-benefit of the tree is that you can functionally increment an entire branch if you wanted to, but that blurs the difference between the theoretical algorithm complexity and the actual program's complexity. -- kainaw ™ 19:01, 9 September 2011 (UTC)[reply]

At least one of us is confused. Quite possibly me. I don't see how looking at just the X's helps you since whether or not a pair of rectangles has an overlap region will also depend on the Ys. For example (0, 0; 2, 2) will overlap (1, 1; 3, 3) but not overlap (1, 3; 3, 7). Dragons flight (talk) 19:18, 9 September 2011 (UTC)[reply]

I was ignoring the Y's just to make it easier to point out that pre-sorting was not necessary. As you check the X's, you can do a sort. -- kainaw ™ 19:21, 9 September 2011 (UTC)[reply]

I'm not really worried about the sort. The limiting factor for me is seeing how O(N^2) regions are overlapped by O(N) original tiles, giving O(N^3). There are probably smart ways to structure the search to cut that down. Maybe you've even explained what they are, but I'm having trouble figuring it out right now. (And I'm not entirely sure it is worth the effort to do so, since O(N^3) seems okay.) Dragons flight (talk) 19:29, 9 September 2011 (UTC)[reply]

Correct. Much of this will depend on the structures used. If done properly, it can be very quick (compared to doing it improperly). Further, the proper structures will allow for parallel processing, making it all run even faster. I've simply tried to be very vague about structures since this isn't the computer desk and the question was about the algorithm, not the implementation of it. -- kainaw ™ 19:34, 9 September 2011 (UTC)[reply]

From just a cursory look (assuming I understand the task correctly), first just look at the X's. For each X, ~~count how many rectangles contain (have the corner or overlap) that X~~ (struck - you don't need this count, just a list of X's). Once you have a set of X's and counts for each X, you know that the resulting rectangle will have corners at two of the X's (or one X if the max stack is a single point). For each X, look at the Y's. If you structured your algorithm well, you know exactly which rectangles overlap each X. Count how many rectangles are at each of the Y's, creating a big list of (x,y) coordinates with a count of how many rectangles contain each coordinate. Keeping a running tab of the highest count will make it easy to spit out the coordinates with the highest count (you may even get more than one rectangle). You can do the count of X's in linear time: O(n). You can do the Y's in linear time per X. So, worst case is

O(n^{2})

. -- kainaw ™ 18:35, 9 September 2011 (UTC)[reply]

BTW, are the sides of all these rectangles (including "the universe") parallel to the X and Y axes ? StuRat (talk) 21:26, 10 September 2011 (UTC)[reply]

Motivation to study mathematics

What could be a few motivating reasons to study pure and applied mathematics? --LijoJames (talk) 15:26, 6 September 2011 (UTC)[reply]

The end of our civilization, in fact the end of time is staved off by the block transfer caalculations of mathematicians. In fact it really isn't all too far off that, most of the mathematics you use in everyday life is hidden from you but is encoded in computer algorithms. When you play a CD, when you look at the internet, when you use GPS, when you make a mobile phone call - each of those depends on mathematics encoded into the devices. The right amount of food is delivered to the supermarket using mathematics. Buildings and cars are made safe using engineering calculations. Drugs are tested using mathematics.

That's just a part of the practical uses of mathematics. However if it does not strike any spark in you I would not suggest waste time learning it. There are enough other people interested enough to not need everyone doing it. Personally I think people who just admire a flower are missing more than half the beauty by not appreciating the ecology behind it. The imagery of the film The Matrix illustrates what it is to live through life without seeing the mathematics around you. Dmcq (talk) 15:54, 6 September 2011 (UTC)[reply]

Are "block transfer caalculations" normally studied in Afrikaans instead of English ? :-) StuRat (talk) 22:57, 6 September 2011 (UTC)[reply]

The most common motivating reason for studying mathematics is when it's required to get a college or university degree. – b_jonas 20:21, 7 September 2011 (UTC)[reply]

I did it as a degree, because *shock - horror*, I enjoyed it. I found it easy, liked the fact there was a definitive answers (none of these wishy washy essay things, where you got more marks if you think like the marker) and because it gave me an analytical way of thinking. That's just me though Worm^TT · (talk) 08:44, 8 September 2011 (UTC)[reply]

Dispersion formula

250 sheep could be anywhere within an area of x square metres. I want to know the probability of each sheep being within a small y square metre area of those x square metres. How can I work this out?--178.167.211.239 (talk) 18:15, 6 September 2011 (UTC)[reply]

Isn't it just y/x? Are you sure you asked the question you intended to ask? Looie496 (talk) 18:36, 6 September 2011 (UTC)[reply]

We don't know the level the OP is working at. They've clarified the answer once, so I'm thinking that's what they mean – perhaps we should wait and see if they want another or further explanation. Grandiose (me, talk, contribs) 18:40, 6 September 2011 (UTC)[reply]

If you're curious about some of the complexities that might come up, these are because there's no reason to assume that sheep are distributed randomly in a field. I'd expect them to clump together in groups, especially near food and water. So, if you knew where all the other sheep were, accurately coming up with the probability of where the 250th sheep is would be quite complex. And this might be just the type of problem a shepherd would face, say when the vet comes to check out his ailing (but still mobile) sheep. StuRat (talk) 22:49, 6 September 2011 (UTC)[reply]

The probability depends on data. If you don't tell us all you know then our answer will not be correct. You don't tell us that any area is distinguished from any other area except that you know the size y. So the probability of each sheep being within a small y square metre area of those x square metres is p=y/x. The number of sheeps within a small y square metre area of those x square metres is 250p, give or take

{\sqrt {250p(1-p)}}

. See our article on the binomial distribution. Bo Jacoby (talk) 14:50, 7 September 2011 (UTC).[reply]

The answer also depends on the predator threat level perceived by the sheep. For a low threat level, the sheep usually spread out almost randomly, assuming an even distribution of grass (water is low priority because sheep spend little time drinking). There is always a slight tendency to remain within sight of close family members, but this counteracts the tendency to spread evenly to maximise food availability. The answers given above are for random sheep. In a situation of high predator threat, they will flock closely together away from the threat but also away from boundaries where they might get trapped. Dbfirs 17:22, 10 September 2011 (UTC)[reply]