Discrete Math Questions

[Steven G]

Maybe we should have a discrete math forum as I do not think that my post should be under advanced math.

In any case my brain is not so sharp these days as I recover from a mild case (no fever) of covid-19.

As a result I have a couple of counting type problems.

The first one I did just fine. The thing is that I was told by someone (a student) that the problem could be done by the pigeon hole principle and if so I would like to see it done that way.

1)What is the minimum number of integers we need to choose from A={1,2,3,4,5,6,7,8,9} so that no matter which integers are chosen, there will always be three integers that sum to 15. My answer is you need 7.

The 2nd one I am not sure how to do
2) 8 arbitrary integers are chosen from {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}. Prove that there are three equal numbers among the pairwise differences of these eight integers.

Yes, I know not to post two problems in one post. It is that they seem similar and I am not up to writing two posts.

 

[Steven G]

OK, I easily did number 2 using the pigeon hole principle. Number 1 using the php is still troubling me. I will look at it some more.

 

[lookagain]

1)What is the minimum number of integers we need to choose from A={1,2,3,4,5,6,7,8,9} so that no matter which integers are chosen, there will always be three integers that sum to 15. My answer is you need 7.

I think the answer is also 7.

Four of them would not be enough because 1 added through 4 is not enough.

Five of them are not enough because with {5, 6, 7, 8, 9}, the smallest of the
three add to too much.

In a set that is chosen to work, there must exist one of the following that add to 15:

1, 5, 9
1, 6, 8
2, 4, 9
2, 5, 8
2, 6, 7
3, 4, 8
3, 5, 7
4, 5, 6

Of these eight sub areas, there are two which have counterexamples that
show that six integers is not a minimum number to choose:

1)
If none of 2, 5, 8 are picked, then you are left with 1, 3, 4, 6, 7, 9.
You cannot get a sum of 15 with any three of those.

or

2)
If none of 4, 5, 6 are picked, then you are left with 1, 2, 3, 7, 8, 9.
It's the same conclusion.

The sets {1, 5, 9}, {2, 6, 7}, and {3, 4, 8} divide up the original set of nine numbers
into three mutually exclusive sets. By the Pigeonhole Principle, when you pick any
seven elements (numbers) from these sets, you necessarily will get a group
of three that will add to 15.