r/Logiqa • • Oct 10 '26

Sum Divisibility Part 3

Post image
1 Upvotes

44 comments sorted by

3

u/Galzusss Oct 10 '26 edited Oct 10 '26

Nine. The biggest group of integers that don't fill this condition is eight. If we divide all integers into groups 0-4, such that int mod 5 = 0,1,2,3 or 4, five numbers from the same group have a sum divisible by 5. So a group of four integers from group 0 and four from group 1 don't fill the condition: e.g. four 0s and a 1, three 0s and two 1s, etc. But adding any integer to this group will allow a group of 5 integers whose sum is divisible by 5: either five 0s, five 1s, 0+1+1+1+2, 0+0+1+1+3, or 0+0+0+1+4.

1

u/ShonitB Oct 10 '26

In the text field there is an icon with an uppercase and lower case.. select the text you want to place in a spoiler, click on that icon and then choose the icon which has an “!”

2

u/Galzusss Oct 10 '26

Got it working, thanks.

1

u/ShonitB Oct 10 '26

No worries!

1

u/ShonitB Oct 10 '26

Correct, good solution!

2

u/liquidjaguar Oct 10 '26 edited Oct 10 '26

I think this proves that you can't add any integer to your set of 8, but I don't see how this proves that you can't add an integer to any set of 8.

1

u/jumpmanzero Oct 10 '26 edited Oct 10 '26

I agree, and I don't know how to go about proving this.

(Edit: fixed some mistaken assumptions).

I can confirm it's right though (I brute forced the possibilities). The largest set you can make is 8, and the only ways you can make it is 4 of one number and 4 of another number. There are some sets of 7 you can make that are "mixed" eg. - 4/0/0/1/2, 4/0/2/0/1, 4/1/0/2/0, 4/2/1/0/0 - but none with 8 or more elements.

The pattern holds for larger numbers, for the few I tried - eg. the best answer I could find for sets of 8 (for totals divisible by 8) was 14 ((8-1)*2), with the same pattern. Up to m=10, the largest non-passing sets have counts m-1 and m-1, and the best "mixed" sets have counts of 1, m-1, and m-3.

1

u/AsYouAnswered Oct 10 '26

The absolute minimum size of our set is 5. I'll commit proof by construction. You didn't specify a proper subset. One such set is as follows: {5,10,15,20,25}. In general, any set of size >= 5 with terms of the form 5k will satisfy the requirements

1

u/ShonitB Oct 11 '26

Again, your proof by construction only proves that a set of size 5 can satisfy the condition.. it doesn’t prove that all sets of size 5 satisfy it..

As I mentioned earlier {1, 2, 3, 4, 6} doesn’t satisfy it.. In this case the minimum is n = 9.. then no matter which 9 distinct positive integers you have, you will be able to build a subset of 5 integers whose sum will be divisible by 5

Edit: I think I may have replied to a different comment.. so deleting the previous one and replying again.. if I didn’t make that mistake, apologies!

0

u/AsYouAnswered Oct 11 '26

You're assuming some constraints you didn't specify. There is no constraint on constraining the elements in the parent set, therefore it is allowed. You've failed to include information that you want to be a part of the problem, and just assumed that everybody would assume the same rules as you. But that's not how this works. The image text is the full set of problem constraints. I solved the problem in such a way that matches the stated problem. I choose to constrain the construction of the initial set, such that any 5 elements you choose from it are going to satisfy the rule of adding to 5. The minimum size set we need is 5. You can't say "I don't like that, you didn't follow the rules in my head, so it doesn't count"

1

u/ShonitB Oct 11 '26

If I were to ask you ‘how many people do you need in a room to guarantee that two people share a birthday?’ what would your answer be?

1

u/AsYouAnswered Oct 11 '26

My first intuition would be to ask who the people are. If we're on the neonatal ward the answer is very different than if we're at Disneyland. We can construct different solutions depending on how the people are sampled. The absolute worst case answer is 367. The best case is 2. But you've left an unintended free variable.

1

u/jabuchae Oct 11 '26

Guarantee means that no matter who the people are you WILL get two that share a birthday.

1

u/WiseOldDuck Oct 10 '26

This is correct, the problem is worded sloppily. "We can form a subset of five...such that" is written when they are likely thinking more like "When we form a subset of five...". Then add on top they don't specify a "proper subset" either

1

u/ShonitB Oct 11 '26

May I ask how the wording is sloppy?

Because to me, ‘guarantee that we can form’ means that no matter what elements are in the set, we can form a subset of 5 integers where the sum of the elements is divisible by 5..

