[Guest]

Alright, here is round 5 for the Talent Search Questions. Hope you guys are enjoying them Will try find some good questions for ya'll

*** REMEMBER TO SHOW ALL WORKING!! ***

Here we go :

1. Prove that 11 * (14^n) + 1 is never prime.

2. Let n, k be positive integers such that n is not divisible by 3, and k>=n. Prove that there is a positive integer m which is divisible by n, and the sum of its digits in decimal representation is k.

3. M is a subset of {1, 2, ..., 15} such that the product of any three distinct elements of M is not a square. Determine the maximum number of elements in M.

4. At a meeting of 12k people, each person exchanges greetings with exactly 3k + 6 others. For any two people, the number who exchange greetings with both is always the same. How many people were at this meeting?

5. A game is played between two players who move alternatively. Initially there are an arbitrary number of matchsticks in each of two piles. Each move is one of the following three types:

(i) A withdraw of any number of matchsticks from the first pile;

(ii) A withdraw of any number of matchsticks from the second pile;

(iii) A withdraw of the same number of matchsticks from both piles.

Winner is the person who takes the last matchstick. Given best play from both sides, find all winning positions (for the player who has just played).

GOOOOOOOOOOOOOOOOOOO!

[Guest]

case 1

Player 1 takes all but 2 sticks from pile 1.

Player 2 takes takes all but 1 stick from pile 2.

Player 1 will lose at this point, since taking 1 stick from both leaves winning move to player 2, as does taking 1 or 2 sticks from either.

case 2

Player 1 takes all but 1 stick from pile 1.

Player 2 takes takes all but 2 sticks from pile 2.

Player 1 will lose at this point.

case x

Player 1 takes all but x sticks from pile 1, leaving 3 or more sticks.

Player 2 takes takes y sticks from pile 2, leaving 3 or more.

The player who first brings any pile to less than 3 sticks will lose.

Player 1 takes all but 4 sticks from pile 1.

Player 2 takes all but 5 sticks from pile 2.

Player 1 will lose since any move allows player 2 to get both stacks to 3 sticks, which forces player 1 to bring a stack under 3 and thus lose.

It looks like player 2 will always win.

Player 2 (to win) needs to make the stacks 4 and 5 and so needs to avoid being first to take a stack below 6. First to go below 6 will also be first to go below 3, which leads to loss. Stacks of 7 and 8 are also good for player 2 to leave, as any move by player 1 lets player 2 set the stacks to 6,6 and forces player 1 to go below 6 first. Player 2 can force stack of 7,8 the moment a stack falls below 9. So the next step up for a winning stack combo to leave is 10,11. First to go below 12 will enter a losing path of moves. And so on, following this pattern up.

So the winner will be the first player to get both sets of sticks to be not divisible by 3 and also consecutive numbers. Or if the number of sticks in one stack is divisible by 3, then making the other stack equal that is a winning move. So actually it is the player who moves first who will always win, by simply following those 2 rules. Make the bigger stack equal the smaller stack if it is divisible by 3, or make it 1 stick bigger or smaller than the small stack with neither stack being divisible by 3.

[superprismatic]

10

[Guest]

It can have 9 elements. Take numbers from 1 to 15 and look at their base factors. Any combination of 3 that gives an even number of base factors will be a square and so at least one element involved must go.

1,2,3,4,6,8 all have to go because they can be combined with 2 elements to make a square.

But 4 can be kept if 9 goes instead.

Alternatively, 2,3 could be kept but would then have to drop 5 and 7.

Keeping 5,7,9,10,11,12,13,14,15 is 9 elements. None can be combined with 2 others to make a square. Only 12 and 9 start with even number of factors, there is no 3rd element for them to combine with that also has even number of factors to make a square. Of the other elements, 11 and 13 are prime with no shared factors with the other numbers. That leaves 5,7,10,14,15 which can not be combine in a group of 3 that will have even number of factors. 5 and 10 for instance will need another 2, which can only come from 14, but that leaves it with a 7 factor. 7 and 14 have the same problem finding a third element, as do 5 and 15.

