GR9367 #35 and 61

[CoCoA]

35. Let f be a real-valued function defined on a set of integers and satisfying f(x)=1/2 f(x-1) + 1/2 f(x+1). Which of the following must be true?
I. The graph of f is a subset of a line.
II. f is strictly increasing.
III. f is a constant function.

A. None
B. I only
C. II only
D. I and II
E. I and III

61. A city has square city blocks formed by a grid of north-south and east-west streets. One automobile route from City Hall to the main firehouse is to go exactly 5 blocks east and 7 blocks north. How many different routes from City Hall to the main firehouse traverse exactly 12 city blocks?
A. 5 \cdot 7
B. 7!/5!
C. 12!/7!5!
D. 2^12
E. 7!5!

[amateur]

For Q. 35, the correct answer is B.

Let us consider the recurrence relation in the question,

f(x + 1) - 2f(x) + f(x - 1) = 0.

Solving it, we get f(x) = C1 + C2 x, where C1 and C2 are constants.
This represents a straight line. As the function is defined only on
integers, (so it is not continuous) and represents a subset of a
straight line.

I. is correct.
II. is wrong since C2 = 0, results in f(x) = C1 which is a constant function
III. is wrong since C1 = 0, results in f(x) = C2 x which is an increasing function.

For Q. 61,

Each valid path can be represented a string of 5 "0"s and 7 "1"s where each
"0" is for "East" and each "1" is for "North". Total number of such strings
is C(7 + 5, 7) = C(7 + 5, 5) = C(12, 5) = 12! / (7! 5!). Correct answer is C.

[Nameless]

35. Let f be a real-valued function defined on a set of integers and satisfying f(x)=1/2 f(x-1) + 1/2 f(x+1). Which of the following must be true?
I. The graph of f is a subset of a line.
II. f is strictly increasing.
III. f is a constant function.

A. None
B. I only
C. II only
D. I and II
E. I and III

@amateur : your answer is great but I dont think many know about functional analysis. Let solve this problems as follow :

1. Choose f=1 then II is incorrect
2. Choose f(x)= x then III is incorrect so the answer is I

Btw, I have some questions :

#Problems 40. - GR9367
if x,y,z are selected independently and at random from the interval [0,1] then the probability that x>= yz is 3/4.

If some one knows, please explain.

#problem 66 - GR9367 :

let n be any positive integer and 1<= x1<x2<....<x_(n+1)<=2n where x_i is an integer the which of following must be true :

I. there is x_i st : x_i is the square of integer
II. there is x_i st : x_(i+1)=x_i + 1
III. There is x_i that is prime

a. I only
b. II only
c. I , II
d. I, III
e. II, III


The answer is II but i am not satisfied with it.
we have 1<=x_1 so and 1^2=1 = x_1 so I is correct
III is correct since there is a prime number between 1,...., 2n for all positive integer n

for II, use the Dirichlet's principle we can prove that II is true

so, in my opinion, I, II,III are correct.

Comments are welcome !

[amateur]

Thanks for the compliment.

The following solution is a bit informal:

Regarding Q. 40, since x, y, and z are being selected randomly from [0, 1], we may assume that their values are equal to their probabilities.

Now consider selecting x randomly. The probability that x >= v is 1 - v.
For example, p(x >= 0) = 1 - 0 = 1, p(x >= 1) = 1 - 1 = 0...

Since y and z are selected randomly and independently, their values would be (on average), equal to 1/2 and 1/2 each, respectively. So yz = (1/2)(1/2) = 1/4 (on average).

Therefore p(x >= 1/4) = 1 - 1/4 = 3/4 = 75%

=========================================================================================

For Q.66, Observe the following,

In the interval [1, 2n], there are n intervals each containing a pair of even/odd integers.
For example when n = 5, 2n = 10, the intervals are [1,2], [3,4], [5,6], [7,8], [9,10].
Since there are n+1 distinct "x" values to be selected, according to the Pigeonhole Principle, at least two of them must belong to the same pair. So we can deduce II quite easily.

Regarding I, the selection 1, x1=2, x2=3, x3=5, x4=6, x5=8, x6=10, 10 does not satisfy I.

