Brain Teaser - Working with numbers that don't divide into one another?

1) Write all of those numbers in the form: 2^k * m where m is an odd integer and k is a non-negative integer. Obviously m < 50. Since we have 25 odd numbers less than 50 if we pick 26 numbers between 1 and 50 two of these m’s are the same. Therefore two of these numbers are of the form x = 2^k * m and y = 2^l * m. Now if k < l then x divides y. If k > l then y divides x.

2) If we have a selection of 25 numbers that don’t divide one another, then by the above argument m’s should be all odd numbers less than 50.

Now, for any odd number m less than 50 pick k to be the largest number that satisfies 2^k * m < = 50.

Obviously if I show this set satisfies the condition, this is the largest possible set.

The set satisfies the condition, because if 2^k * m divides 2^l * n then n is a multiple of m, and hence n is at least 3 m. Hence k is larger than l.

For (3) I should think a bit more.

For (3) the idea is similar. I claim that the set with smallest integers consists of all numbers in the form 2^k * m when m < 50 is odd and k is the largest integer satisfying 3^k * m < 50.

Assume we have a set of 25 numbers satisfying the condition. Then pick an odd number m < 50. Since 3^(k-1) * m divides 3^k * m, the number with 3^(k-1) * m as its “odd part” should be even.

Repeat this argument with 3^(k-1) * m and you can conclude that the number with 3^(k-2) * m as its “odd part” should be divisible by 4. This argument shows that the number with m as its odd part should be divisible by 2^k. Hence this number is at least 2^k * m.

This shows that if we show this set satisfies the condition then it is actually the set with the “smallest” numbers.

Now to see it satisfies the conditions, assume 2^k * m divides 2^l * n. Therefore m divides n. Hence n is at least 3m. By the choice of l we have 3^l * n < 50 which means 3^(l+1) * m < 50. But by definition of k we have: k is the largest number that satisfies 3^k * m < 50, which shows k is at least l+1 and hence 2^k * m does not divide 2^l * n.

All arguments work for any natural number, instead of 50!

@BonusQuestion , I just can’t seem to stump you. Not only do you get the answers, but you get them rather quickly. I am having a little trouble following your reasoning, so I am going to give the answer at a more relaxed pace.

Every number can be expressed as O*2^n where O is odd. For numbers of the form 2^n, O=1 and for odd numbers O, n=0. Half the numbers up to 50 are odd, so there are 25 of them. Given more than 25 numbers, at least two of them must have the same value of O in the O*2^n representation, so one of them must divide the other.

We get the largest solution to the problem if, for each odd number O, we choose the O*2^n such that n is the maximum value such that O*2^n <= 50. To see why this is a solution, we need only consider pairs of odd numbers O1 and O2 where O1 divides O2. O2 must be at least 3 times greater than O1, and therefore O1 can be multiplied by at least one extra power of 2, so we will have O1*2^m and O2*2^n where m > n and therefore O1*2^m will not divide O2*2^n.

To get the smallest solution, consider a sequence like 5, 5*3=15 and 5*3^2= 45. Each of these odd numbers must be multiplied by a different power of 2, The smallest powers of two for the preceding sequence would be 5*2^2, 15*2 and 45, and we can get these values of 2^n for each member O of this sequence by finding the largest value of n such that that O*3^n <= 50. To show that this produces a solution for all odd numbers, you can use an argument similar to the one used in the preceding paragraph for the largest solution.

Now all I have to do is go through this list

http://en.wikipedia.org/wiki/List_of_number_theory_topics

and reread all the details like I did for some of the number theory topics 25 years ago. Can I get back to you next year? I have to admit I never did diophantine approximation though…

Number theory can get quite involved. Whole numbers do not behave as nicely as real numbers, which in turn do not behave as nicely as complex numbers.

Can you @LostInParadise or @BonusQuestion solve this problem?

X people check their coats. Later all X coats are given back randomly. Do you know the probability that no one gets the right coat? Please note, after the event all X coats are given back to the same X people randomly.

This is done by inclusive/exclusive principle. The idea is that the size of union of n sets is the sum of their sizes, minus the sum of the intersection of each pair, plus the size of intersection of each triple, minus intersection of each four, etc.

