Can a Grasshopper Reach Infinite Points on a Number Line?

[niwaone]

Homework Statement

1. A grasshopper sitting on the number line can jump p or q inches right or left. Find all points on the line the grasshopper can reach starting from the origin (i.e. at zero).

2.Say exactly eight people show up to your birthday party, where there are two types of desserts: apple pie and birthday cake. As the host of the party, you have to make sure that one or more of the guests get a piece of pie, and one or more of them get a piece of cake. In how many different ways can you distribute the desserts, given that at least one person gets both a piece of cake and a piece of pie?

3. An alien lock has 16 keys arranged in a 4 × 4 grid, each key is either pointing horizontally or vertically. In order to open the lock, you must make sure that all the keys must be vertically oriented, by switching the orientation of one key at a time. When a key is switched to another position, all the other keys in the same row and column automatically switch their orientations too (i.e. vertical to horizontal, horizontal to vertical). Is it true that no matter what the initial positions of the 16 keys are, it is always possible to open
this lock?

The Attempt at a Solution

1. i think the grasshopper can jump infinite points on the line but I can't prove?
2. is it right to divide each cake and pie into 8 pieces and distribute to the 8 people so each of them can get both a piece of cake and pie?
3.someone please help me to solve this question because i think it's impossible to open the lock, but there may be another way to solve it (this reminds me of the rubik cube)

Thank you very much!

 

[daveb]

1. Suppose the grasshopper can jump 6 points to the right and 3 points to the left. Could it jump to "2"?

2. Is rather poorly worded, since it only stipulates that at least 1 person receive both. It doesn't require each receive a piece of both. Thus, you could also distribute it such that 1 person receives a piece of both, and everyone else receives only a piece of cake (there are a lot more combinations as well, which since this is a precalc problem, I say it is poorly constructed).

3. Again, a far too complex problem for precalc, but all you need to do is come up with a single example that doesn't work, rather than prove that it is possible.

 

[Joffan]

(1) see daveb's suggestion. Another one to consider: p=5/7, q=2/3

