Brain Teasers
Brain Teasers Trivia Mentalrobics Games Community
Personal Links
Your Friends
Your Watchlist
Public Forums
Games
Writing Teasers
Teaser Answers
Ask a Question
The Human Mind
Trivia and Quizzes
New? Start Here!

General Discussion
Entertainment
Sports
Current Events

Announcements
Bugs & Requests

Subscribers
High Scorers
Moderators
High Karma
Debate
Grownups
More Community
Newsgroups
Wiki
Teaser Comments
Trivia Comments

User Rankings
Search for User
Add to Google delicious Add to del.icio.us

More ways to get Braingle...
rss

Braingle Time
6:21 pm

Public Forums >> Teasers Without Answers >>


Forum Rules View Watchlist


Skip to Page:  1   2   3   4  

Maths challenge

AuthorMessage
dewtell*

Posts: 18

new 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

new 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

new 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 re-derive 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    
Steve1973Aus

Posts: 826

new Posted: 09:33AM Jan 28, 2015

dewtell wrote:

Here's a challenge, from a math competition years ago. Non-empty 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 counter-example for n-1).

(Edited to clarify that x-y = 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 No-No 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*dk

Posts: 63

new 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

new 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 counter-example. 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

new 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 re-derive 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

new 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

new 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

new 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 well-known 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

new 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

new 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    

Skip to Page:  1   2   3   4    



Public Forums >> Teasers Without Answers >>


! Access Restricted

You'll need to create an account and sign in before you can post messages.






Users in Chat : None 

Online Now: 10 users and 394 guests

Copyright © 1999-2014 | Updates | FAQ | RSS | Widgets | Links | Green | Subscribe | Contact | Privacy | Conditions | Advertise

Custom Search





Sign In A Create a free account