So, we count the number of all permutations that fix i for a given i. That would give us (n-1)!. Then we count the number of all permutations that fix two numbers i and j that would give us (n-2)!, etc. So if you write down the formula for the number of all permutations that no i is located in position i would be:

n! – n * (n-1)! + (n choose 2) * (n-2)! – (n choose 3) * (n-3)! + (n choose 4) * (n-4)! – ...

Which after simplification we end up with:

n! * ( 1/ 0! – 1/1! + 1/2! – 1/3! + 1/4! – ... + (-1)^n 1/n!)

Therefore the probability would be ( 1/ 0! – 1/1! + 1/2! – 1/3! + 1/4! – ... + (-1)^n 1/n!)

For large n’s this is approximately 1/e!

I saw a real neat solution to this that did not require the inclusion-exclusion. It does take a bit of work though.

Let f(n) = number of ways that none of the n people get the right coat.

Now consider person 1. Suppose that person 1 has person k’s coat. We then ask what the number of ways is that the n-1 remaining people have the wrong coat. There are two possiblities.

One is that person k has person 1’s coat. In that case the number of possibilities is f(n-2).

If we stipulate that person k does not have person 1’s coat then we can say that person 1’s coat is the “right” coat for person k and then there are f(n-1) ways that none of the people get the right coat. Since there are n-1 people whose coat person 1 could have we get:
f(n) = (n-1)(f(n-1) + f(n-2))

Now watch carefully (this is not done with mirrors)
We can rearrange the above equation to get:
f(n) – nf(n-1) = -(f(n-1) – (n-1)f(n-2)).

In other words, apart from sign reversal, f(n) – nf(n-1) is constant.

Since f(1)=0 and f(2)=1, we get f(2) – 1*f(1) = 1,
so f(n) – nf(n-1) = (-1)^n

Now divide both sides by n! and let p(n) be the probabilty of nobody getting the right coat.

We get p(n) – p(n-1) = (-1)^n/n!
p(n) = p(1) + (p(2) – p(1)) + (p(3) – p(2)) +... + (p(n) – p(n-1)),
so p(n) = sum of the terms -(1)^k/k! for k=1 to n,
in agreement with @BonusQuestion‘s answer

You guys are really good! It’s also known as the hat-check problem or derangement.

http://en.wikipedia.org/wiki/Derangement

Let me be clear about this. I did not come up with the solution that I showed. I found it in this really good collection of classic math brain teasers – Ingenious Mathematical Problems and Methods by L. A. Graham.

My previous solution was the “classical” way of dealing with this sort of problems.

Here is another proof that I just came up with:

Let p(n) = f(n)/n! be such probability. (f(n) is the number of all derangements on n numbers.) Any permutation of n numbers has k fixed points for some non-negative integer k; less than or equal to n. Now if we fix these k points the number of derangement in the other n-k positions is f(n-k).

So the number of permutations with exactly k fixed points is (n choose k) * f(n-k). But if we change k from 0 to n we should get all permutations. This means the sum of all these numbers is n!. i.e. sum (n choose k) * f(n-k) = n! ( where 0 <= k <= n )

Divide this by n!, write (n choose k) as n! / (k! * (n-k)!) and write f(n-k) as p(n-k) * (n-k)! and we get:

( sum p(n-k)/k! for k=0…n ) = 1 [call this equation (1)]

Now look at the following power series:

A(x) = sum p(k) * x^k for k = 0…infinity.

If we multiply this series by the series

B(x) = sum x^k/k! for k=0…infinity

and look at the coefficient of x^n we can see that we get exactly the sum in the left hand side of equation (1). Which means:

A(x) * B(x) = sum x^k when k =0…infinity

Now look at B(x). It is the power series of e^x. This means A(x) = e^(-x) * (sum x^k when k =0…infinity)

Write down the power series expansion of e^(-x) and look at the coefficient of x^n in the RHS, it is sum (-1)^k / k!. But the coefficient of x^n in the LHS is p(n) which gives us the same equality that we found before!

Not to brag about my solution… but isn’t that a nice little solution? I liked that! Did I just brag about it?! :D

@BonusQuestion – Only mathematicians are able to see a divine beauty in elegant solutions ;-)