Knowee
Questions
Features
Study Tools

ere are five separate sets of grid squares.Let S be the set of finite sets of grid squares which form connected shapes. We do not count squares touchingdiagonally just at a vertex as being connected. The sets a, b, c and e on the above picture are elements of S. Set dis not an element of S.Let โˆผ be a binary relation on S. Say that s โˆผ t if and only if t can be obtained from s by moving the whole setby some sequence of any finite number (including none) of the following moves: move horizontally left one square,move horizontally right one square, move up one square, move down one square, rotate ninety degrees clockwise(about any square).So b โˆผ c in the diagram above.Show that โˆผ is an equivalence relation

Question

ere are five separate sets of grid squares.Let S be the set of finite sets of grid squares which form connected shapes. We do not count squares touchingdiagonally just at a vertex as being connected. The sets a, b, c and e on the above picture are elements of S. Set dis not an element of S.Let โˆผ be a binary relation on S. Say that s โˆผ t if and only if t can be obtained from s by moving the whole setby some sequence of any finite number (including none) of the following moves: move horizontally left one square,move horizontally right one square, move up one square, move down one square, rotate ninety degrees clockwise(about any square).So b โˆผ c in the diagram above.Show that โˆผ is an equivalence relation

...expand
๐Ÿง Not the exact question you are looking for?Go ask a question

Solution

An equivalence relation must satisfy three properties: reflexivity, symmetry, and transitivity.

  1. Reflexivity: For any set s in S, s โˆผ s. This is because we can obtain s from itself by making no moves. So, the reflexivity property is satisfied.

  2. Symmetry: If s โˆผ t for any sets s and t in S, then t โˆผ s. This is because if t can be obtained from s by a sequence of moves, then s can be obtained from t by the reverse sequence of moves. So, the symmetry property is satisfied.

  3. Transitivity: If s โˆผ t and t โˆผ u for any sets s, t, and u in S, then s โˆผ u. This is because if t can be obtained from s by a sequence of moves, and u can be obtained from t by another sequence of moves, then u can be obtained from s by the combined sequence of moves. So, the transitivity property is satisfied.

Since โˆผ satisfies the properties of reflexivity, symmetry, and transitivity, โˆผ is an equivalence relation.

This problem has been solved

Similar Questions

My First Geometry ProblemYou are on a 22-dimensional grid, where you start at (0,0)(0,0).You are given a binary string ๐‘†S of length 44 where:๐‘†1S 1โ€‹ refers to left direction;๐‘†2S 2โ€‹ refers to right direction;๐‘†3S 3โ€‹ refers to up direction;๐‘†4S 4โ€‹ refers to down direction.๐‘†๐‘–=1S iโ€‹ =1 denotes that you are allowed to make a move in the respective direction and vice-versa.Find the number of cells (๐‘ฅ,๐‘ฆ)(x,y) you can possibly visit which satisfy โˆ’10โ‰ค๐‘ฅ,๐‘ฆโ‰ค10โˆ’10โ‰คx,yโ‰ค10.Note that:You always include the cell (0,0)(0,0) in your answer.If you can visit (๐ด1,๐ต1)(A 1โ€‹ ,B 1โ€‹ ) and (๐ด2,๐ต2)(A 2โ€‹ ,B 2โ€‹ ) individually, but not both at the same time, you will still include both of them in your answer.Moves are defined as:A move in left direction is a move from cell (๐ด,๐ต)(A,B) to (๐ดโˆ’1,๐ต)(Aโˆ’1,B).A move in right direction is a move from cell (๐ด,๐ต)(A,B) to (๐ด+1,๐ต)(A+1,B).A move in up direction is a move from cell (๐ด,๐ต)(A,B) to (๐ด,๐ต+1)(A,B+1).A move in down direction is a move from cell (๐ด,๐ต)(A,B) to (๐ด,๐ตโˆ’1)(A,Bโˆ’1).Input FormatThe first line of input will contain a single integer ๐‘‡T, denoting the number of test cases.Each test case consists of a binary string ๐‘†S of length 44 - denoting the directions in which moves are allowed.Output FormatFor each test case, output on a new line, the number of cells you can visit as mentioned in statement.Constraints1โ‰ค๐‘‡โ‰ค151โ‰คTโ‰ค15โˆฃ๐‘†โˆฃ=4โˆฃSโˆฃ=4๐‘†๐‘–โˆˆ{0,1}S iโ€‹ โˆˆ{0,1}๐‘†๐‘–=1S iโ€‹ =1 for at least one 1โ‰ค๐‘–โ‰ค41โ‰คiโ‰ค4.Sample 1:InputOutput5001011000110111011111121121231441Explanation:Test case 11: The only allowed direction is up. Thus, you can only visit cells (0,0),(0,1),(0,2),โ€ฆ,(0,10)(0,0),(0,1),(0,2),โ€ฆ,(0,10); which are a total of 1111 cells.Test case 22: The allowed directions are left and right. Thus, you can visit cells (โˆ’10,0),(โˆ’9,0),โ€ฆ,(0,0),โ€ฆ,(9,0),(10,0)(โˆ’10,0),(โˆ’9,0),โ€ฆ,(0,0),โ€ฆ,(9,0),(10,0), which are a total of 2121 cells.Test case 33: The allowed directions are right and up. You can visit all cells (๐‘ฅ,๐‘ฆ)(x,y) such that ๐‘ฅโ‰ฅ0xโ‰ฅ0 and ๐‘ฆโ‰ฅ0yโ‰ฅ0, which are a total of 121121 cells.Accepted195Submissions293

