Combinatorics

[indigo island]

what have you tried?

[viral sapphire]

Total number of distinct pairs = 15C2 = 105 pairs
each group of 5 creates pairs, 5C2 = 10 pairs
Maximum number of groups = 105 / 10 = 10.5 ≈ 10
the exact answer needs to be 7

[indigo island]

groups of 5 are formed
how many groups of 5?

the final answer is supposed to be 7?

i really cannot make sense of the question if the answer is supposed to be 7

[queen anvil]

does it make sense if those groups are formed simultaneously?

(sorry for jumping in.)

[indigo island]

don’t worry you are welcome here

[viral sapphire]

The question is asking you to form as many groups of 5 students as possible from a total of 15 students, with two conditions: first, a student is allowed to appear in multiple groups (so people can repeat), but second, and this is the key rule, no pair of students should ever appear together more than once across all the groups. In simple terms, if two students have already been in the same group once, they are not allowed to be together in any future group. Your task is to figure out the maximum number of such groups you can create while strictly following this rule.

and about the answer i don't strictly know it's seven but it's definitely less than 9

[indigo island]

oh ok i understand now

[viral sapphire]

Pardon, could you please ask more clearly?

[indigo island]

it’s not about how many possible assignments there are. it’s about what the largest number of groups possible for an assignment is (which i don’t think was clear from the original but i digress)

[viral sapphire]

Yes

[queen anvil]

never mind, I don't think my idea leads anywhere. sorry to have bothered.

[viral sapphire]

No worries, you can share

[queen anvil]

hm, I cannot find a way to construct more than 3 of these groups.

[indigo island]

1,2,3,4,5
1,6,7,8,9
2,9,10,11,12
3,6,13,14,15

[queen anvil]

if I label the students from A to O, then
[ABCDE] [FGHIJ] [KLMNO]
are the initial groups.
but after this, each group must have students from different initial sets, but there are only three of them.

or was it a bad idea to start with disjoint groups?

[indigo island]

you can get more than 3 starting with not disjoint groups

but i'm still skeptical of 7

[queen anvil]

hm. in that case...

[indigo island]

or maybe that is right

hmm

[queen anvil]

7 seems to be impossible (speculated, not a solution).

[indigo island]

after 3 groups are formed, there are at most 3 unused people left

seems difficult to get to 7 groups from there

[queen anvil]

I was thinking of it another way.

not sure if this helps, but I think that a student appearing more than once links the groups they appear in pairwise.
that is, suppose A appears in groups 1, 4, 7. then the pairs of groups linked are 1 and 4, 1 and 7, and 4 and 7.

this should mean that no two students can link the same two groups together.

[indigo island]

i know where this is going and i agree

[queen anvil]

(SPOILERS!)
||the number of distinct pairs of groups is 7C2 = 21. with seven groups, there will thus be 35 student appearances.||
||then, we want to minimize the number of pairs of groups linked by every student, which amounts to minimizing and spreading the number of appearances per student.||
||for 15 students, the most even spread is five 3s and ten 2s, but that gives 5(3C2) + 10(2C2) = 15 + 10 = 25 group-pairs, 4 more than the 21 allowed.||

please let me know if this is considered a solution, I'll scramble some things up if necessary.

[indigo island]

hm what is the significance of five 3s and ten 2s?

[queen anvil]

||five students will appear in 3 groups and the other ten in 2.
this even spread is to reduce the number of group-pairs they contribute (as nC2 grows faster the larger n is), so the minimum total group-pairs happens when the number of appearances are evenly spread across the 15 students.||

(again, please let me know if it is safe to unspoiler, since I see this as potentially solution-revealing.)

[indigo island]

what about like one 3 and sixteen 2s?

[queen anvil]

there aren't 17 students, and we need the number of appearances to total to 35.

[indigo island]

i see

[queen anvil]

we could do something like, say, five 4s, five 2s, and five 1s, which does indeed make 35 appearance, but assuming this arrangement is even somehow possible, we'd get 5(4C2) to be 30 group-pairs already.

[indigo island]

there also can't be any 4s because if e.g. 1 shows up in 3 groups, there are at least 12 other numbers that can't go with it in a group anymore

[queen anvil]

right, and there's that too.

(disclaimer to OP: I may be very wrong! I am not at all good at combinatorics, so take my words with a sea of salt!)

[indigo island]

no you're doing great

[queen anvil]

anyway another way of arranging is possibly ten 3s and five 1s, but that would also give 10(3C2) = 30 group-pairs already, let alone the remaining 5.
so for an exercise in ||minimizing the number of group-pairs|| this is probably not the best candidate arrangement.

(I am also not sure this arrangement is possible.)

but then again, the impossibility of these arrangements are themselves quite the answer to what's going on here, so maybe it is?

[indigo island]

||the only solution to
x + y = 15
3x + 2y = 35
is (5,10) so that should settle the appearance numbers||

[queen anvil]

oh! that... was quite the approach that my brain had somehow missed.

[indigo island]

yea i was a little confused what you were trying to optimize 😭

it's ok though

[queen anvil]

I was trying to reduce the number of times any student appears in groups, because the more times a student appears in a group the more restrictive any future solution involving them is, intuitively.
(I am sure I am horribly wrong here though.)