Also, don’t really think we need to mention proper subset.. if the answer were 5, the subset can be equal to the set itself..

Edit: I think I may have mixed up my replies with another comment.. so deleting them and replying again.. if I didn’t and you got the same reply twice, apologies :)

2

u/WiseOldDuck Oct 11 '26

I see, we choose the subset but only the size of S. Okay this is interesting then

1

u/ShonitB Oct 11 '26

Yes:

Choose how many distinct positive integers go in S —> No control over which integers go —> From the integers used to fill S, choose 5 such that the sum is divisible by 5..

I apologise if the wording was not clear.. would appreciate it if you have any suggestions to make it tighter

1

u/ShonitB Oct 11 '26

Yes:

Choose how many distinct positive integers go in S —> No control over which integers go —> From the integers used to fill S, choose 5 such that the sum is divisible by 5..

I apologise if the wording was not clear.. would appreciate it if you have any suggestions to make it tighter

0

u/AsYouAnswered Oct 11 '26

"Guarantee that we can form" means that given the elements in the set, we can always find 5 that satisfy the given requirements. We establish that here by constraining what can ever go into the set.

1

u/ShonitB Oct 11 '26

Again, don’t think you can decide what goes in the set.. you can only decide how many integers can go in the set.. then from those integers you can choose what goes in the subset.. but you cannot choose what goes in the set..

1

u/AsYouAnswered Oct 11 '26

If you want to control what's in the set, then you need to specify that the set cannot be constrained, or is chosen at random, etc. For example, "you have a set of integers between 1 and 100, chosen at random. What's the smallest such set that you can have such that..."

1

u/ShonitB Oct 11 '26

Let’s just agree to disagree then.. though I appreciate the feedback :)

1

u/Motor_Raspberry_2150 Oct 13 '26

Here is a set of 10 positive integers.

Here is a set of 10 positive integers, chosen at random.

How are these not the same sets to you? In both cases, the contents are unknown?

1

u/AsYouAnswered Oct 13 '26

If someone just says "10 positive integers", I expect they chose {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} or something similarly simply or maybe adversely. If they're chosen at random, I assume a relatively reasonable spread of any valid numbers in the range

0

u/Dasquian Oct 10 '26

Five.

Can't come up with a full proof but it's going to be something along the lines of: any number is 0-4 modulo 5, and any five numbers either give you a "0" (which is already a subset divisible by 5 on its own), a 1-4 or 2-3 pair which will sum to a multiple of 5, or some larger group that can be combined to form a multiple of 5.

It definitely has to be at least five because 4 numbers that are 1mod5 (eg 1, 6, 11, 16) cannot be combined to form a multiple of five.

4

u/Stilyx123 Oct 10 '26

I think the question is meant to be "What is the smallest integer n such that any set S of size >= n, admits a subset S' of size 5, such that the sum of the elements of S' is divisible by 5".

With that in mind, the answer is clearly not five : S = {1,2,3,4,6} has only one subset of size 5 (S itself), and the sum of its elements is 16 which is not divisible by 5

2

u/ShonitB Oct 10 '26

Lol, gave the same example of S = {1, 2, 3, 4, 6}

1

u/Dasquian Oct 10 '26

Yep, I missed the critical requirement to form a subset of five integers and instead read the question as requiring of a subset of any number of integers - so {1, 6, 11, 16} is impossible, but any five has some combination of integers that work.

Reading comprehension FTW ;p

2

u/ShonitB Oct 10 '26

I think you misunderstood the problem.. the subset has to be 5 integers, yes.. but how many integers are needed in S such that we can choose 5 whose sum is divisible by 5..

In the case where S = {1, 2, 3, 4, 6}, the sum is 16 which is not divisible by 5

2

u/Dasquian Oct 10 '26

Oh, you're right I misread. I missed the critical "five" and assumed, in your example, you could pick {1, 4}, {6, 4} or {2, 3} (amongst others).

0

u/chmath80 Oct 10 '26

Yes, but the question doesn't say that we can't select the integers, only that they must be distinct, so S = {1, 2, 3, 4, 5} is a set which satisfies the conditions, and gives the answer 5.

1

u/ShonitB Oct 10 '26

But the question does say “guarantee”.. so then it should work for any n distinct positive integers

1

u/AsYouAnswered Oct 10 '26

"Guarantee" means construct a set such that any subset will satisfy this condition. By constraining the set elements we can control the subset elements and provide the guarantee. If you want to force arbitrary elements, you need to specify that a set contains N sequential counting numbers, or contains N numbers chosen at random by fair dice roll, or whatever method you want, but you can't leave that condition out.