You are given four integers sx, sy, fx, fy, and a non-negative integer t.In an infinite 2D grid, you start at the cell (sx, sy). Each second, you must move to any of its adjacent cells.Return true if you can reach cell (fx, fy) after exactly t seconds, or false otherwise.A cell's adjacent cells are the 8 cells around it that share at least one corner with it. You can visit the same cell several times.

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.ย Example 1:Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0Output: 6

You are on a 22-dimensional grid, where you start at (0,0)(0,0).You are given a binary string ๐‘†S of length 44 where:๐‘†1S 1โ€‹ refers to left direction;๐‘†2S 2โ€‹ refers to right direction;๐‘†3S 3โ€‹ refers to up direction;๐‘†4S 4โ€‹ refers to down direction.๐‘†๐‘–=1S iโ€‹ =1 denotes that you are allowed to make a move in the respective direction and vice-versa.Find the number of cells (๐‘ฅ,๐‘ฆ)(x,y) you can possibly visit which satisfy โˆ’10โ‰ค๐‘ฅ,๐‘ฆโ‰ค10โˆ’10โ‰คx,yโ‰ค10.Note that:You always include the cell (0,0)(0,0) in your answer.If you can visit (๐ด1,๐ต1)(A 1โ€‹ ,B 1โ€‹ ) and (๐ด2,๐ต2)(A 2โ€‹ ,B 2โ€‹ ) individually, but not both at the same time, you will still include both of them in your answer.Moves are defined as:A move in left direction is a move from cell (๐ด,๐ต)(A,B) to (๐ดโˆ’1,๐ต)(Aโˆ’1,B).A move in right direction is a move from cell (๐ด,๐ต)(A,B) to (๐ด+1,๐ต)(A+1,B).A move in up direction is a move from cell (๐ด,๐ต)(A,B) to (๐ด,๐ต+1)(A,B+1).A move in down direction is a move from cell (๐ด,๐ต)(A,B) to (๐ด,๐ตโˆ’1)(A,Bโˆ’1).Input FormatThe first line of input will contain a single integer ๐‘‡T, denoting the number of test cases.Each test case consists of a binary string ๐‘†S of length 44 - denoting the directions in which moves are allowed.Output FormatFor each test case, output on a new line, the number of cells you can visit as mentioned in statement.Constraints1โ‰ค๐‘‡โ‰ค151โ‰คTโ‰ค15โˆฃ๐‘†โˆฃ=4โˆฃSโˆฃ=4๐‘†๐‘–โˆˆ{0,1}S iโ€‹ โˆˆ{0,1}๐‘†๐‘–=1S iโ€‹ =1 for at least one 1โ‰ค๐‘–โ‰ค41โ‰คiโ‰ค4.Sample 1:InputOutput5001011000110111011111121121231441Explanation:Test case 11: The only allowed direction is up. Thus, you can only visit cells (0,0),(0,1),(0,2),โ€ฆ,(0,10)(0,0),(0,1),(0,2),โ€ฆ,(0,10); which are a total of 1111 cells.Test case 22: The allowed directions are left and right. Thus, you can visit cells (โˆ’10,0),(โˆ’9,0),โ€ฆ,(0,0),โ€ฆ,(9,0),(10,0)(โˆ’10,0),(โˆ’9,0),โ€ฆ,(0,0),โ€ฆ,(9,0),(10,0), which are a total of 2121 cells.Test case 33: The allowed directions are right and up. You can visit all cells (๐‘ฅ,๐‘ฆ)(x,y) such that ๐‘ฅโ‰ฅ0xโ‰ฅ0 and ๐‘ฆโ‰ฅ0yโ‰ฅ0, which are a total of 121121 cells.

This is the net of a square-based pyramid. How many such nets are there in total, not counting those which are equal by rotations/mirror symmetry?

1/1

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.