[indigo island]

one mutual friend towa, the self deprecation sure checks out

[queen anvil]

and again, I believe that no two students can link the same pair of groups together, because that would mean that they have both shown up in the same pair of groups, which is against the rules.

[queen anvil]

anyway I think I may have said too much without OP's input, so I will wait for OP to respond.

[faint moss]

1,2,3,4,5
1,6,7,8,9
1,10,11,12,13
2,6,10.14.15
3,7,11,14,12
4,8,13,15,9
5,12,14,7,9

[snow silo]

math makes you do that ._.

[faint moss]

i tried ur way , can u check errors or any other possible pair

[indigo island]

11,12 shows up twice

in groups 3 and 5

[faint moss]

oh yeah

[indigo island]

i am pretty sure 7 is impossible as per chiaki's solution

[queen anvil]

groups 2/7 have 7 and 9.
groups 5/7 have 12 and 14.
groups 5/7 have 7 and 12.
groups 5/7 have 7 and 14.

and I think it ties back quite nicely to my numbers: ||4 extra group-pairs||.

oh wait there's more as well. then maybe not.

[indigo island]

there was also 11,12 repeated

[queen anvil]

I missed that one. my bad.

[faint moss]

yup that was a disaster

[snow silo]

okay I probably made a mistake here but I think the max is four? proof: ||if there were three groups, then if they were all disjoint then you couldn’t make a fourth since all the students are used up and creating another one would cause an overlap of > 2 by pigeonhole.
suppose two groups share a student, and the third is disjoint, then again, this means there’s one student who isn’t in any group but you could only pick one from each the three original groups so that wouldn’t work either.
the only case that works if all groups share one student. there’s 5*3 - 2 =13 students used up so there’s 2 free students. adding these two to one group from each of the other three groups makes the maximum four. if you wanted to make a fifth, you can only take 1 from each of the four groups but there are no free students remaining so you can’t make another one||

[queen anvil]

||I think I can construct a set of 6.||

[snow silo]

O_O

[faint moss]

0_o

[queen anvil]

but I've already pushed nosols as far as it can go with my statements above, so I'll wait for OP.

[snow silo]

wait can you show it in spoilers? because I don’t see what’s wrong with my proof

[queen anvil]

||ACEIJ
ADFGM
BDHIL
BJKMN
CFHKO
EGLNO​||

[queen anvil]

you are assuming that ||the first three groups are either pairwise disjoint, share one student, or two sharing one student and the third disjoint from both two||.
but you can have ||chain overlaps, like groups 1 and 2 sharing one student, groups 2 and 3 sharing a diff. student, and groups 1 and 3 sharing nothing. this is not covered by your proof||.

[snow silo]

ahhh

okay that does make sense

[viral sapphire]

alright i guys i used AI for this and here is it's solution

[queen anvil]

!noai first of all, but if you were going to use AI, respectfully, why did you ask here, if I may ask?

[slate pond]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[viral sapphire]

I wasn't going to, but I am not getting a clear problem

[queen anvil]

wasn't what we have been trying to do here for the past two hours trying to understand your problem?

[viral sapphire]

It's a specific problem from Combinatorial specifically from maximum packing problem

[queen anvil]

that changes nothing, in my opinion.

[viral sapphire]

I understand but there's something off, Total number of groups as 3 is not possible

[queen anvil]

but have you seen the conversation after that point?

[viral sapphire]

If you only formed 3 groups, you would be leaving many "pair slots" unused

[indigo island]

[queen anvil]

I know. the point is that helpers have spent two hours refining their understanding of the problem.

[viral sapphire]

Okay, but why be rude, i thought you all might get some reference from it? i know AI can't solve properly but just as reference, what's wrong with that?

[viral sapphire]

I understand and i am not dismissing all of urs effect, i appreciate it

what my intention was to give a reference, if not, it's fine

[queen anvil]

well, I suppose you can try helping someone for a couple of hours next time and have them tell you that "it's all good, I pawned my question to a machine and it solved it for me".
regardless, I'll disengage, as this is becoming unproductive and you've probably gotten what you need anyway.
(also, not sure where I was being rude, but sure.)

all the best.

[viral sapphire]

People are so rude, i am never asking questions again

[indigo island]

[queen anvil]

OP seems to have left the server. can this be closed then?
also I apologize to the people in this thread for having to witness this.

[indigo island]

sure, i can close it

.close

[slate pond]

Solved

Post marked as solved by @indigo island.

Use .unsolved if this was a mistake.

[snow silo]

🦫

[reef stag]

Well said.

[snow silo]

ooh I was just thinking about this again before heading to sleep and the solution can be visualized as half of a dodecahedron!! (where edges are students and the other half represents a mirror of the original)

how’s that for an answer chatGPT

https://media.geeksforgeeks.org/wp-content/uploads/20250613171714072995/dodecahedron.webp

[reef stag]

um what

lets not use this channel

tis closed

[snow silo]

oh tis same channel as where it occurred though

[faint moss]

what happened here!

[tranquil condor]

see the above messages

TL;DR: While the helpers were trying to understnad problem, the OP used AI to get answer. Helpers crashed out, and he left the server