The sort of standard contest math technique for problems like this is to construct a 9 member subset that doesn’t have the property. Then show that you can’t add another number without creating 2 subsets that have the same sum wlog.
A friend just gave me this, I can't solve it, and moreover, I have no idea how it could even be solved:
prove that for any set of 10 unique numbers [1,100] there will be 2 subsets with the same sum
I'm not even sure how to reduce it to a manageable problem where I can formulate a hypothesis. 10 seems like root 100, but that is a red herring I think. I just have no idea how to formulate this problem with [1,10] or [1,1000]. Intuitively, it feels like the number of unique numbers required for the proposition to hold will scale with ln(n) but I really have no idea.
There are 955 possible sums of those ten unique numbers up to 100. From one to 955. The number of possible combos of ten things is two to the tenth power minus one.,which is 1023. Those 1023 combos can't all be different sums since there are only 955 available.
The sort of standard contest math technique for problems like this is to construct a 9 member subset that doesn’t have the property. Then show that you can’t add another number without creating 2 subsets that have the same sum wlog.
There are 955 possible sums of those ten unique numbers up to 100. From one to 955. The number of possible combos of ten things is two to the tenth power minus one.,which is 1023. Those 1023 combos can't all be different sums since there are only 955 available.
I don't understand this, sorry David. How are there 955 possible sums?
I don't know what it is about quantum computers that makes incredible intelligent people say insane things but this made the rounds on certain parts of facebook.....
Borcherds is obviously making a joke, but just to explain it to the unfamiliar, the current best tests we have for quantum computers that they can actually pass involve highly convoluted problems designed specifically to be hard for classical computers, but easy for quantum ones. Borcherds compares this to figuring out how many pieces a teapot will break into if you drop it, which is of course a problem that might be much easier for a teapot than a supercomputer.
The glaring difference, of course, is that if quantum computers can do these highly contrived problems better than classical computers, there is no "good reason" to think they also cannot do much more important "natural" problems like integer factorization or certain optimizations that many people reasonably believe cannot be done efficiently with classical computers. No such natural problems of course exist for tea pots.
I don't know what it is about quantum computers that makes incredible intelligent people say insane things but this made the rounds on certain parts of facebook.....
Borcherds is obviously making a joke, but just to explain it to the unfamiliar, the current best tests we have for quantum computers that they can actually pass involve highly convoluted problems designed specifically to be hard for classical computers, but easy for quantum ones. Borcherds compares this to figuring out how many pieces a teapot will break into if you drop it, which is of course a problem that might be much easier for a teapot than a supercomputer.
The glaring difference, of course, is that if quantum computers can do these highly contrived problems better than classical computers, there is no "good reason" to think they also cannot do much more important "natural" problems like integer factorization or certain optimizations that many people reasonably believe cannot be done efficiently with classical computers. No such natural problems of course exist for tea pots.
If that isn't from Douglas Adams then he would have wished it was.
67 and 23 are touching. Hint and solution in two more nested spoilers.
Spoiler:
The key thing to realise is that the two middle squares touch all but one other square. This drastically limits which numbers can be placed in those two squares.
The key thing to realise is that the two middle squares touch all but one other square. This drastically limits which numbers can be placed in those two squares.
Spoiler:
Well Done. And until you realize the hint there isn't any way I can think of to get the answer other than stumbling upon it. As Prof. Gowers alluded to.
A friend just gave me this, I can't solve it, and moreover, I have no idea how it could even be solved:
prove that for any set of 10 unique numbers [1,100] there will be 2 subsets with the same sum
I'm not even sure how to reduce it to a manageable problem where I can formulate a hypothesis. 10 seems like root 100, but that is a red herring I think. I just have no idea how to formulate this problem with [1,10] or [1,1000]. Intuitively, it feels like the number of unique numbers required for the proposition to hold will scale with ln(n) but I really have no idea.
There was actually a mathologer video on the pigeonhole principle last month that included almost this exact problem (it was using a version from an old math olympiad, which for some reason only included double digit numbers rather than all of 1-100):
Also a bit of an extension, which the above video will provide a hint to:
What is the highest integer X for which this statement is true: For any set of 10 unique integers in the range [1,X] there will be 2 subsets with the same sum
Spoiler is another slight hint but also why I wanted to add the extension.
Spoiler:
This is interesting to me because the answer is not what might be expected given David's short explanation of a proof for the original statement with X=100.
Also a bit of an extension, which the above video will provide a hint to:
What is the highest integer X for which this statement is true: For any set of 10 unique integers in the range [1,X] there will be 2 subsets with the same sum
Spoiler is another slight hint but also why I wanted to add the extension.
Spoiler:
This is interesting to me because the answer is not what might be expected given David's short explanation of a proof for the original statement with X=100.
I was thinking about this again and realised that what I was getting at with this extension wasn't really accurate. I'm not sure there is actually a method outside of brute force to find the value of X and I think that has NP-hard complexity. There is a specific value for X after which pigeonhole proofs stop being valid though and that's what I was thinking of when I wrote this.
Do we know how many answers there are for this as you and I came to 2 different ones?
I found it instantly intuitive.
And I am now thinking perhaps I just lucky as your proof does not use what I thought was a key opening sequence.
For me I instantly assumed the key to solving was...
Spoiler:
...starting with the two most central number 4 & 5 and putting them in the polar opposite spots where they touched the least numbers.
I could instantly see that would leave the 4 remaining numbers with the most potential space between them and once I plopped those 2 in, and just looked at the board it was crystal clear and obvious as to how to arrange the last 4.
...1 8
4 6 3 5
...2 7
Quote:
Quote:
Originally Posted by Willd
[SPOIL]...
Spoiler:
The key thing to realise is that the two middle squares touch all but one other square. This drastically limits which numbers can be placed in those two squares.
Do we know how many answers there are for this as you and I came to 2 different ones?
I found it instantly intuitive.
And I am now thinking perhaps I just lucky as your proof does not use what I thought was a key opening sequence.
For me I instantly assumed the key to solving was...
Spoiler:
...starting with the two most central number 4 & 5 and putting them in the polar opposite spots where they touched the least numbers.
I could instantly see that would leave the 4 remaining numbers with the most potential space between them and once I plopped those 2 in, and just looked at the board it was crystal clear and obvious as to how to arrange the last 4.
...1 8
4 6 3 5
...2 7
Your solution is wrong. King Spew's reply immediately after your post was pointing out that you have 2,3 and 6,7 touching. The only valid solutions are symmetries of each other, there are no other distinct solutions.
cannot be reduced to a simpler fraction for all integer values of x
Seems like nobody gave this a shot. Hint in spoilers
Spoiler:
Think of the conditions on when x and x+n share a common factor. For instance, it should be obvious that they never do when n=1. After that, think of what you can do to the given fraction to make a comparison like the one above in terms of common factors.
cannot be reduced to a simpler fraction for all integer values of x
I haven't read your hint yet or done formal proofs for a long time so there might be an obvious flaw somewhere but this is my attempt:
Spoiler:
Assume there is a number z that divides both numerator and denominator such that
(21x + 4) / z = k
(14x + 3) / z = j
where z, k, and j are integers
Rearranging to get x in terms of k, j, z:
x = (kz - 4) / 21
x = (jz - 3) / 14
therefore
(kz - 4) / 3 = (jz - 3) / 2
Rearranging for z in terms of k, j:
14kz - 28 = 21jz - 63
2kz = 3jz - 5
5 = 3jz - 2kz
z = 5/(3j - 2k)
Since 5 is prime the only possible solution when z, j and k are integers is z = 5 (or technically also z = -5 but they are functionally equivalent)
for 5 to divide the numerator
(21x + 4) mod 5 = 0
this is true when x = 5n + 1, where n is an integer
for 5 to divide the denominator
(14x + 3) mod 5 = 0
this is true when x = 5n + 3, where n is an integer
x cannot be both 1 more and 3 more than a multiple of 5 so we have reached a contradiction and our original assumption must be incorrect. Therefore z does not exist and the fraction cannot be reduced. QED