Mathematics desk
< April 8	<< Mar \| April \| May >>	Current desk >

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

April 9

Minimum number of elements to produce an average

StackOverflow hates me, can you do better? I use a Web site where people vote on songs from 1 to 5 stars (integer). So if I see a score like 3.5, that might be two votes, 3 and 4. Given an overall score, how can I determine the minimum number of votes that could have produced that score? Equinox ◑ 00:33, 9 April 2022 (UTC)[reply]

Write it as a fraction in lowest terms (e.g. 3.5 = 7/2); the denominator is your answer.--2406:E003:858:CA01:24BF:8EA6:3747:8373 (talk) 02:45, 9 April 2022 (UTC)[reply]

That works if the fraction as a decimal fraction is exact. If it was obtained by rounding, that does not work. If the average is shown as 3.14, sure, it could be 157/50, but 22/7 rounded to two decimals is already 3.14. A very simple method is just to try successive denominators till you find one that does the job. So by the time you try 6, compute 6 × 3.14 = 18.84, which is closest to 19. Does that work? Let's see. 19/6 = 3.16666..., which rounds to 3.17. No cigar, so let's move on to the next try. 7 × 3.14 = 21.98, which is closest to 22. Does that work? 22/7 = 3.14159..., which rounds to 3.14. Bingo! Doing this by hand for a number like 3.29166 is not practical, but as a job run on a computer it will take only a millisecond or so. There are algorithms for expressing a real number as a continued fraction, which can be used to find best rational approximations. While more complicated, this may be faster by hand. The last two approximants of the continued fraction expansion of 3.29166 before they are close enough are 23/7 and 79/24. This means the simplest rational takes the form (23 + 79k) / (7 + 24k) for some positive integer k. The value of k needs to satisfy 3.291655 ≤ (23 + 79k) / (7 + 24k) ≤ 3.291665. Since the fraction in the middle equals (79 − 1/(7 + 24k)) / 24, we see that it increases monotonically with k, so we only need to pay attention to the left inequation. Solving this algebraically tells us that k has to be at least 8317/56 = 148.5..., and since k is an integer, we know now that we can take k = 149, which gives us (23 + 79×149) / (7 + 24×149) = 11794/3583 = 3.2916550⁺. So the least denominator that can explain the result 3.29166 is 3583. --Lambiam 08:32, 9 April 2022 (UTC)[reply]

Perhaps simpler: The continued fractions for 3.291655 and 3.291665 are respectively [3,3,2,3,148,1,1,13,2] and [3,3,2,3,1041,2,1,2]. Find the first place where they differ, increase the lower of these two numbers by one, and lop off the rest, giving [3,3,2,3,149] = 11794/3583. —Tamfang (talk) 01:53, 12 April 2022 (UTC)[reply]

Definitely less work, but this needs some refinement or elaboration for the case that one expansion is a prefix of the other. For example, for 3.14063, 3.140625 gives [3,7,9] while 3.140635 gives [3,7,9,48,1,2,1,1,4]. Then the shorter of the two will do if rounding can go either way. Also, due to rounding ambiguity, simpler fractions may occasionally be possible. For example, for 3.69812 this clever method finds 6113/1653 = 3.6981246..., but 5917/1600 = 3.698125 rounded down already produces 3.69812. --Lambiam 09:07, 12 April 2022 (UTC)[reply]

Shuffling sections of students

There are 4 classes of students in grade 1 each containing 30 students. When students are promoted to a higher grade they are shuffled randomly again in 4 sections. Presuming all students are always promoted, and the total count remains the same, by which grade is it guaranteed that for all students any given pair has at some point been in the same grade?

This seems like a problem of block designs to me, but I don't know how to solve it. -- Abdul Muhsy talk 06:25, 9 April 2022 (UTC)[reply]

Did you mean "has at some point been in the same class"? (Also, in presenting something to be mathematically modelled, the use of consistent terminology can reduce confusion, so use either class or section but not both.) If the shuffling is truly random, it could produce, just by chance, the same partition for each next grade as that of the grade before. There needs to be some restriction, which could be that no class has the same composition as any earlier class, or the weaker restriction that the whole partition is different. --Lambiam 08:49, 9 April 2022 (UTC)[reply]

Yes. I meant the same class. I realize now that random shuffling has no guarantee, in the way the problem is posed. Let me pose a different question: how to shuffle the students so that at some grade n any pair has shared a class at some point of time, and how to tell the least such n?-- Abdul Muhsy talk 09:34, 9 April 2022 (UTC)[reply]