Note that (2) asks how many solutions, not for one solution. While giving everyone a slice of each works, so do many others (infinitely many if the number of pieces is unlimited), including giving just one person a piece of each (presumably "you", since it's your birthday).

One observation that might help you with (3) - and a way in which it is far far simpler than Rubik's cube - is that moves are commutative.

 

[niwaone]

(1) see daveb's suggestion. Another one to consider: p=5/7, q=2/3

Note that (2) asks how many solutions, not for one solution. While giving everyone a slice of each works, so do many others (infinitely many if the number of pieces is unlimited), including giving just one person a piece of each (presumably "you", since it's your birthday).

One observation that might help you with (3) - and a way in which it is far far simpler than Rubik's cube - is that moves are commutative.

can you explain further for number 3? I don't know how it's simpler?

 

[Joffan]

If I turn key A, then B, it's the same result as turning key B then key A. And in general, if I make make a sequence of key turns, the order is irrelevant; the result is the same.

This allows you to limit the number of different possible move sets.

Another possible reduction of the question would be: Is there a move set that results in just one key being turned, or is this impossible?

 

[niwaone]

If I turn key A, then B, it's the same result as turning key B then key A. And in general, if I make make a sequence of key turns, the order is irrelevant; the result is the same.

This allows you to limit the number of different possible move sets.

Another possible reduction of the question would be: Is there a move set that results in just one key being turned, or is this impossible?

So there's no way to unlock it, right?

 

[Joffan]

So there's no way to unlock it, right?

Guessing is not the same as mathematics

Guessing wrong is even worse. Find me the set of keys to turn that results in changing only key C2.

 

[niwaone]

Guessing is not the same as mathematics

Guessing wrong is even worse. Find me the set of keys to turn that results in changing only key C2.

What do you mean by changing only key C2?
My opinion: there is no way to unlock it because the diagram of the lock is not given and we can't just predict the way we want. Also, the question just said the 4*4 grid with some keys are vertical and horizontal, we can't find a unique way to change all the keys' directions to be vertical
What do you think about this question? If you know, please give me some hints? Thank you very much

 

[Joffan]

There is a way to change only one key (any key - no keys are special). Therefore any locked state can be changed to the unlocked state one key at a time.

Imagine that the current state is that only C2 is horizontal. Find the unlocking move set.

[The lock is a 4x4 grid of keys. I have jumped ahead and numbered these with a letter [A..D] for the row and a number [1..4] for the column. Turning A1 means that A2, A3, A4, B1, C1 and D1 also turn.]

 

[niwaone]

There is a way to change only one key (any key - no keys are special). Therefore any locked state can be changed to the unlocked state one key at a time.

Imagine that the current state is that only C2 is horizontal. Find the unlocking move set.

[The lock is a 4x4 grid of keys. I have jumped ahead and numbered these with a letter [A..D] for the row and a number [1..4] for the column. Turning A1 means that A2, A3, A4, B1, C1 and D1 also turn.]

so it seems possible to unlock this lock but like I say we need proofs to prove that this is possible. Can you show the detail explanation? Thank you

 

[Joffan]

The proof is a description of how to change one key at a time, and the argument that this can be applied repeatedly.

I did start at both ends of the problem. The idea that moves are commutative AND that a move is self inverse (A2.A2 = 0) means that any possible keymove sequence can be reduced to a move set which involves turning some of the keys once only. This means that the number of different key moves is 2^16 (each key is either moved or not). The number of different lock states is also 2^16 (each key is either horizontal or vertical). If I could show that two different (reduced) move sets result in the same state, then it would be true that some lock state does NOT have a corresponding move set, and that that lock state cannot be unlocked. I would NOT then have to actually show that locked state, but any single key, turned, would be such a state, because the ability to unlock a grid with a single horizontal key implies an ability to unlock the whole grid from any state.

Exercise:
If, starting from a unlocked state, I turn a full row of keys one after the other (with other keys responding to each turn of course), what is the grid state at the end?

 

[LCKurtz]

Please note Dick's comment in

https://www.physicsforums.com/showthread.php?t=560848

that these problems are from an entrance exam at St. Mary's college:

http://math.stmarys-ca.edu/smc2/SMC2quiz.pdf

 

[Dick]

Please note Dick's comment in

https://www.physicsforums.com/showthread.php?t=560848

that these problems are from an entrance exam.

Also note that I'm not saying giving help is a bad thing. We don't know that the context of these problems is the entrance exam, they may just have been borrowed from it. My main point is that niwaone doesn't seem to be contributing much. Don't contribute until you start getting something back. Definitely don't provide anything like complete solutions.

 

[LCKurtz]

Also note that I'm not saying giving help is a bad thing. We don't know that the context of these problems is the entrance exam, they may just have been borrowed from it. My main point is that niwaone doesn't seem to be contributing much. Don't contribute until you start getting something back. Definitely don't provide anything like complete solutions.

I dropped an email to the link given in that college's pdf file pointing out these threads and received an immediate reply which indicated they weren't too happy about it.

 

[Dick]

I dropped an email to the link given in that college's pdf file pointing out these threads and received an immediate reply which indicated they weren't too happy about it.

Ok. So now what? While I have an intrinsic belief there is no profit in cheating, hence niwaone won't do terribly well anyway. But nothing in their exam bans outside consulting. Did you ask the moderators if this should be removed? This is too bad. They were interesting questions.

 

[LCKurtz]

Ok. So now what? While I have an intrinsic belief there is no profit in cheating, hence niwaone won't do terribly well anyway. But nothing in their exam bans outside consulting. Did you ask the moderators if this should be removed? This is too bad. They were interesting questions.

No, I didn't contact the moderators. I think this is just the tip of the iceberg and that we here at PF are just deluding ourselves if we think this doesn't happen all the time. It is a fact of life for all instructors that with the internet being so available, you can never know that the work you are grading belongs to the students who turned it in. I think they just have to live with it and act accordingly. Makes me glad I am retired.

Still, I think PF performs a valuable function for those who use it properly. So now what? I think I will just continue on and not worry much about it.

 

[Dick]

No, I didn't contact the moderators. I think this is just the tip of the iceberg and that we here at PF are just deluding ourselves if we think this doesn't happen all the time. It is a fact of life for all instructors that with the internet being so available, you can never know that the work you are grading belongs to the students who turned it in. I think they just have to live with it and act accordingly. Makes me glad I am retired.

Still, I think PF performs a valuable function for those who use it properly. So now what? I think I will just continue on and not worry much about it.

Yeah, that's my attitude as well.

 

[Joffan]

I was thinking about the pie question (#2).

Of the eight guests, each of whom either has the pie or does not, and has the cake or does not, there are clearly 4^8 states (when counting multiple helpings of the same dessert as one). Some number of those states will include at least one guest who has both pie and cake - that, I assume, is the number we are after. The complement set, where no guest samples both desserts, is easier to establish - in this case each guest has only three possible states, not four.