[Guest]

There are 12k people, as you said. k can be any integer and it will work. Take k=1. That is 12 people and 9 handshakes. Group everyone into groups of 3. Each group of 3 shakes the hands of the other 9. This works out quite well.

Take case of k=2. This is 24 people and 12 handshakes. Have first 12 people shake hands of second group of 12 people.

Case of k=3. That is 36 people and 15 handshakes. Group people into groups of 3, total of 12 groups. Have each even group shake hands with other even groups, and odd groups shake hands with other odd groups. So each group of 3 shakes hands with 5 other groups of 3, for 15 handshakes.

k=4, there are 48 people and 18 handshakes. Group all into groups of 6. There are 8 groups of 6 people. Have even groups shake with even groups, and odd with odd. That is shaking hands with 3 groups each of 6 people, 18 handshakes.

The OP does not limit the value of k and gives nothing to solve for.

[superprismatic]

Here's an example of a subset of 10:

{1,3,4,5,6,7,10,11,13,14}

[Guest]

Can you please explain me why in question #4

you have asked for the no. of people in a meeting when you have already said that its 12k?

[Guest]

Here's an example of a subset of 10:

{1,3,4,5,6,7,10,11,13,14}

Can you show your workings?

Thanks

[Guest]

Since no one has taken a stab at it, I will get number 1 started, though proof is incomplete.

If n is odd, then the last digit must be 5 since every other 4 factor ends with 4, multplying by eleven doesn't change it and adding 1 makes the last digit 5, obviously divisible by 5. Observation also shows me that wihen n is even, then the number is divisible by 3. Just haven't figured out how to prove it

[Guest]

It can have 9 elements. Take numbers from 1 to 15 and look at their base factors. Any combination of 3 that gives an even number of base factors will be a square and so at least one element involved must go.

1,2,3,4,6,8 all have to go because they can be combined with 2 elements to make a square.

But 4 can be kept if 9 goes instead.

Alternatively, 2,3 could be kept but would then have to drop 5 and 7.

Keeping 5,7,9,10,11,12,13,14,15 is 9 elements. None can be combined with 2 others to make a square. Only 12 and 9 start with even number of factors, there is no 3rd element for them to combine with that also has even number of factors to make a square. Of the other elements, 11 and 13 are prime with no shared factors with the other numbers. That leaves 5,7,10,14,15 which can not be combine in a group of 3 that will have even number of factors. 5 and 10 for instance will need another 2, which can only come from 14, but that leaves it with a 7 factor. 7 and 14 have the same problem finding a third element, as do 5 and 15.

Ok I pick the elements 5 12 15?

[Guest]

There are 12k people, as you said. k can be any integer and it will work. Take k=1. That is 12 people and 9 handshakes. Group everyone into groups of 3. Each group of 3 shakes the hands of the other 9. This works out quite well.

Take case of k=2. This is 24 people and 12 handshakes. Have first 12 people shake hands of second group of 12 people.

Case of k=3. That is 36 people and 15 handshakes. Group people into groups of 3, total of 12 groups. Have each even group shake hands with other even groups, and odd groups shake hands with other odd groups. So each group of 3 shakes hands with 5 other groups of 3, for 15 handshakes.

k=4, there are 48 people and 18 handshakes. Group all into groups of 6. There are 8 groups of 6 people. Have even groups shake with even groups, and odd with odd. That is shaking hands with 3 groups each of 6 people, 18 handshakes.

The OP does not limit the value of k and gives nothing to solve for.

Please note:

At a meeting of 12k people, each person exchanges greetings with exactly 3k + 6 others. For any two people, the number who exchange greetings with both is always the same. How many people were at this meeting?

@Silver Surfer, 12k is not 12,000. k is a constant here that you need to find

[Guest]

whatever be the value of ( n ) it will always have factor 11 so can't be a prime no

[Guest]

whatever be the value of ( n ) it will always have factor 11 so can't be a prime no

