Maths challenge
Author  Message 
dewtell
Posts: 18

Posted: 04:39AM Jan 27, 2015 

Steve1973: No. That's an example of a set where n=3 and the properties hold, but n=3 doesn't guarantee the properties hold for any set S with 3 members. For example, {2, 17, 39} would fail. The challenge is to find n so that every set S with n members (as specified in the problem) will have the properties (a) and (b), and n is as small as possible. Obviously n=100 would satisfy the properties, since there is only one set possible with 100 members, but you can do better than that.
This message was edited on 04:42AM Jan 27, 2015 
Back to Top 
View Profile
Send PM

JQPublic
Posts: 1879

Posted: 05:23AM Jan 27, 2015 

This reminds me of your frisbee problem, which I still haven't cracked ...
'An idea, like a ghost, must be spoken to a little before it will explain itself.'  Charles Dickens 
Back to Top 
View Profile
Send PM
Visit Wiki

dewtell
Posts: 18

Posted: 05:07PM Jan 27, 2015 

JQPublic: The hint to my frisbee problem gives the formula the two numbers have to satisfy, for those who don't remember (or never studied) enough number theory to work it out from scratch. I'm not sure if I remember enough off the top of my head to rederive it without looking up my references, although I could certainly work it out for a bunch of concrete examples, which would suggest the general formula.
This message was edited on 05:11PM Jan 27, 2015 
Back to Top 
View Profile
Send PM

Steve1973
Posts: 826

Posted: 09:33AM Jan 28, 2015 