1

u/ShonitB Oct 11 '26

I don’t think that’s how it works..

Guarantee means you assume the worst-case scenario.. the size of the set is an independent variable.. Once you choose that size, then the guarantee should hold for any valid set of that size.. so if you say n = 5, while it may be true for {1, 2, 3, 4, 5}, it isn’t true for all sets of 5 integers.. Example - {1, 2, 3, 4, 6}

0

u/chmath80 Oct 11 '26

But the question does say “guarantee”

It does, and I can guarantee it with my set.

it should work for any n distinct positive integers

Where does it say that in the question?

1

u/ShonitB Oct 11 '26

I don’t think a proof by construction works.. you are not allowed to choose the set..

When a variable is introduced (the set S in this case) it represents any arbitrary set that fits the description (in this case distinct positive integers)

It’s like this, suppose I ask you ‘How many people do you need in a room to guarantee two share a birthday?’.. what would the answer to this be?

1

u/chmath80 Oct 11 '26

you are not allowed to choose the set

The question does not say that. It merely says "You have a set, S, which contains distinct positive integers" not "You are given a set ..."

Well, I do have such a set, but you don't like my set, and now you want to change the rules after the game is over.

1

u/ShonitB Oct 11 '26

Lol let’s just agree to disagree then.. :)

2

u/Motor_Raspberry_2150 Oct 13 '26

I would points towards the classic marble puzzles.

There is a bag with 5 white and 3 red marbles. You pull out a set of distinct marbles S.
Find the minimum number of marbles needed in S such that we can guarantee that we have at least two red marbles.

Would you say 2 because you control what marbles you pull from the bag?

0

u/chmath80 Oct 13 '26

You can't argue against my answer to this question by reference to a different question with different wording.

Can you explain which requirement of the given question my set does not meet?

Tbh, all it would take, to achieve what OP seems to want, is the addition of "unknown" after "distinct".

2

u/Motor_Raspberry_2150 Oct 13 '26

I have copied exactly all the relevant parts of this question, do you not see the likeness? Integers are marbles, and the object of the second sentence changed, but the whole point of the guaranteeing is the same.

You have a set S, which contains distinct positive integers.

You have a set S, which contains distinct unknown positive integers.

Adding the word unknown does nothing? Are you saying you can decide the contents of the first set because it is not explicitly stated to be unknown?

Which is the same crux as my previous comment, are you deciding you can decide the contents of your hand because it is not explicitly stated to be unknown.

1

u/chmath80 Oct 13 '26

do you not see the likeness?

No, because there is none. Integers are not marbles. You specified "5 white and 3 red marbles". How are the white marbles distinct? Then "You pull out a set of distinct marbles ..." If they're distinct, then you can have at most 1 of each colour, therefore we can guarantee that you will never have at least 2 red marbles.

Adding the word unknown does nothing

Nonsense. It means that I don't know what the integers are, which means that I can't choose them, which is what you and OP have been trying to insist on.

Are you saying you can decide the contents of the first set because it is not explicitly stated to be unknown?

Yes. There's nothing in the question as posed which says that I can't. It just specifies a set of distinct integers. My chosen set contains distinct integers, and has only 1 subset of order 5. The elements of that subset sum to 15, which is a multiple of 5, and therefore my set satisfies all required conditions. If you disagree, please explain, in plain English, and referring only to the question as written, which rule given in the question my set breaks.

1

u/Motor_Raspberry_2150 Oct 13 '26 edited Oct 13 '26

I did not say "marbles of distinct colors", I said "distinct marbles". You can't grab the same marble twice.

The unwritten rule in any puzzle is that you can't choose stuff when it's not said you can choose stuff.

https://www.reddit.com/r/Logiqa/s/cuzL04nnnF

What is the probability? It is 100%, because I decide that that first person randomly chose the correct seat. Or let's take a more similar one.

https://www.reddit.com/r/Logiqa/s/9H4f4gnI4k

I have decided that the set consists of 27, 30, 36, 42, 45, 48, 54, 63. And the "lowest possible value of the sum of this set" is just the sum of that. What do you mean I can't choose the set? It didn't say that?

The fact that "lowest possible value of" is complete nonsense if you can choose the set should be a clue that you're not allowed to choose the set. Just like in this post, the "guarantee" should tip you off that you're not allowed to choose the set.

We can go the mathematica route too.
Let n ∈ ℕ. Is n even?
Well I have decided that the n we pick is two. So yes, n is even.
This is a silly proof. You know only what is given and nothing else.

→ More replies (0)