Hey, there's a +1 at the end of that formula, double check the question, I wouldn't ask something that straight forward

[superprismatic]

As thoughfulfellow said, for odd n, 11×14ⁿ+1 ends in the digit 5, and hence, is divisible by 5.

Suppose n is even, say n=2×m. The look at 11×14ⁿ+1 = 11×14^2×m+1 = 11×196^m+1.

Looking at 11×196^m+1 modulo 3, we see that 11 = 2 (mod 3), 196^m = 1 (mod 3) [because 196 = 1 (mod 3)],

and so we have that 11×196^m+1 = 2×1 + 1 = 0 (mod 3). Thus, 11×196^m+1 is divisible by 3.

So, in any case 11×14ⁿ+1 composite (either divisible by 5 or 3) and is never prime.

[superprismatic]

Can you show your workings?

Thanks

I cheated in a way because I wrote a program to

check all 32,768 subsets. I found 6 subsets

of size 10 that work:

1 3 4 5 6 7 10 11 13 14

1 3 5 6 7 9 10 11 13 14

3 4 5 6 7 9 10 11 13 14

1 4 5 6 7 10 11 12 13 14

1 5 6 7 9 10 11 12 13 14

4 5 6 7 9 10 11 12 13 14

The program found no subsets of size>10 that work.

[Guest]

Please note:

At a meeting of 12k people, each person exchanges greetings with exactly 3k + 6 others. For any two people, the number who exchange greetings with both is always the same. How many people were at this meeting?

@Silver Surfer, 12k is not 12,000. k is a constant here that you need to find

When you say the number who exchange greetings is always the same, do you mean the number of handshakes, or do you mean that there are people who shake hands with each of the 2 and that number is the same for any 2 people? If it is the first, which is how I read it, it is a redundant statement. If it is the second, which I am thinking is how you mean it, that complicates it a bit. So if any pair shakes hands with a person in common then all pairs must have a person in common as well.

one solution is to have everyone shake everyone else's hand. One can not shake one's own hand and have it count per OP (they shake the hands of others). If one could shake one's own hand, you would have the people equal the handshakes and solve 12k=3k+6 for 8 people and 8 handshakes. However, the number of people is one more than the handshakes, so to balance the two sides add 1 to the handshakes for 12k=3k+6+1 and solve for k=7/9, and there are 9 and 1/3 people who shake the hands of 8 and 1/3 others. That is a bit messy though.

It is impossible to make k big enough for nobody to share a person in common since everyone that one shakes hands with will share that person in common. So a solution could invole permutations so all share the same number in common. In that case, I would say there are 12 people because it sounds right.

Edited June 24, 2011 by Nana7

[Guest]

We need to split the problem in half; case one n = 2m and case two n = 2m + 1.

n = 2m

11 * (14 ^0) + 1 = 11 + 1 = 12 which is divisible by 3 and not a prime.

We note that, for any given integers x and y, (3x + 2)(3y + 1) = 3z + 2 for some integer z (modular multiplication)

11 = 3*3 + 2, 14 * 14 = 196 = 3 * 65 + 1 -> 11*(14^2) = 2 mod 3, if we add a 1 to it, then the number is divisible by 3 (and not a prime).

-> By mathematical induction then we will have a prime value if n is an even number.

n = 2m + 1

Like arguments show that

11* (14^1) = 11*14 = 4 mod 5 and 14*14 = 1 mod 5

(4 mod 5) * (1 mod 5) = 4 mod 5

1 + (4 mod 5) = 0 mod 5

