GR9367 #35 and 61
GR9367 #35 and 61
35. Let f be a realvalued function defined on a set of integers and satisfying f(x)=1/2 f(x1) + 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 northsouth and eastwest 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!
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 northsouth and eastwest 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!
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.
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.
@amateur : your answer is great but I dont think many know about functional analysis. Let solve this problems as follow :35. Let f be a realvalued function defined on a set of integers and satisfying f(x)=1/2 f(x1) + 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
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 !
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.
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.
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 rewording of a "for all... there exists" statement)we can choose x_1=1 so x_1=1^1 so I is correct , is it ?
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")
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.
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.

 Posts: 5
 Joined: Wed Oct 01, 2008 4:26 pm
#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)=xxlnx,
put this back to the original integral,
Pr(X<YZ)
=int xxlnx dx from x=0 to 1
=(3/4)(x^2)(1/2)(x^2)(lnx) from x=0 to 1
=3/4
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)=xxlnx,
put this back to the original integral,
Pr(X<YZ)
=int xxlnx dx from x=0 to 1
=(3/4)(x^2)(1/2)(x^2)(lnx) from x=0 to 1
=3/4

 Posts: 5
 Joined: Wed Oct 01, 2008 4:26 pm
#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
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

 Posts: 16
 Joined: Wed Jul 22, 2009 1:20 am
Re:
Since we're talking about strategy, here's one step lesser:Nameless wrote:#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...
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.
Re: GR9367 #35 and 61
For the problem on sequences, just consider when n=1. You'll soon see that II is the only true statement.
Re: GR9367 #35 and 61
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.miguel wrote:For the problem on sequences, just consider when n=1. You'll soon see that II is the only true statement.