Regarding III, since the number of primes diminishes with increasing n, so I am inclined to rule out III also. As a matter of fact, for n = 10, 2n = 20, the selection of the 11 integers 1, x1=4, x2=6, x3=8, x4=9, x5=10, x6=12, x7=14, x8=15, x9=16, x10=18, x11=20, 20 rules out III also.

[Nameless]

Your answer for #Q.40 is awesome. But :

Regarding I, the selection 1, x1=2, x2=3, x3=5, x4=6, x5=8, x6=10, 10 does not satisfy I.

Based the definition of x_i :

1<= x1<x2<....<x_(n+1)<=2n


we can choose x_1=1 so x_1=1^1 so I is correct , is it ?

[CoCoA]

we can choose x_1=1 so x_1=1^1 so I is correct , is it ?

I think it is a tricky wording. Since they say "which of the following must be true," there must exist a perfect in *every* sequence you can form like that. (So it is really a re-wording of a "for all... there exists" statement)

Youo have chosen a sequence that does have a square, but the sequence given by amateur does not have a perfect square in it, so it is not true for every sequence (it does not meet condition "must be true")

[Nameless]

Hi CoCa

it is not word problem, please take a look at the definition of sequence (x_i)

let n be any positive integer and 1<= x1<x2<....<x_(n+1)<=2n

[amateur]

This was a problem I faced for the GRE General Exam also.

When a question on the GRE asks Which of the following could be true [Q.5 GR9768, Q.30 GR9768] it means that anyone of the following could be a possible solution or a possible true statement under certain conditions.

When a question on the GRE asks Which of the following must be true [many examples in GR 0568] it means that the statement must be true inder all circumstances and all value choices.

[Wonderacle]

#Problems 40. - GR9367

note that CAPITAL letters represent variables while lower case represent a specific value.

Pr(X>YZ)
=int Pr(X=x, YZ<x) dx evaluating from x=0 to x=1
=int f(X=x)f(YZ<x) dx from x=0 to 1 since X,Y,Z are independent random variables
=int f(YZ<x) dx from X=0 to 1 since X from[0, 1]

Now, we just need to find f(YZ<x) then do the integral. There are two cases for the choice of Y (you can use Z instead):
1. if Y<x, Z could be any value;
2. if Y>x, Z must be less than x/y.
therefore,
f(YZ<x)=Pr(Case 1)+Pr(Case 2), while
Pr(Case 1)
=f(Y<x)
=x
Pr(Case 2)
=int Pr(Y=y, Z<x/y) dy from y=x to y=1
=int f(Y=y)f(Z<x/y) dy from y=x to 1
=int f(Z<x/y) dy from y=x to 1
=int x/y dy from y=x to 1
=x int 1/y dy from y=x to 1
=-xlnx
therefore,
f(YZ<x)=x-xlnx,
put this back to the original integral,
Pr(X<YZ)
=int x-xlnx dx from x=0 to 1
=(3/4)(x^2)-(1/2)(x^2)(lnx) from x=0 to 1
=3/4

[Wonderacle]

#problem 66 - GR9367

I is incorrect if we let n=3, and choose the sequence
1, 2, 3, 5, 6, 6
III is incorrect if we let n=5, and choose the sequence
1, 1, 4, 6, 8, 9, 10, 10

II is correct since there can be at most 2n numbers (1 to 2n) to be chosen for x1 to x_(n+1), so at least two of them must be consecutive

[zuluyankee]

#problem 66 - GR9367 :

let n be any positive integer and 1<= x1<x2<....<x_(n+1)<=2n where x_i is an integer the which of following must be true :

I. there is x_i st : x_i is the square of integer
II. there is x_i st : x_(i+1)=x_i + 1
III. There is x_i that is prime

a. I only
b. II only
c. I , II
d. I, III
e. II, III


The answer is II...

Since we're talking about strategy, here's one step lesser:

Once we checked that I is false, we eliminate choices with I, which leaves us with choices (b) and (e). Then we check if III is true or false, which turns out to be false (reason as Wonderacle). We are left with II only and we didn't have to check for it's truth or falsehood.

[miguel]

For the problem on sequences, just consider when n=1. You'll soon see that II is the only true statement.

[MathCat]

For the problem on sequences, just consider when n=1. You'll soon see that II is the only true statement.

This does not work. The definition of the sequence requires you to pick 2 numbers if n=1. Then your sequence is 1, 2 and there is a prime. So it only eliminates I.