I get n=7. Divide students into 8 teams of 15 students and pair them off.

1: AB CD EF GH

2: AC BD EH FG

3: AD BC EG HF

4: AE BF CG DH

5: AF BE CH DG

6: AG BH CE DF

7: AH BG CF DE

.. Modocc (talk) 13:39, 9 April 2022 (UTC)[reply]

There is a somewhat obvious lower bound of

\lceil {\tbinom {120}{2}}/\left(4\cdot {\tbinom {30}{2}}\right)\rceil =5,

and this design establishes

7

as an upper bound. How do we know there is no design formed by a set of

6

partitions? --Lambiam 15:46, 9 April 2022 (UTC)[reply]

I don't know. The new relationships can be increased more rapidly by not grouping them as such. The OP did ask for a guaranteed outcome for some arrangement, so perhaps this one will be useful. Modocc (talk) 19:43, 9 April 2022 (UTC)[reply]

A computer algorithm written by someone who is motivated can certainly brute force minimum class schedules. It would also be less tedious and more robust. --Modocc (talk) 21:50, 9 April 2022 (UTC)[reply]

I'm afraid the running time will be prohibitively large. There are more than 56·10⁶⁶ ways of forming 4 sets of 30 elements each from a given set of 120 elements (T(4,30) in OEIS A060540), which would be about the branching factor in a search tree. Or is there some clever way of pruning the search space? --Lambiam 10:27, 10 April 2022 (UTC)[reply]

Searching all the permutations is unnecessary. For example, the first grade is arbitrary, thus those are not permutated. After that, any remaining groups of complete strangers are not permutated either, but in-groups of friends do form and these can be distributed as evenly as possible across the 4 classes in order to maximize the number of new friendships per grade. Modocc (talk) 12:09, 10 April 2022 (UTC)[reply]

Distributing acquaintances (elements that at some time have shared a block) across different classes is a greedy heuristic like best-first search that may help to find a reasonable solution more quickly but does not guarantee optimality of the first solution found. It may help to prune when the best possible continuation from a node being visited cannot improve on the currently best full solution, but that will not help much in this case. Using the symmetry of anticliques in the acquaintancy graph reduces the number of combinations to be reduced somewhat. But this can only be used for more than one anticlique if they are disjoint and not connected in the acquaintancy graph by an edge, which after the first grade cannot be the case if they are maximal. The size of these anticliques after the first grade is at most 4, so I fear this can offer no more than a reduction by a factor 24 for the number of second grades to be considered, and probably at most 2 for only very few subsequent grades. --Lambiam 14:45, 10 April 2022 (UTC)[reply]

I think I understand what you're driving at, but its not clear to me yet that it matters here, for its not so much a search algorithm, but an optimization program that maximizes the most number of possible new friends for each grade, hence I may have abused the term brute force when I said that above. Each grade is and has to be optimized, for example we have for the first two grades:

1: A B C D -4 new groups of 30 friends, 29 each, at most.

2: A B C D | A B C D | A B C D | A B C D

or:7, 8, 8, 7 | 8,7,7,8 | 8,7,7,8 | 7,8,8,7 -moved 23 from each class, 22 or 23 new friends, at most, for which there is no better shuffle.

Grade 3: A tad too exhausting for me now.

Note that new relations between strangers is factorial, but between any two cliques x and y its only x*y. The program therefore optimizes each grade by shuffling cliques, which on a first approximation, each class happens to be a clique.

--Modocc (talk) 21:13, 10 April 2022 (UTC)[reply]

Diagram of 6 divisions of 120 into 4×30 that tried to put every two together

If the number of students were slightly different, it would be possible to do it in 5 grades: divide the students into 16 equal groups, and assign the classes of each grade based on the finite affine plane of order 4. This is shown in the portion of the diagram within the pink line: in each section, each colour represents a class.

It is not possible to directly make this work for 120 students by adjusting the sizes of the groups while keeping each class at size 30: the corresponding system of equations has a unique solution (with every group size being 7.5). However, this does give a 6-grade solution for 120 students by making the 16 groups have size 7 and adding 4 more groups of size 2, as shown in the full diagram (the grey portion can be assigned arbitrarily). --116.86.4.41 (talk) 14:46, 13 April 2022 (UTC)[reply]

Correction: I have realised that it isn't actually a 6-grade solution, failing to pair the top-left large group with three of the small groups. --116.86.4.41 (talk) 13:21, 14 April 2022 (UTC)[reply]