--> 11*( 14^(2m +1)) + 1 is divisible by 5 and is not a prime (as it's not equal to 5 itself).

There no cases for n to consider so we are done.

Edited June 24, 2011 by Treesfearme

[Guest]

When you say the number who exchange greetings is always the same, do you mean the number of handshakes, or do you mean that there are people who shake hands with each of the 2 and that number is the same for any 2 people? If it is the first, which is how I read it, it is a redundant statement. If it is the second, which I am thinking is how you mean it, that complicates it a bit. So if any pair shakes hands with a person in common then all pairs must have a person in common as well.

one solution is to have everyone shake everyone else's hand. One can not shake one's own hand and have it count per OP (they shake the hands of others). If one could shake one's own hand, you would have the people equal the handshakes and solve 12k=3k+6 for 8 people and 8 handshakes. However, the number of people is one more than the handshakes, so to balance the two sides add 1 to the handshakes for 12k=3k+6+1 and solve for k=7/9, and there are 9 and 1/3 people who shake the hands of 8 and 1/3 others. That is a bit messy though.

It is impossible to make k big enough for nobody to share a person in common since everyone that one shakes hands with will share that person in common. So a solution could invole permutations so all share the same number in common. In that case, I would say there are 12 people because it sounds right.

Yes your second interpretation is right. So basically what it is saying is that there exists a number n, where any two people have greeted n people in common. Does that make sense?

[Guest]

Clearly (0,0) is a winning position, and (x,0) and (x,x) are losing positions for any x>0. We say that one position is smaller than another if it has a smaller big stack, or if the big stack is the same size and it has a smaller little stack. The smallest position which is not (x,0) or (x,x) must be winning. From (2,1) the active player can only reach a losing position, hence (2,1) is a winning position. Any position from which (2,1) can be reached by the active player is a losing position. So (x,1), (x,2), and (x,x-1) are losing positions for any x>2. The smallest position which isn't already determined is (5,3), so it must be winning. Which makes (x,3), (x,5), and (x,x-2) losing positions for any x>5. The smallest undetermined position now is (7,4), which is therefore a winning position. Moving on like this we find these winning positions:

(0,0)

(2,1) (big stack has 1 more stick than little stack)

(5,3) (big stack has 2 more sticks than little stack)

(7,4) (big-little=3)

(10,6) (big-little=4)

(13,8) (little stack is always the smallest number which hasn't already been used, difference to big stack increases by 1)

(15,9)

(18,11)

(20,12)

(23,14)

...

I fail to see a nice formula for expressing these positions though.

[Guest]

{1,..15}

the item pairs that could not happen at same time.

15: (15,10,6)

14:(14,7,2)

13 none

12: (12,9,3),(12,8,6),(12,6,2),(12,4,3)

11:none

10:(10,5,2)

9:(9,8,2)

8:(8,6,3),(8,4,2)

7: aboe

6:(6,2,3)

5:above

4:above

3:above

2:above

1:none

For example.

{1-15}

remove 6.

15:work

14:(14,7,2)

13:work

12:(12,9,3),(12,4,3)

11:work

10:(10,5,2)

9:(9,8,2)

8:(8,4,2)

7:above

5:above

4:above

3:above

2:above

1:none

remove 2: leave

12:(12,9,3),(12,4,3)

remove 3. leave

12.work

So remove 2,3,6 will let rest satisfy the condition.

And totally 12.

[superprismatic]

{1,..15}

the item pairs that could not happen at same time.

15: (15,10,6)

14:(14,7,2)

13 none

12: (12,9,3),(12,8,6),(12,6,2),(12,4,3)

11:none

10:(10,5,2)

9:(9,8,2)

8:(8,6,3),(8,4,2)

7: aboe

6:(6,2,3)

5:above

4:above

3:above

2:above

1:none

For example.

{1-15}

remove 6.

15:work

14:(14,7,2)

13:work

12:(12,9,3),(12,4,3)

11:work

10:(10,5,2)

9:(9,8,2)

8:(8,4,2)

7:above

5:above

4:above

3:above

2:above

1:none

remove 2: leave

12:(12,9,3),(12,4,3)

remove 3. leave

12.work

So remove 2,3,6 will let rest satisfy the condition.

And totally 12.

What about choosing 1,4,9?

[Guest]

What about choosing 1,4,9?

Sorry for wrong building exclusive list for 9. missing 9, 4, 1

Therefore,

maybe 11 is largest.