dewtell wrote:
Here's a challenge, from a math competition years ago. Nonempty set S consists of n distinct integers between 1 and 100 (inclusive). What is the smallest value of n that guarantees that both (a): the largest element of S is equal to the sum of two distinct elements of S, and (b): the smallest element of S is equal to the difference of two elements of S other than that smallest element. Explain (the original question asked for a proof, and a counterexample for n1).
(Edited to clarify that xy = y doesn't satisfy (b), if y is the smallest element.)
Steve1973: No. That's an example of a set where n=3 and the properties hold, but n=3 doesn't guarantee the properties hold for any set S with 3 members. For example, {2, 17, 39} would fail. The challenge is to find n so that every set S with n members (as specified in the problem) will have the properties (a) and (b), and n is as small as possible. Obviously n=100 would satisfy the properties, since there is only one set possible with 100 members, but you can do better than that.
AS the question asked for "what is the smallest value of n", the answer would be 3.
Explanation:
It's a classic case of X + Y = Z as defined by the question itself, and we need 3 distinct numbers to fill the smallest set of numbers as " the smallest element of S is equal to the difference of two elements of S other than that smallest element".
two elements  this says at least 2 elements are needed
other than that smallest element  this defines at least a 3rd element
By the definition of the question alone, it's proven that we need 3 elements (and 1, 2, 3 satisify all parts of our requirement), so 3 would be the smallest value of n possible in this case.
Like to chat? Share links? Don't want to be told, it's a NoNo to do so? Then come join us in THE REAL GENERAL DISCUSSION talkbox  where you can post with only the lightest of moderation. 
Back to Top 
View Profile
Send PM

Evita
Posts: 63

Posted: 11:10AM Jan 28, 2015 

you don't decide what numbers fill the set, only how many numbers can be in the set
It's when you draw it you realize what it really looks like 
Back to Top 
View Profile
Send PM
Visit Wiki

dewtell
Posts: 18

Posted: 12:58PM Jan 28, 2015 

Right. The question doesn't ask what value of n makes such a set possible, it asks what is the smallest value of n that guarantees that the set meets those properties.
Perhaps it's time for a hint: it might be helpful to try and construct a counterexample. What is the largest set you can construct (within the rules) that *doesn't* have those properties? If that set has k members, you know that n has to be at least k+1, which should at least get you looking in the right neighborhood.

Back to Top 
View Profile
Send PM

JQPublic
Posts: 1879

Posted: 06:49AM Jan 29, 2015 

dewtell wrote: JQPublic: The hint to my frisbee problem gives the formula the two numbers have to satisfy, for those who don't remember (or never studied) enough number theory to work it out from scratch. I'm not sure if I remember enough off the top of my head to rederive it without looking up my references, although I could certainly work it out for a bunch of concrete examples, which would suggest the general formula.
Since I fall into a 'nver studied' category, I got it using the formula (which made it significantly easier ... ), although I still have no clue about this set question ... does it require number theory too? or can it be found using basic algebra (to which I am limited)?
'An idea, like a ghost, must be spoken to a little before it will explain itself.'  Charles Dickens 
Back to Top 
View Profile
Send PM
Visit Wiki

dewtell
Posts: 18

Posted: 10:34AM Jan 29, 2015 

No number theory or other fancy math required for the set problem, though it takes some cleverness in how you set it up. You definitely should be able to follow the proof using nothing more powerful than high school algebra. Another hint: some version of the Pigeonhole Principle may be involved. If you haven't heard of it, it just says that if you have n+1 pigeons living in n pigeonholes, at least two pigeons must live in the same hole. Pretty common sense, actually.

Back to Top 
View Profile
Send PM

dewtell
Posts: 18

Posted: 11:15AM Jan 29, 2015 

JQ  here's an example that may give some of the intuition behind that frisbee problem formula (though I may be giving away a chance to earn points with a bunch of cheap teasers here). Consider the game of simplified (American) football, in which the only two scoring moves are the field goal, worth 3 points, and the touchdown, worth 7. (Compared with the actual game, this gets rid of the point after touchdown and the safety). What's the largest score that can't be achieved by one side in simplified football?
Well, you can split the possible scores to be achieved into 3 categories: numbers of the form 3n, 3n+1, and 3n+2. Any score of the form 3n can be achieved by kicking field goals alone. Scoring a single touchdown gives you a score of 7, which is of the form 3n+1. So you can get any score of this form that is 7 or bigger with one touchdown plus a bunch of field goals. The biggest score of the form 3n+1 that you can't achieve is 4 (also 1). Finally, two touchdowns scores 14, which is of the form 3n+2. So you can get any score of this form that is 14 or bigger with two touchdowns plus a bunch of field goals. The only scores of the form 3n+2 that you can't achieve are those less than 14: 2, 5, 8, and 11. So the biggest overall score that you can't achieve is 11.
You can make a similar argument for any two positive integers that are relatively prime to each other (no common factors). (If they do have a common factor, then there will be no upper bound on the scores that can't be achieved, because you will not be able to achieve any score that is not divisible by that common factor.) In each case, the highest score that can't be achieved will be given by that formula  and if you look at how we argued here (splitting the cases up into the different remainders that are left when dividing possible scores by one of the numbers), you should be able to get some intuition of where the different parts of the formula come from. Actually proving it in general may take some results from number theory, but the intuition isn't that complicated.

Back to Top 
View Profile
Send PM

JQPublic
Posts: 1879

Posted: 07:09PM Jan 29, 2015 

dewtell wrote: No number theory or other fancy math required for the set problem, though it takes some cleverness in how you set it up. You definitely should be able to follow the proof using nothing more powerful than high school algebra. Another hint: some version of the Pigeonhole Principle may be involved. If you haven't heard of it, it just says that if you have n+1 pigeons living in n pigeonholes, at least two pigeons must live in the same hole. Pretty common sense, actually.
Thanks for explaining the frisbee teaser.
I remember reading about the pigeonhole principle (I think it was called the 'drawer principle' in Chinese) in 100,000 Whys, a wellknown Chinese publication that teaches kids maths and science. (I enjoyed the two maths volumes. The environmental science ones, by contrast, were really really dull ...)
Anyway, I'm still struggling to realise how pigeons are related to the set ...
This message was edited on 07:09PM Jan 29, 2015
'An idea, like a ghost, must be spoken to a little before it will explain itself.'  Charles Dickens 
Back to Top 
View Profile
Send PM
Visit Wiki

dewtell
Posts: 18

Posted: 08:43PM Jan 29, 2015 

JQ: No problem. Actually, on further reflection, I realized that the frisbee problem formula can be proven without much number theory at all, using an argument that is structured much like my simplified football example.
If you did want to learn more about number theory, I can highly recommend H. Davenport's book, "The Higher Arithmetic: An Introduction to the Theory of Numbers." That book can be read and understood without much more than just high school algebra as a background  I read it when I was in either early high school or junior high. There are some number theory topics the book doesn't cover that require more background  a bunch of the theorems on the distribution of primes, for example  but a lot of number theory isn't that hard to learn on your own if you are interested. It's just not covered in the typical high school curriculum, because it isn't seen as having as much general value as the stuff that is covered. But it is rather useful for puzzles and teasers, along with a bunch of modern applications like cryptography.

Back to Top 
View Profile
Send PM

dewtell
Posts: 18

Posted: 10:50AM Jan 31, 2015 

Another hint on the set problem: it might be useful to look at simpler versions of the same problem, to see if they can yield any useful insights. What happens if you limit the size of the numbers to the point where you can fully enumerate all the subsets of a given size? For example, if the numbers were limited to being between 1 and 5, then we know that {1, 2, 4} doesn't have the two properties, so n would have to be at least 4. Looking at all the subsets of size 4, we have: {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, and {2, 3, 4, 5}. Each of these satisfies the two properties, so for an upper bound of 5, we have n=4.
Now what happens if we use an upper bound of 6 on the size of the numbers? The same counterexample tells us that n is at least 4, but are there any bigger counterexamples? Note: we also know that any bigger counterexample will have to include the number 6, since we have already checked all the examples that don't above.
(Note: there's an issue about counterexamples that starts to become evident with an upper bound of 6, but I'll wait to make it for a bit.)
This message was edited on 05:15PM Jan 31, 2015 
Back to Top 
View Profile
Send PM

 
